Skip to main content

PERFORMANCE

Understand how data-structure-typed performs, and when to use each structure.

Back to README • Architecture Details • Code Examples • 📈 Interactive HTML Report

Table of Contents​

  1. Performance Summary
  2. Real-World Scenarios
  3. Detailed Benchmarks
  4. When to Use What
  5. Optimization Tips

Performance Summary​

Note on JS vs C++ gaps: Many “C++ faster” results are primarily explained by runtime / memory-model differences, not a flaw in data-structure-typed. JavaScript runs on a GC’d VM with boxed numbers, dynamic dispatch, and different cache/memory behavior, while C++ can use tight value types and predictable memory layouts. When the benchmark mixes in baseline containers (Native JS / js-sdsl / C++), treat cross-language comparisons as directional and rely most on within-JS comparisons for practical decisions.

Key Numbers​

  • 484x faster than Array.shift() with 100K elements (Deque vs Array)
  • 40x–308x faster in repeated “update + resort” workloads (RedBlackTree vs Array)
  • O(log n) guaranteed on all balanced tree operations
  • O(1) guaranteed on Deque head/tail operations
  • Benchmarks include warm-up runs to reduce V8 JIT noise

Performance Tier Chart​

StructureAccessSearchInsertDeleteBest For
ArrayO(1)O(n)O(n)O(n)Random access
LinkedListO(n)O(n)O(1)*O(1)*If you have pointer
Stack--O(1)O(1)LIFO, undo/redo
Queue--O(1)O(1)FIFO, message queues
Deque--O(1)O(1)Head/tail ops
BSTO(log n)O(log n)O(log n)O(log n)Sorted if balanced
RedBlackTreeO(log n)O(log n)O(log n)O(log n)Guaranteed sorted
AVL TreeO(log n)O(log n)O(log n)O(log n)Max search speed
HeapO(n)O(n)O(log n)O(log n)Priority queue
TrieN/AO(m)O(m)O(m)Prefix search

Benchmark​

Queue​

Test CaseAvg (ms)Min (ms)Max (ms)Stability
1M push26.9324.4151.97±4.28%
100K push & shift3.452.7215.26±8.97%

Queue (side-by-side)​

Comparison table. The main table above is Queue only. Native is - when there is no apples-to-apples equivalent in this benchmark.

Test CaseDST (ms)Native (ms)C++ (ms)js-sdsl (ms)
1M push26.9323.831.7027.59
100K push & shift3.451152.770.202.71

Deque​

Test CaseAvg (ms)Min (ms)Max (ms)Stability
1M push9.776.2721.63±9.28%
1M push & pop14.7511.8031.16±5.06%
1M push & shift14.6113.3140.42±5.25%
100K push & shift1.291.193.37±3.91%
100K unshift & shift1.261.142.75±3.59%

Deque (side-by-side)​

Comparison table. The main table above is Deque only. Native is - when there is no apples-to-apples equivalent in this benchmark.

Test CaseDST (ms)Native (ms)C++ (ms)js-sdsl (ms)
1M push9.7726.811.767.79
1M push & pop14.7527.962.2012.34
1M push & shift14.61-1.94-
100K push & shift1.291243.770.191.17
100K unshift & shift1.261867.280.191.17

DoublyLinkedList​

Test CaseAvg (ms)Min (ms)Max (ms)Stability
100k push5.704.807.27±1.57%
100k unshift5.574.6313.65±5.7%
100k unshift & shift4.043.875.34±1.3%
100k addAt(mid)1865.991778.941992.65±5.43%
100k addBefore (cursor)6.815.3217.77±4.44%

DoublyLinkedList (side-by-side)​

Comparison table. The main table above is DoublyLinkedList only. Native is - when there is no apples-to-apples equivalent in this benchmark.

Test CaseDST (ms)Native (ms)C++ (ms)js-sdsl (ms)
100k push5.702.405.701.90
100k unshift5.57884.065.851.52
100k unshift & shift4.042050.715.741.89
100k addAt(mid)1865.99-754.81-
100k addBefore (cursor)6.81-6.18-

