Space-Time Trade-offs in Node Design

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140

/**
 * Cache-Aware Trie Node Design
 * 
 * This implementation demonstrates cache-conscious design principles.
 * In JavaScript/TypeScript, we have limited control over memory layout,
 * but we can still apply the principles.
 */
 
/**
 * Strategy 1: Node Pooling
 * Allocate nodes from a contiguous pool to improve spatial locality.
 * Nodes created around the same time are close in memory.
 */
class TrieNodePool {
    private nodes: CacheAwareNode[] = [];
    private freeList: number[] = [];
    
    allocateNode(): CacheAwareNode {
        if (this.freeList.length > 0) {
            const index = this.freeList.pop()!;
            return this.nodes[index];
        }
        
        const node = new CacheAwareNode(this.nodes.length);
        this.nodes.push(node);
        return node;
    }
    
    freeNode(node: CacheAwareNode): void {
        node.reset();
        this.freeList.push(node.poolIndex);
    }
    
    // Get nodes in sorted order for cache-friendly traversal
    getNodesInOrder(): CacheAwareNode[] {
        return [...this.nodes].sort((a, b) => a.poolIndex - b.poolIndex);
    }
}
 
class CacheAwareNode {
    poolIndex: number;
    
    // Fixed-size children array for English lowercase
    // Keeping it small helps fit in cache line
    children: (CacheAwareNode | null)[];
    
    isEndOfWord: boolean = false;
    
    // Optional: Keep frequently accessed data at the start
    // to maximize chance it's in the same cache line
    prefixCount: number = 0;
    
    constructor(poolIndex: number) {
        this.poolIndex = poolIndex;
        this.children = new Array(26).fill(null);
    }
    
    reset(): void {
        this.children.fill(null);
        this.isEndOfWord = false;
        this.prefixCount = 0;
    }
    
    getChild(char: string): CacheAwareNode | null {
        return this.children[char.charCodeAt(0) - 97];
    }
    
    setChild(char: string, node: CacheAwareNode): void {
        this.children[char.charCodeAt(0) - 97] = node;
    }
}
 
/**
 * Strategy 2: Hot/Cold Separation
 * Keep frequently accessed data separate from rarely accessed data.
 * Hot data stays in cache; cold data is accessed only when needed.
 */
interface HotNodeData {
    // Frequently accessed - keep small
    children: (number | null)[]; // Indices into node array
    isEndOfWord: boolean;
}
 
interface ColdNodeData {
    // Rarely accessed - can be larger
    wordFrequency: number;
    metadata: string;
    timestamps: number[];
}
 
class HotColdTrie {
    private hotData: HotNodeData[] = [];
    private coldData: ColdNodeData[] = [];
    
    addNode(): number {
        const index = this.hotData.length;
        
        // Hot data: minimal, frequently accessed
        this.hotData.push({
            children: new Array(26).fill(null),
            isEndOfWord: false
        });
        
        // Cold data: initialized lazily or with defaults
        this.coldData.push({
            wordFrequency: 0,
            metadata: '',
            timestamps: []
        });
        
        return index;
    }
    
    // Fast path: only touches hot data
    search(word: string): boolean {
        let nodeIndex = 0; // Root
        
        for (const char of word) {
            const childIndex = this.hotData[nodeIndex].children[char.charCodeAt(0) - 97];
            if (childIndex === null) return false;
            nodeIndex = childIndex;
        }
        
        return this.hotData[nodeIndex].isEndOfWord;
    }
    