SinglyLinkedList​

Test CaseAvg (ms)Min (ms)Max (ms)Stability
100K unshift & shift3.773.623.99±0.41%
10K unshift & shift0.370.360.44±0.78%
10K addAt(mid)18.6117.6125.55±1.66%
10K addBefore (cursor)17.5616.6720.17±1.11%

SinglyLinkedList (side-by-side)​

Comparison table. The main table above is SinglyLinkedList only. Native is - when there is no apples-to-apples equivalent in this benchmark.

Test CaseDST (ms)Native (ms)C++ (ms)js-sdsl (ms)
100K unshift & shift3.771958.394.80-
10K unshift & shift0.376.260.47-
10K addAt(mid)18.61-5.77-
10K addBefore (cursor)17.56-0.53-

PriorityQueue​

Test CaseAvg (ms)Min (ms)Max (ms)Stability
100K add4.003.804.41±0.6%
100K add & poll22.5121.2342.99±3.19%

PriorityQueue (side-by-side)​

Comparison table. The main table above is PriorityQueue only. Native is - when there is no apples-to-apples equivalent in this benchmark.

Test CaseDST (ms)Native (ms)C++ (ms)js-sdsl (ms)
100K add4.00-1.054.96
100K add & poll22.51-4.5322.97

TreeSet​

Test CaseAvg (ms)Min (ms)Max (ms)Stability
1M add995.72948.081124.92±6.28%
1M has67.8064.5386.26±1.67%
100K rangeSearch17.3416.7918.81±0.46%
100K navigable118.65117.95119.38±0.14%

TreeSet (side-by-side)​

Comparison table. The main table above is TreeSet only. Native is - when there is no apples-to-apples equivalent in this benchmark.

Test CaseDST (ms)DST classic (ms)Native (ms)C++ (ms)js-sdsl (ms)
1M add995.72807.88-462.00677.58
1M has67.80747.62-444.00655.62
100K rangeSearch17.3416.70---
100K navigable118.65123.91---

TreeMap​

Test CaseAvg (ms)Min (ms)Max (ms)Stability
1M set978.72934.591130.02±6.39%
1M get127.82123.10133.96±1.2%
100K rangeSearch38.1734.80100.14±6.97%
100K navigable160.66151.89307.88±9.6%

TreeMap (side-by-side)​

Comparison table. The main table above is TreeMap only. Native is - when there is no apples-to-apples equivalent in this benchmark.

Test CaseDST (ms)DST classic (ms)Native (ms)C++ (ms)js-sdsl (ms)
1M set978.72831.32-512.00623.23
1M get127.82719.05-322.00626.87
100K rangeSearch38.1734.42---
100K navigable160.66213.76---

TreeMultiSet​

Test CaseAvg (ms)Min (ms)Max (ms)Stability
1M add (TreeMultiSet expanded iteration)217.73191.17319.78±8.07%
1M has-only (TreeMultiSet)67.6766.0872.83±0.72%
1M count-only (TreeMultiSet)55.7453.9457.60±0.49%
1M build+has (TreeMultiSet)260.84248.30300.22±2.79%
1M build+count (TreeMultiSet)267.81242.77339.53±5.97%
100K delete-one (TreeMultiSet)217.76201.92254.80±2.97%
100K setCount (TreeMultiSet)214.66201.65264.54±3.65%
1M expanded iteration (TreeMultiSet)54.4153.1462.22±0.78%
1M entries view (TreeMultiSet)15.6714.8117.19±0.72%
1M size property (TreeMultiSet)0.000.000.00±3.47%
1M distinctSize property (TreeMultiSet)0.000.000.00±3.88%

TreeMultiSet (side-by-side)​

Comparison table. The main table above is TreeMultiSet only. Native is - when there is no apples-to-apples equivalent in this benchmark.

Test CaseDST (ms)Native (ms)C++ (ms)js-sdsl (ms)
1M add (TreeMultiSet expanded iteration)217.73-752.00-
1M has-only (TreeMultiSet)67.67-756.00-
1M count-only (TreeMultiSet)55.74-1332.00-
1M build+has (TreeMultiSet)260.84-1406.00-
1M build+count (TreeMultiSet)267.81-1909.00-
100K delete-one (TreeMultiSet)217.76---
100K setCount (TreeMultiSet)214.66---
1M expanded iteration (TreeMultiSet)54.41---
1M entries view (TreeMultiSet)15.67---
1M size property (TreeMultiSet)0.00---
1M distinctSize property (TreeMultiSet)0.00---

TreeMultiMap​

Test CaseAvg (ms)Min (ms)Max (ms)Stability
1M add (TreeMultiMap bucketed)366.19346.31454.65±5.51%
1M has-only (TreeMultiMap)35.3734.9436.94±0.39%
1M get-only (TreeMultiMap)58.3756.0573.86±1.37%
1M count-only (TreeMultiMap)105.3494.16124.54±2.71%
1M build+has (TreeMultiMap)396.87373.62538.68±8.08%
1M build+get (TreeMultiMap)416.59412.46424.84±0.62%
100K hasEntry (TreeMultiMap Object.is)375.85346.85396.95±2.39%
100K deleteValue (TreeMultiMap Object.is)411.69388.10577.77±9.06%
100K firstEntry/lastEntry (TreeMultiMap)0.00--±0%
100K ceilingEntry/floorEntry (TreeMultiMap)0.00--±0%
1M bucket iteration (TreeMultiMap)22.5521.9125.20±0.68%
1M flatEntries iteration (TreeMultiMap)106.47104.33110.52±0.6%
1M size property (TreeMultiMap)0.000.000.00±4.08%
1M totalSize property (TreeMultiMap)21.7421.0925.40±0.8%

TreeMultiMap (side-by-side)​

Comparison table. The main table above is TreeMultiMap only. Native is - when there is no apples-to-apples equivalent in this benchmark.

Test CaseDST (ms)Native (ms)C++ (ms)js-sdsl (ms)
1M add (TreeMultiMap bucketed)366.19-731.00-
1M has-only (TreeMultiMap)35.37-833.00-
1M get-only (TreeMultiMap)58.37-1553.00-
1M count-only (TreeMultiMap)105.34-1548.00-
1M build+has (TreeMultiMap)396.87-1519.00-
1M build+get (TreeMultiMap)416.59-2263.00-
100K hasEntry (TreeMultiMap Object.is)375.85---
100K deleteValue (TreeMultiMap Object.is)411.69---
100K firstEntry/lastEntry (TreeMultiMap)0.00---
100K ceilingEntry/floorEntry (TreeMultiMap)0.00---
1M bucket iteration (TreeMultiMap)22.55-109.00-
1M flatEntries iteration (TreeMultiMap)106.47-109.00-
1M size property (TreeMultiMap)0.00---
1M totalSize property (TreeMultiMap)21.74---

RedBlackTree​

Test CaseAvg (ms)Min (ms)Max (ms)Stability
1M get99.2482.27109.67±16.59%
200K rangeSearch SEQ1365.151251.751491.01±9.18%
200K rangeSearch RAND1565.261528.891613.47±2.69%
1M upd SEQ84.7582.2686.85±3.10%
1M upd RAND113.72112.51116.12±1.70%
1M ins SEQ535.64459.83795.68±33.88%
1M ins RAND989.88973.811001.58±1.43%
1M keys-only4.222.715.81±41.71%

RedBlackTree (side-by-side)​

Comparison table. The main table above is RedBlackTree only. Native is - when there is no apples-to-apples equivalent in this benchmark.

Test CaseDST (ms)DST classic (ms)Native (ms)C++ (ms)js-sdsl (ms)
1M get99.24304.72-52.97-
200K rangeSearch SEQ1365.15----
200K rangeSearch RAND1565.26----
1M upd SEQ84.75302.03-68.43-
1M upd RAND113.72422.53-158.14-
1M ins SEQ535.64211.38-162.72-
1M ins RAND989.88882.76-483.56-
1M keys-only4.22--0.09-