    // Slow path: accesses cold data when needed
    getMetadata(word: string): string | null {
        let nodeIndex = 0;
        
        for (const char of word) {
            const childIndex = this.hotData[nodeIndex].children[char.charCodeAt(0) - 97];
            if (childIndex === null) return null;
            nodeIndex = childIndex;
        }
        
        if (!this.hotData[nodeIndex].isEndOfWord) return null;
        return this.coldData[nodeIndex].metadata;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

/**
 * Trie with precomputed statistics
 * Demonstrates the trade-off between space and query performance
 */
class PrecomputedTrieNode {
    children: Map<string, PrecomputedTrieNode> = new Map();
    isEndOfWord: boolean = false;
    
    // Precomputed data - costs 20+ bytes but enables O(1) queries
    wordCount: number = 0;      // Words ending at or below this node
    prefixCount: number = 0;    // Words passing through this node
    childCount: number = 0;     // Direct children (for fast leaf check)
    depth: number = 0;          // Distance from root
    minWordLength: number = Infinity;  // Shortest word in subtree
    maxWordLength: number = 0;         // Longest word in subtree
    
    isLeaf(): boolean {
        return this.childCount === 0;  // O(1) instead of checking children.size
    }
}
 
class PrecomputedTrie {
    private root: PrecomputedTrieNode = new PrecomputedTrieNode();
    
    /**
     * Insert with precomputation maintenance
     * Time: O(m) same as before, but with constant factor overhead
     */
    insert(word: string): void {
        let current = this.root;
        current.prefixCount++;
        
        for (let i = 0; i < word.length; i++) {
            const char = word[i];
            
            if (!current.children.has(char)) {
                const newNode = new PrecomputedTrieNode();
                newNode.depth = current.depth + 1;
                current.children.set(char, newNode);
                current.childCount++;  // Maintain precomputed count
            }
            
            current = current.children.get(char)!;
            current.prefixCount++;
        }
        
        if (!current.isEndOfWord) {
            // New word - update word counts along the path
            current.isEndOfWord = true;
            current.wordCount++;
            this.updateWordLengthStats(word);
        }
    }
    
    private updateWordLengthStats(word: string): void {
        let current = this.root;
        const wordLength = word.length;
        
        // Update min/max word length on each node along the path
        current.minWordLength = Math.min(current.minWordLength, wordLength);
        current.maxWordLength = Math.max(current.maxWordLength, wordLength);
        
        for (const char of word) {
            current = current.children.get(char)!;
            current.minWordLength = Math.min(current.minWordLength, wordLength);
            current.maxWordLength = Math.max(current.maxWordLength, wordLength);
        }
    }
    
    /**
     * Count words with prefix - O(m) traverse + O(1) lookup
     * Without precomputation: O(m + subtree size)
     */
    countWordsWithPrefix(prefix: string): number {
        const node = this.traverseToNode(prefix);
        if (!node) return 0;
        return node.prefixCount;  // Precomputed!
    }
    
    /**
     * Check if any words exist with length in range
     * O(m) traverse + O(1) check
     * Without precomputation: O(m + subtree size)
     */
    hasWordsInLengthRange(prefix: string, minLen: number, maxLen: number): boolean {
        const node = this.traverseToNode(prefix);
        if (!node) return false;
        
        // Use precomputed min/max to answer instantly
        return node.minWordLength <= maxLen && node.maxWordLength >= minLen;
    }
    
    /**
     * Get statistics about a prefix - all O(1) after traversal
     */
    getPrefixStats(prefix: string): {
        exists: boolean;
        wordCount: number;
        prefixCount: number;
        minWordLength: number;
        maxWordLength: number;
    } | null {
        const node = this.traverseToNode(prefix);
        if (!node) return null;
        
        return {
            exists: true,
            wordCount: node.wordCount,
            prefixCount: node.prefixCount,
            minWordLength: node.minWordLength,
            maxWordLength: node.maxWordLength
        };
    }
    
    private traverseToNode(str: string): PrecomputedTrieNode | null {
        let current = this.root;
        for (const char of str) {
            const child = current.children.get(char);
            if (!child) return null;
            current = child;
        }
        return current;
    }
}
 
// Demonstrate the benefit
const trie = new PrecomputedTrie();
const words = ["apple", "app", "application", "apply", "banana", "band"];
words.forEach(w => trie.insert(w));
 
// O(3) traverse + O(1) lookup instead of O(3 + subtree enumeration)
console.log("Words with 'app':", trie.countWordsWithPrefix("app")); // 4
 
// O(1) range check instead of enumerating all words
console.log("Has 3-5 letter words:", trie.hasWordsInLengthRange("app", 3, 5)); // true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155

/**
 * Compact Trie Node using bit packing and index references
 * Optimized for minimal memory footprint
 */
class CompactTrieNode {
    /**
     * Packed flags field (32 bits):
     * - bit 0: isEndOfWord
     * - bits 1-5: reserved
     * - bits 6-31: wordCount (up to 67 million)
     */
    private flags: number = 0;
    
    /**
     * Children stored as indices into a node pool
     * Using Uint32Array for fixed-size, typed storage
     * Value 0xFFFFFFFF means "no child"
     */
    children: Uint32Array;
    
    private static readonly NO_CHILD = 0xFFFFFFFF;
    private static readonly END_OF_WORD_MASK = 0x01;
    private static readonly WORD_COUNT_SHIFT = 6;
    
    constructor(alphabetSize: number = 26) {
        this.children = new Uint32Array(alphabetSize);
        this.children.fill(CompactTrieNode.NO_CHILD);
    }
    
    get isEndOfWord(): boolean {
        return (this.flags & CompactTrieNode.END_OF_WORD_MASK) !== 0;
    }
    
    set isEndOfWord(value: boolean) {
        if (value) {
            this.flags |= CompactTrieNode.END_OF_WORD_MASK;
        } else {
            this.flags &= ~CompactTrieNode.END_OF_WORD_MASK;
        }
    }
    
    get wordCount(): number {
        return this.flags >>> CompactTrieNode.WORD_COUNT_SHIFT;
    }
    
    set wordCount(value: number) {
        this.flags = (this.flags & 0x3F) | (value << CompactTrieNode.WORD_COUNT_SHIFT);
    }
    
    getChildIndex(char: string): number {
        const idx = char.charCodeAt(0) - 97; // 'a' = 0
        const childIdx = this.children[idx];
        return childIdx === CompactTrieNode.NO_CHILD ? -1 : childIdx;
    }
    
    setChildIndex(char: string, nodeIndex: number): void {
        const idx = char.charCodeAt(0) - 97;
        this.children[idx] = nodeIndex;
    }
    
    hasChild(char: string): boolean {
        return this.getChildIndex(char) !== -1;
    }
    
    /**
     * Estimate memory usage of this node
     */
    static estimateBytes(alphabetSize: number): number {
        // Object overhead + flags + TypedArray overhead + array data
        return 16 + 4 + 16 + (alphabetSize * 4);
    }
}
 
/**
 * Compact Trie using node pool with index-based references
 */
class CompactTrie {
    private nodes: CompactTrieNode[] = [];
    private alphabetSize: number;
    
    constructor(alphabetSize: number = 26) {
        this.alphabetSize = alphabetSize;
        // Create root node
        this.nodes.push(new CompactTrieNode(alphabetSize));
    }
    
    private allocateNode(): number {
        const index = this.nodes.length;
        this.nodes.push(new CompactTrieNode(this.alphabetSize));
        return index;
    }
    
    insert(word: string): void {
        let nodeIndex = 0; // Root
        
        for (const char of word.toLowerCase()) {
            let childIndex = this.nodes[nodeIndex].getChildIndex(char);
            
            if (childIndex === -1) {
                childIndex = this.allocateNode();
                this.nodes[nodeIndex].setChildIndex(char, childIndex);
            }
            
            nodeIndex = childIndex;
        }
        
        const node = this.nodes[nodeIndex];
        node.isEndOfWord = true;
        node.wordCount = node.wordCount + 1;
    }
    
    search(word: string): boolean {
        let nodeIndex = 0;
        
        for (const char of word.toLowerCase()) {
            const childIndex = this.nodes[nodeIndex].getChildIndex(char);
            if (childIndex === -1) return false;
            nodeIndex = childIndex;
        }
        
        return this.nodes[nodeIndex].isEndOfWord;
    }
    
    /**
     * Get memory usage statistics
     */
    getMemoryStats(): {
        nodeCount: number;
        bytesPerNode: number;
        totalBytes: number;
        vsStandardBytes: number;
        savingsPercent: number;
    } {
        const nodeCount = this.nodes.length;
        const bytesPerNode = CompactTrieNode.estimateBytes(this.alphabetSize);
        const totalBytes = nodeCount * bytesPerNode;
        
        // Standard node with Map and regular properties: ~200+ bytes
        const standardBytesPerNode = 200;
        const vsStandardBytes = nodeCount * standardBytesPerNode;
        
        return {
            nodeCount,
            bytesPerNode,
            totalBytes,
            vsStandardBytes,
            savingsPercent: Math.round((1 - totalBytes / vsStandardBytes) * 100)
        };
    }
}
 
// Memory comparison
const compactTrie = new CompactTrie();
console.log("Bytes per compact node:", CompactTrieNode.estimateBytes(26));  // ~140 bytes
// Compare to standard Map-based node: ~200+ bytes (30%+ savings)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

/**
 * Hybrid allocation strategy: Start lazy, convert to eager when dense
 */
class AdaptiveAllocationNode {
    private lazyChildren: Map<string, AdaptiveAllocationNode> | null = new Map();
    private eagerChildren: (AdaptiveAllocationNode | null)[] | null = null;
    
    private static readonly CONVERSION_THRESHOLD = 10; // Convert at 10 children
    
    isEndOfWord: boolean = false;
    
    getChild(char: string): AdaptiveAllocationNode | null {
        if (this.eagerChildren) {
            return this.eagerChildren[char.charCodeAt(0) - 97];
        }
        return this.lazyChildren?.get(char) ?? null;
    }
    
    setChild(char: string, node: AdaptiveAllocationNode): void {
        if (this.eagerChildren) {
            this.eagerChildren[char.charCodeAt(0) - 97] = node;
            return;
        }
        
        this.lazyChildren!.set(char, node);
        
        // Check if we should convert to eager allocation
        if (this.lazyChildren!.size >= AdaptiveAllocationNode.CONVERSION_THRESHOLD) {
            this.convertToEager();
        }
    }
    
    private convertToEager(): void {
        this.eagerChildren = new Array(26).fill(null);
        
        for (const [char, node] of this.lazyChildren!) {
            this.eagerChildren[char.charCodeAt(0) - 97] = node;
        }
        
        this.lazyChildren = null; // Free the map
    }
    
    removeChild(char: string): boolean {
        if (this.eagerChildren) {
            const index = char.charCodeAt(0) - 97;
            if (this.eagerChildren[index]) {
                this.eagerChildren[index] = null;
                return true;
            }
            return false;
        }
        return this.lazyChildren?.delete(char) ?? false;
    }
    
    getChildCount(): number {
        if (this.eagerChildren) {
            return this.eagerChildren.filter(c => c !== null).length;
        }
        return this.lazyChildren?.size ?? 0;
    }
    
    /**
     * Get current allocation mode (for analysis)
     */
    getAllocationMode(): 'lazy' | 'eager' {
        return this.eagerChildren ? 'eager' : 'lazy';
    }
}
 
/**
 * Deferred allocation: Delay node creation entirely
 * Useful when most insertions share common prefixes
 */
class DeferredAllocationTrie {
    private pendingWords: string[] = [];
    private root: SimpleNode | null = null;
    private readonly BATCH_THRESHOLD = 1000;
    
    insert(word: string): void {
        this.pendingWords.push(word);
        
        if (this.pendingWords.length >= this.BATCH_THRESHOLD) {
            this.flush();
        }
    }
    
    search(word: string): boolean {
        // Must flush to search accurately
        if (this.pendingWords.length > 0) {
            this.flush();
        }
        return this.searchInTrie(word);
    }
    
    private flush(): void {
        // Sort words to maximize prefix sharing during batch insert
        this.pendingWords.sort();
        
        if (!this.root) {
            this.root = new SimpleNode();
        }
        
        for (const word of this.pendingWords) {
            this.insertIntoTrie(word);
        }
        
        this.pendingWords = [];
    }
    
    private insertIntoTrie(word: string): void {
        let current = this.root!;
        for (const char of word) {
            if (!current.children.has(char)) {
                current.children.set(char, new SimpleNode());
            }
            current = current.children.get(char)!;
        }
        current.isEndOfWord = true;
    }
    
    private searchInTrie(word: string): boolean {
        if (!this.root) return false;
        let current = this.root;
        for (const char of word) {
            if (!current.children.has(char)) return false;
            current = current.children.get(char)!;
        }
        return current.isEndOfWord;
    }
}
 
class SimpleNode {
    children: Map<string, SimpleNode> = new Map();
    isEndOfWord: boolean = false;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172

/**
 * Trie Benchmark Framework
 * Measure time and space characteristics of different implementations
 */
interface BenchmarkResult {
    implementation: string;
    operationType: string;
    operationCount: number;
    totalTimeMs: number;
    avgTimeNs: number;
    opsPerSecond: number;
    p50TimeNs: number;
    p99TimeNs: number;
    memoryBefore: number;
    memoryAfter: number;
    memoryDelta: number;
}
 
interface TrieInterface {
    insert(word: string): void;
    search(word: string): boolean;
    startsWith(prefix: string): boolean;
}
 
class TrieBenchmark {
    /**
     * Warm up the JIT compiler and caches
     */
    private warmUp(trie: TrieInterface, words: string[], iterations: number = 1000): void {
        for (let i = 0; i < iterations; i++) {
            const word = words[i % words.length];
            trie.insert(word);
            trie.search(word);
        }
    }
    
    /**
     * Measure operation latencies with high precision
     */
    measureLatencies(
        operation: () => void,
        iterations: number
    ): { times: number[]; avg: number; p50: number; p99: number } {
        const times: number[] = [];
        
        for (let i = 0; i < iterations; i++) {
            const start = performance.now();
            operation();
            const end = performance.now();
            times.push((end - start) * 1_000_000); // Convert to nanoseconds
        }
        
        times.sort((a, b) => a - b);
        
        const avg = times.reduce((a, b) => a + b, 0) / times.length;
        const p50 = times[Math.floor(times.length * 0.5)];
        const p99 = times[Math.floor(times.length * 0.99)];
        
        return { times, avg, p50, p99 };
    }
    
    /**
     * Measure memory impact of building a trie
     */
    measureMemory(
        createTrie: () => TrieInterface,
        words: string[]
    ): { bytesPerWord: number; bytesPerNode: number; totalBytes: number } {
        // Force garbage collection if possible
        if (global.gc) global.gc();
        
        const memBefore = process.memoryUsage().heapUsed;
        
        const trie = createTrie();
        for (const word of words) {
            trie.insert(word);
        }
        
        if (global.gc) global.gc();
        
        const memAfter = process.memoryUsage().heapUsed;
        const totalBytes = memAfter - memBefore;
        
        return {
            bytesPerWord: totalBytes / words.length,
            bytesPerNode: 0, // Would need internal node count
            totalBytes
        };
    }
    
    /**
     * Run comprehensive benchmark comparing implementations
     */
    async runComparison(
        implementations: { name: string; create: () => TrieInterface }[],
        testWords: string[],
        searchWords: string[],
        prefixes: string[]
    ): Promise<BenchmarkResult[]> {
        const results: BenchmarkResult[] = [];
        
        for (const impl of implementations) {
            console.log(`
Benchmarking: ${impl.name}`);
            
            // Memory measurement
            const memResult = this.measureMemory(impl.create, testWords);
            console.log(`  Memory: ${(memResult.totalBytes / 1024 / 1024).toFixed(2)} MB`);
            console.log(`  Per word: ${memResult.bytesPerWord.toFixed(0)} bytes`);
            
            // Create fresh trie for latency tests
            const trie = impl.create();
            this.warmUp(trie, testWords);
            
            // Reset and insert all words
            const freshTrie = impl.create();
            
            // Insert benchmark
            const insertLatency = this.measureLatencies(
                () => {
                    for (const word of testWords) {
                        freshTrie.insert(word);
                    }
                },
                10
            );
            
            console.log(`  Insert avg: ${(insertLatency.avg / testWords.length).toFixed(0)} ns/word`);
            
            // Search benchmark
            const searchLatency = this.measureLatencies(
                () => {
                    for (const word of searchWords) {
                        freshTrie.search(word);
                    }
                },
                100
            );
            
            console.log(`  Search avg: ${(searchLatency.avg / searchWords.length).toFixed(0)} ns/word`);
            console.log(`  Search p99: ${(searchLatency.p99 / searchWords.length).toFixed(0)} ns/word`);
            
            // Prefix benchmark
            const prefixLatency = this.measureLatencies(
                () => {
                    for (const prefix of prefixes) {
                        freshTrie.startsWith(prefix);
                    }
                },
                100
            );
            
            console.log(`  Prefix avg: ${(prefixLatency.avg / prefixes.length).toFixed(0)} ns/prefix`);
            
            results.push({
                implementation: impl.name,
                operationType: 'combined',
                operationCount: testWords.length,
                totalTimeMs: insertLatency.avg / 1_000_000,
                avgTimeNs: searchLatency.avg / searchWords.length,
                opsPerSecond: 1_000_000_000 / (searchLatency.avg / searchWords.length),
                p50TimeNs: searchLatency.p50 / searchWords.length,
                p99TimeNs: searchLatency.p99 / searchWords.length,
                memoryBefore: 0,
                memoryAfter: memResult.totalBytes,
                memoryDelta: memResult.totalBytes
            });
        }
        
        return results;
    }
}