BST​

Test CaseAvg (ms)Min (ms)Max (ms)Stability
10K add randomly5.505.115.93±0.6%
10K add & delete randomly10.019.7510.79±0.4%
10K addMany11.6210.0068.37±15.54%
10K get10.6510.3511.67±0.48%

BST (side-by-side)​

Comparison table. The main table above is BST only. Native is - when there is no apples-to-apples equivalent in this benchmark.

Test CaseDST (ms)Native (ms)C++ (ms)js-sdsl (ms)
10K add randomly5.50---
10K add & delete randomly10.01---
10K addMany11.62---
10K get10.65---

BinaryTree​

Test CaseAvg (ms)Min (ms)Max (ms)Stability
1K add randomly9.779.5210.28±0.36%
1K add & delete randomly10.059.6711.34±0.69%
1K addMany10.799.2084.26±19.64%
1K get9.649.1512.52±1.33%
1K has9.509.2011.91±0.76%
1K dfs92.8790.4696.24±0.62%
1K bfs37.3436.1842.30±0.7%
1K morris37.4936.2939.54±0.51%

BinaryTree (side-by-side)​

Comparison table. The main table above is BinaryTree only. Native is - when there is no apples-to-apples equivalent in this benchmark.

Test CaseDST (ms)Native (ms)C++ (ms)js-sdsl (ms)
1K add randomly9.77---
1K add & delete randomly10.05---
1K addMany10.79---
1K get9.64---
1K has9.50---
1K dfs92.87---
1K bfs37.34---
1K morris37.49---

HashMap​

Test CaseAvg (ms)Min (ms)Max (ms)Stability
1M set146.1784.97644.99±33.94%
1M set & get141.88106.42178.02±6.1%
1M ObjKey set & get223.16210.45300.73±5.48%

HashMap (side-by-side)​

Comparison table. The main table above is HashMap only. Native is - when there is no apples-to-apples equivalent in this benchmark.

Test CaseDST (ms)Native (ms)C++ (ms)js-sdsl (ms)
1M set146.17144.8376.2694.16
1M set & get141.88200.4775.2567.16
1M ObjKey set & get223.16206.6284.40382.79

Trie​

Test CaseAvg (ms)Min (ms)Max (ms)Stability
100K add141.1078.571348.32±65.27%
100K getWords57.1652.5863.12±1.37%

Trie (side-by-side)​

Comparison table. The main table above is Trie only. Native is - when there is no apples-to-apples equivalent in this benchmark.

Test CaseDST (ms)Native (ms)C++ (ms)js-sdsl (ms)
100K add141.10---
100K getWords57.16---

DirectedGraph​

Test CaseAvg (ms)Min (ms)Max (ms)Stability
1K addVertex0.050.050.05±0.43%
1K addEdge0.00--±0%
1K getVertex37.5436.0538.86±0.39%
1K getEdge74.4872.6077.63±0.44%
tarjan0.380.340.42±0.93%
topologicalSort0.240.230.26±0.51%

DirectedGraph (side-by-side)​

Comparison table. The main table above is DirectedGraph only. Native is - when there is no apples-to-apples equivalent in this benchmark.

Test CaseDST (ms)Native (ms)C++ (ms)js-sdsl (ms)
1K addVertex0.05---
1K addEdge0.00---
1K getVertex37.54---
1K getEdge74.48---
tarjan0.38---
topologicalSort0.24---

Stack​

Test CaseAvg (ms)Min (ms)Max (ms)Stability
1M push46.3831.28258.38±26.06%
1M push & pop34.5927.52121.56±14.83%

Stack (side-by-side)​

Comparison table. The main table above is Stack only. Native is - when there is no apples-to-apples equivalent in this benchmark.

Test CaseDST (ms)Native (ms)C++ (ms)js-sdsl (ms)
1M push46.3830.281.6532.38
1M push & pop34.5934.532.6234.45

red-black-tree-cjs​

Test CaseAvg (ms)Min (ms)Max (ms)Stability
1M get97.5775.66115.14±22.94%
1M upd SEQ85.7678.9692.92±8.16%
1M upd RAND113.48101.84120.90±7.77%
1M ins SEQ493.45436.86670.44±25.42%
1M ins RAND1023.19976.561094.17±5.36%
1M keys-only4.222.715.90±41.83%

red-black-tree-cjs (side-by-side)​

Comparison table. The main table above is red-black-tree-cjs only. Native is - when there is no apples-to-apples equivalent in this benchmark.

Test CaseDST (ms)Native (ms)C++ (ms)js-sdsl (ms)
1M get97.57---
1M upd SEQ85.76---
1M upd RAND113.48---
1M ins SEQ493.45---
1M ins RAND1023.19---
1M keys-only4.22---

Real-World Scenarios​

Scenario 1: Message Queue Processing​

Problem: Process 100,000 messages in a queue.

// ❌ Array.shift() approach
const queue = [];
for (let msg of incomingMessages) queue.push(msg);
for (let i = 0; i < 100000; i++) {
  const msg = queue.shift();  // O(n) each time!
  processMessage(msg);
}
// Total: 100,000 * O(n) = O(n²)
// Time: ~2829ms for 100K items
// ✅ Deque approach
import { Deque } from 'data-structure-typed';

const deque = new Deque();
for (let msg of incomingMessages) deque.push(msg);
for (let i = 0; i < 100000; i++) {
  const msg = deque.shift();  // O(1)!
  processMessage(msg);
}
// Total: 100,000 * O(1) = O(n)
// Time: ~5.83ms for 100K items

// 484x faster!

Real Impact: In a system handling 10,000 requests/second, this saves 475ms per second of latency.

Scenario 2: Leaderboard Ranking​

Problem: Maintain top 100 players with constantly changing scores.

// ❌ Array approach
const players = [];

function updateScore(playerId, newScore) {
  const idx = players.findIndex(p => p.id === playerId);
  players[idx].score = newScore;
  players.sort((a, b) => b.score - a.score);  // O(n log n) each time!
}

// After 1000 updates: 1000 * O(n log n) = O(n² log n)
// Time: ~2500ms for maintaining ranking of 100 players
// ✅ RedBlackTree approach
import { RedBlackTree } from 'data-structure-typed';

const leaderboard = new RedBlackTree<number, number>();

function updateScore(playerId, newScore) {
  // Keyed by playerId: updates are a single O(log n) set.
  // (If you need to *rank by score*, use score as (part of) the key and maintain a playerId→score index.)
  leaderboard.set(playerId, newScore);
}

// After 1000 updates: 1000 * O(log n) = O(n log n)
// Time: ~8ms for 1000 updates on 100 players (measured in PERFORMANCE.md)

// ~312x faster than sorting on every update

Real Impact: Live leaderboards update instantly instead of lagging.

Scenario 3: Task Scheduling by Priority​

Problem: Execute tasks in priority order with 10K pending tasks.

// ❌ Manual priority handling
const tasks = [];

function addTask(task) {
  tasks.push(task);
  tasks.sort((a, b) => b.priority - a.priority);  // O(n log n)
}

function nextTask() {
  return tasks.shift();  // O(n)
}

// Adding 10K tasks: 10K * O(n log n) = O(n² log n)
// Time: ~3200ms
// ✅ PriorityQueue approach
import { MaxPriorityQueue } from 'data-structure-typed';

const pq = new MaxPriorityQueue();

function addTask(task) {
  pq.add(task);  // O(log n)
}

function nextTask() {
  return pq.poll();  // O(log n)
}

// Adding 10K tasks: 10K * O(log n) = O(n log n)
// Time: ~45ms

// 71x faster!

Detailed Benchmarks​

Deque vs Array Performance​

OperationArrayDequeSpeed-up
100K shifts2829ms5.83ms485x
100K unshifts2847ms6.12ms465x
100K operations2900ms7.45ms390x

Sorting Performance​

Data SizeArray.sortRedBlackTreeSpeed-up
1K items0.8ms3.2ms*0.25x (sort faster)
10K items12ms18ms**~0.66x
100K items150ms165ms**~0.9x
1M items1800ms1950ms**~0.92x

*First time - not repeated sorts **Maintains sorted order throughout

Key Insight: For repeated operations (updates with resorts), RBTree is much faster:

ScenarioArrayRBTreeSpeed-up
Insert 1K, sort once2ms5ms0.4x
Insert 1K, resort 100x200ms5ms40x
Insert 100K, resort 1000x20000ms65ms308x

Search Performance​

Structure1K items10K items100K items
Array (linear)0.5ms5ms50ms
BST (balanced)0.01ms0.013ms0.015ms
RedBlackTree0.01ms0.013ms0.015ms
HashMap0.001ms0.001ms0.001ms

Memory Usage​

Data Structure1K items10K items100K items1M items
Array39 KB242 KB2,706 KB21,519 KB
Queue38 KB248 KB2,712 KB21,527 KB
Deque53 KB147 KB1,341 KB10,717 KB
SinglyLinkedList60 KB425 KB3,947 KB39,100 KB
DoublyLinkedList60 KB502 KB4,726 KB46,909 KB
Stack42 KB240 KB2,709 KB21,521 KB
Heap35 KB250 KB2,716 KB21,530 KB
PriorityQueue39 KB245 KB2,711 KB21,524 KB
Trie526 KB3,040 KB29,160 KB270,733 KB
RedBlackTree570 KB1,069 KB8,765 KB86,035 KB
TreeCounter553 KB1,134 KB11,099 KB91,415 KB
TreeMultiMap2,069 KB4,836 KB32,828 KB208,619 KB

C++ vs JavaScript Data Structure Memory Usage Comparison (1M Elements)​

Data StructureC++JavaScriptMultipleEvaluation
Array4–8 MB21.01 MB2.75×–5.51×JavaScript uses significantly more memory due to object model and GC overhead
Queue8–24 MB21.02 MB0.92×–2.76×Memory usage depends heavily on the C++ implementation strategy
Deque8–24 MB10.47 MB0.46×–1.37×JavaScript implementation is relatively memory-efficient in this case
SinglyLinkedList24–40 MB38.18 MB1.00×–1.67×Similar memory footprint; both suffer from per-node allocation overhead
DoublyLinkedList32–56 MB45.81 MB0.86×–1.50×Comparable memory usage; allocator overhead dominates in both languages
Stack4–8 MB21.02 MB2.75×–5.51×JavaScript stacks are much heavier than C++ vector-based stacks
Heap4–8 MB21.03 MB2.76×–5.51×JavaScript heap implementations incur substantial runtime overhead
PriorityQueue4–8 MB21.02 MB2.76×–5.51×Similar to Heap; JavaScript pays extra metadata and GC costs
Trie32–160 MB264.39 MB1.73×–8.66×Highly implementation-dependent; JavaScript object-based tries are very memory-intensive
RedBlackTree48–80 MB84.02 MB1.10×–1.84×JavaScript trees are larger, but the gap is moderate compared to arrays
TreeCounter56–88 MB89.27 MB1.06×–1.67×Additional per-node bookkeeping increases JavaScript memory usage
TreeMultiMap56–96 MB203.73 MB2.23×–3.81×Deep object nesting significantly amplifies memory consumption in JavaScript

When to Use What​

Decision Matrix​

Need...Use...ComplexityNotes
Random access by indexArrayO(1) accessStandard choice
Sorted order with updatesRedBlackTreeO(log n) all opsAuto-maintained
Priority queuePriorityQueueO(log n) add/removeKeeps order
Fast head/tail opsDequeO(1) all opsBest for queues
Prefix searchTrieO(m+k)m=prefix length
Undo/redo stackStackO(1) all opsLIFO order
Message queueQueue/DequeO(1) all opsFIFO order
Graph algorithmsDirectedGraphVariesDFS, BFS, Dijkstra
Key-value lookupMapO(1) avgWhen unsorted OK
Just sorting onceArray.sort()O(n log n)One-time cost OK

Quick Decision Guide​

Need frequent head/tail operations?
  YES → Deque (O(1) shift/unshift/push/pop)
  NO  → Next

Need sorted + fast lookup?
  YES → RedBlackTree (O(log n) guaranteed)
  NO  → Next

Need highest/lowest priority?
  YES → Heap/PriorityQueue (O(log n) add/remove)
  NO  → Next

Need prefix/text matching?
  YES → Trie (O(m+k) where m=prefix)
  NO  → Next

Need graph operations?
  YES → DirectedGraph/UndirectedGraph
  NO  → Use Array (simplest case)

Optimization Tips​

Tip 1: Batch Operations​

// ❌ Slow: Sorting after each insert
const tree = new RedBlackTree();
for (const item of items) {
  tree.set(item.id, item);  // Tree rebalances each time
}
// ✅ Fast: Build in bulk
const tree = new RedBlackTree(items);
// Single rebalancing pass

// Often faster for large datasets (fewer per-insert balancing steps). Measure on your workload.

Tip 2: Use Right Structure Early​

// ❌ Wrong: Start with Array, convert later
const data = [];
for (const item of input) data.push(item);
const sorted = [...new RedBlackTree(data).keys()];
// ✅ Right: Use correct structure immediately
const tree = new RedBlackTree(input);
const sorted = [...tree.keys()];

// Benefit: No conversion overhead

Tip 3: Chain Operations​

// ❌ Slow: Converting to Array loses benefits
const tree = new RedBlackTree(data);
const result = tree.toArray()
  .filter(x => x > 5)
  .map(x => x * 2);
// ✅ Fast: Stay on tree
const result = tree
  .filter((v => (v ?? 0) > 5)
    .map(((v, k) => [k, (x ?? 0) * 2]);

// Benefit: Maintains structure type throughout

Tip 4: V8 JIT Warm-up​

// First calls are interpreted (slow)
// Subsequent calls are JIT-compiled (fast)

const tree = new RedBlackTree();

// First 100 inserts: Interpreted, slower
// Next 900 inserts: JIT-compiled (typically faster)

// Strategy: Do warm-up before timing
for (let i = 0; i < 1000; i++) tree.set(i, i);
// Now tree is warm and fast for benchmarks

Tip 5: Choose Right Comparator​

// ❌ Slow: Complex comparator
const tree = new RedBlackTree((a, b) => {
  if (a.category !== b.category) {
    return a.category.localeCompare(b.category);
  }
  return a.priority - b.priority;
});
// ✅ Fast: Simple comparator
const tree = new RedBlackTree([], { comparator: (a, b) => a - b)
}
;

// Why: V8 can inline simple comparators

Benchmark Summary Table​

Operations per Second​

OperationArrayDequeTreeHeap
1K shifts353/sec171K/sec--
1K inserts625/sec625/sec10K/sec8K/sec
1K searches2K/sec-100K/sec1K/sec
1K sorts1/sec-1000/sec*-

*Maintains sorted order

Conclusion​

When to Optimize​

  1. Profile first: Don't optimize without data
  2. Hot paths only: Focus on frequently-called code
  3. Right structure matters: large speedups are possible (see the measured scenarios above)
  4. Small datasets: Array usually fine
  5. Large datasets: Structure choice critical

Performance Hierarchy​

Array.sort() ← Simple, once per session
RedBlackTree ← Sorted + frequent updates
Deque ← Frequent head/tail ops
Heap ← Priority matters
Trie ← Prefix search
HashMap/Map ← Unsorted key-value lookup

Need examples? See GUIDES.md.

Understand why? Read ARCHITECTURE.md.