Skip to content

PERFORMANCE.md

Latest commit

 

History

History
828 lines (633 loc) · 31.3 KB

PERFORMANCE.md

File metadata and controls

828 lines (633 loc) · 31.3 KB

PERFORMANCE: Benchmarks & Comparisons

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

Structure Access Search Insert Delete Best For
Array O(1) O(n) O(n) O(n) Random access
LinkedList O(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
BST O(log n) O(log n) O(log n) O(log n) Sorted if balanced
RedBlackTree O(log n) O(log n) O(log n) O(log n) Guaranteed sorted
AVL Tree O(log n) O(log n) O(log n) O(log n) Max search speed
Heap O(n) O(n) O(log n) O(log n) Priority queue
Trie N/A O(m) O(m) O(m) Prefix search

Benchmark

Queue

Test Case Avg (ms) Min (ms) Max (ms) Stability
1M push 26.93 24.41 51.97 ±4.28%
100K push & shift 3.45 2.72 15.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 Case DST (ms) Native (ms) C++ (ms) js-sdsl (ms)
1M push 26.93 23.83 1.70 27.59
100K push & shift 3.45 1152.77 0.20 2.71

Deque

Test Case Avg (ms) Min (ms) Max (ms) Stability
1M push 9.77 6.27 21.63 ±9.28%
1M push & pop 14.75 11.80 31.16 ±5.06%
1M push & shift 14.61 13.31 40.42 ±5.25%
100K push & shift 1.29 1.19 3.37 ±3.91%
100K unshift & shift 1.26 1.14 2.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 Case DST (ms) Native (ms) C++ (ms) js-sdsl (ms)
1M push 9.77 26.81 1.76 7.79
1M push & pop 14.75 27.96 2.20 12.34
1M push & shift 14.61 - 1.94 -
100K push & shift 1.29 1243.77 0.19 1.17
100K unshift & shift 1.26 1867.28 0.19 1.17

DoublyLinkedList

Test Case Avg (ms) Min (ms) Max (ms) Stability
100k push 5.70 4.80 7.27 ±1.57%
100k unshift 5.57 4.63 13.65 ±5.7%
100k unshift & shift 4.04 3.87 5.34 ±1.3%
100k addAt(mid) 1865.99 1778.94 1992.65 ±5.43%
100k addBefore (cursor) 6.81 5.32 17.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 Case DST (ms) Native (ms) C++ (ms) js-sdsl (ms)
100k push 5.70 2.40 5.70 1.90
100k unshift 5.57 884.06 5.85 1.52
100k unshift & shift 4.04 2050.71 5.74 1.89
100k addAt(mid) 1865.99 - 754.81 -
100k addBefore (cursor) 6.81 - 6.18 -

SinglyLinkedList

Test Case Avg (ms) Min (ms) Max (ms) Stability
100K unshift & shift 3.77 3.62 3.99 ±0.41%
10K unshift & shift 0.37 0.36 0.44 ±0.78%
10K addAt(mid) 18.61 17.61 25.55 ±1.66%
10K addBefore (cursor) 17.56 16.67 20.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 Case DST (ms) Native (ms) C++ (ms) js-sdsl (ms)
100K unshift & shift 3.77 1958.39 4.80 -
10K unshift & shift 0.37 6.26 0.47 -
10K addAt(mid) 18.61 - 5.77 -
10K addBefore (cursor) 17.56 - 0.53 -

PriorityQueue

Test Case Avg (ms) Min (ms) Max (ms) Stability
100K add 4.00 3.80 4.41 ±0.6%
100K add & poll 22.51 21.23 42.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 Case DST (ms) Native (ms) C++ (ms) js-sdsl (ms)
100K add 4.00 - 1.05 4.96
100K add & poll 22.51 - 4.53 22.97

TreeSet

Test Case Avg (ms) Min (ms) Max (ms) Stability
1M add 995.72 948.08 1124.92 ±6.28%
1M has 67.80 64.53 86.26 ±1.67%
100K rangeSearch 17.34 16.79 18.81 ±0.46%
100K navigable 118.65 117.95 119.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 Case DST (ms) DST classic (ms) Native (ms) C++ (ms) js-sdsl (ms)
1M add 995.72 807.88 - 462.00 677.58
1M has 67.80 747.62 - 444.00 655.62
100K rangeSearch 17.34 16.70 - - -
100K navigable 118.65 123.91 - - -

TreeMap

Test Case Avg (ms) Min (ms) Max (ms) Stability
1M set 978.72 934.59 1130.02 ±6.39%
1M get 127.82 123.10 133.96 ±1.2%
100K rangeSearch 38.17 34.80 100.14 ±6.97%
100K navigable 160.66 151.89 307.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 Case DST (ms) DST classic (ms) Native (ms) C++ (ms) js-sdsl (ms)
1M set 978.72 831.32 - 512.00 623.23
1M get 127.82 719.05 - 322.00 626.87
100K rangeSearch 38.17 34.42 - - -
100K navigable 160.66 213.76 - - -

TreeMultiSet

Test Case Avg (ms) Min (ms) Max (ms) Stability
1M add (TreeMultiSet expanded iteration) 217.73 191.17 319.78 ±8.07%
1M has-only (TreeMultiSet) 67.67 66.08 72.83 ±0.72%
1M count-only (TreeMultiSet) 55.74 53.94 57.60 ±0.49%
1M build+has (TreeMultiSet) 260.84 248.30 300.22 ±2.79%
1M build+count (TreeMultiSet) 267.81 242.77 339.53 ±5.97%
100K delete-one (TreeMultiSet) 217.76 201.92 254.80 ±2.97%
100K setCount (TreeMultiSet) 214.66 201.65 264.54 ±3.65%
1M expanded iteration (TreeMultiSet) 54.41 53.14 62.22 ±0.78%
1M entries view (TreeMultiSet) 15.67 14.81 17.19 ±0.72%
1M size property (TreeMultiSet) 0.00 0.00 0.00 ±3.47%
1M distinctSize property (TreeMultiSet) 0.00 0.00 0.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 Case DST (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 Case Avg (ms) Min (ms) Max (ms) Stability
1M add (TreeMultiMap bucketed) 366.19 346.31 454.65 ±5.51%
1M has-only (TreeMultiMap) 35.37 34.94 36.94 ±0.39%
1M get-only (TreeMultiMap) 58.37 56.05 73.86 ±1.37%
1M count-only (TreeMultiMap) 105.34 94.16 124.54 ±2.71%
1M build+has (TreeMultiMap) 396.87 373.62 538.68 ±8.08%
1M build+get (TreeMultiMap) 416.59 412.46 424.84 ±0.62%
100K hasEntry (TreeMultiMap Object.is) 375.85 346.85 396.95 ±2.39%
100K deleteValue (TreeMultiMap Object.is) 411.69 388.10 577.77 ±9.06%
100K firstEntry/lastEntry (TreeMultiMap) 0.00 - - ±0%
100K ceilingEntry/floorEntry (TreeMultiMap) 0.00 - - ±0%
1M bucket iteration (TreeMultiMap) 22.55 21.91 25.20 ±0.68%
1M flatEntries iteration (TreeMultiMap) 106.47 104.33 110.52 ±0.6%
1M size property (TreeMultiMap) 0.00 0.00 0.00 ±4.08%
1M totalSize property (TreeMultiMap) 21.74 21.09 25.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 Case DST (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 Case Avg (ms) Min (ms) Max (ms) Stability
1M get 99.24 82.27 109.67 ±16.59%
200K rangeSearch SEQ 1365.15 1251.75 1491.01 ±9.18%
200K rangeSearch RAND 1565.26 1528.89 1613.47 ±2.69%
1M upd SEQ 84.75 82.26 86.85 ±3.10%
1M upd RAND 113.72 112.51 116.12 ±1.70%
1M ins SEQ 535.64 459.83 795.68 ±33.88%
1M ins RAND 989.88 973.81 1001.58 ±1.43%
1M keys-only 4.22 2.71 5.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 Case DST (ms) DST classic (ms) Native (ms) C++ (ms) js-sdsl (ms)
1M get 99.24 304.72 - 52.97 -
200K rangeSearch SEQ 1365.15 - - - -
200K rangeSearch RAND 1565.26 - - - -
1M upd SEQ 84.75 302.03 - 68.43 -
1M upd RAND 113.72 422.53 - 158.14 -
1M ins SEQ 535.64 211.38 - 162.72 -
1M ins RAND 989.88 882.76 - 483.56 -
1M keys-only 4.22 - - 0.09 -

BST

Test Case Avg (ms) Min (ms) Max (ms) Stability
10K add randomly 5.50 5.11 5.93 ±0.6%
10K add & delete randomly 10.01 9.75 10.79 ±0.4%
10K addMany 11.62 10.00 68.37 ±15.54%
10K get 10.65 10.35 11.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 Case DST (ms) Native (ms) C++ (ms) js-sdsl (ms)
10K add randomly 5.50 - - -
10K add & delete randomly 10.01 - - -
10K addMany 11.62 - - -
10K get 10.65 - - -

BinaryTree

Test Case Avg (ms) Min (ms) Max (ms) Stability
1K add randomly 9.77 9.52 10.28 ±0.36%
1K add & delete randomly 10.05 9.67 11.34 ±0.69%
1K addMany 10.79 9.20 84.26 ±19.64%
1K get 9.64 9.15 12.52 ±1.33%
1K has 9.50 9.20 11.91 ±0.76%
1K dfs 92.87 90.46 96.24 ±0.62%
1K bfs 37.34 36.18 42.30 ±0.7%
1K morris 37.49 36.29 39.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 Case DST (ms) Native (ms) C++ (ms) js-sdsl (ms)
1K add randomly 9.77 - - -
1K add & delete randomly 10.05 - - -
1K addMany 10.79 - - -
1K get 9.64 - - -
1K has 9.50 - - -
1K dfs 92.87 - - -
1K bfs 37.34 - - -
1K morris 37.49 - - -

HashMap

Test Case Avg (ms) Min (ms) Max (ms) Stability
1M set 146.17 84.97 644.99 ±33.94%
1M set & get 141.88 106.42 178.02 ±6.1%
1M ObjKey set & get 223.16 210.45 300.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 Case DST (ms) Native (ms) C++ (ms) js-sdsl (ms)
1M set 146.17 144.83 76.26 94.16
1M set & get 141.88 200.47 75.25 67.16
1M ObjKey set & get 223.16 206.62 84.40 382.79

Trie

Test Case Avg (ms) Min (ms) Max (ms) Stability
100K add 141.10 78.57 1348.32 ±65.27%
100K getWords 57.16 52.58 63.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 Case DST (ms) Native (ms) C++ (ms) js-sdsl (ms)
100K add 141.10 - - -
100K getWords 57.16 - - -

DirectedGraph

Test Case Avg (ms) Min (ms) Max (ms) Stability
1K addVertex 0.05 0.05 0.05 ±0.43%
1K addEdge 0.00 - - ±0%
1K getVertex 37.54 36.05 38.86 ±0.39%
1K getEdge 74.48 72.60 77.63 ±0.44%
tarjan 0.38 0.34 0.42 ±0.93%
topologicalSort 0.24 0.23 0.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 Case DST (ms) Native (ms) C++ (ms) js-sdsl (ms)
1K addVertex 0.05 - - -
1K addEdge 0.00 - - -
1K getVertex 37.54 - - -
1K getEdge 74.48 - - -
tarjan 0.38 - - -
topologicalSort 0.24 - - -

Stack

Test Case Avg (ms) Min (ms) Max (ms) Stability
1M push 46.38 31.28 258.38 ±26.06%
1M push & pop 34.59 27.52 121.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 Case DST (ms) Native (ms) C++ (ms) js-sdsl (ms)
1M push 46.38 30.28 1.65 32.38
1M push & pop 34.59 34.53 2.62 34.45

red-black-tree-cjs

Test Case Avg (ms) Min (ms) Max (ms) Stability
1M get 97.57 75.66 115.14 ±22.94%
1M upd SEQ 85.76 78.96 92.92 ±8.16%
1M upd RAND 113.48 101.84 120.90 ±7.77%
1M ins SEQ 493.45 436.86 670.44 ±25.42%
1M ins RAND 1023.19 976.56 1094.17 ±5.36%
1M keys-only 4.22 2.71 5.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 Case DST (ms) Native (ms) C++ (ms) js-sdsl (ms)
1M get 97.57 - - -
1M upd SEQ 85.76 - - -
1M upd RAND 113.48 - - -
1M ins SEQ 493.45 - - -
1M ins RAND 1023.19 - - -
1M keys-only 4.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

Operation Array Deque Speed-up
100K shifts 2829ms 5.83ms 485x
100K unshifts 2847ms 6.12ms 465x
100K operations 2900ms 7.45ms 390x

Sorting Performance

Data Size Array.sort RedBlackTree Speed-up
1K items 0.8ms 3.2ms* 0.25x (sort faster)
10K items 12ms 18ms** ~0.66x
100K items 150ms 165ms** ~0.9x
1M items 1800ms 1950ms** ~0.92x

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

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

Scenario Array RBTree Speed-up
Insert 1K, sort once 2ms 5ms 0.4x
Insert 1K, resort 100x 200ms 5ms 40x
Insert 100K, resort 1000x 20000ms 65ms 308x

Search Performance

Structure 1K items 10K items 100K items
Array (linear) 0.5ms 5ms 50ms
BST (balanced) 0.01ms 0.013ms 0.015ms
RedBlackTree 0.01ms 0.013ms 0.015ms
HashMap 0.001ms 0.001ms 0.001ms

Memory Usage

Data Structure 1K items 10K items 100K items 1M items
Array 39 KB 242 KB 2,706 KB 21,519 KB
Queue 38 KB 248 KB 2,712 KB 21,527 KB
Deque 53 KB 147 KB 1,341 KB 10,717 KB
SinglyLinkedList 60 KB 425 KB 3,947 KB 39,100 KB
DoublyLinkedList 60 KB 502 KB 4,726 KB 46,909 KB
Stack 42 KB 240 KB 2,709 KB 21,521 KB
Heap 35 KB 250 KB 2,716 KB 21,530 KB
PriorityQueue 39 KB 245 KB 2,711 KB 21,524 KB
Trie 526 KB 3,040 KB 29,160 KB 270,733 KB
RedBlackTree 570 KB 1,069 KB 8,765 KB 86,035 KB
TreeCounter 553 KB 1,134 KB 11,099 KB 91,415 KB
TreeMultiMap 2,069 KB 4,836 KB 32,828 KB 208,619 KB

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

Data Structure C++ JavaScript Multiple Evaluation
Array 4–8 MB 21.01 MB 2.75×–5.51× JavaScript uses significantly more memory due to object model and GC overhead
Queue 8–24 MB 21.02 MB 0.92×–2.76× Memory usage depends heavily on the C++ implementation strategy
Deque 8–24 MB 10.47 MB 0.46×–1.37× JavaScript implementation is relatively memory-efficient in this case
SinglyLinkedList 24–40 MB 38.18 MB 1.00×–1.67× Similar memory footprint; both suffer from per-node allocation overhead
DoublyLinkedList 32–56 MB 45.81 MB 0.86×–1.50× Comparable memory usage; allocator overhead dominates in both languages
Stack 4–8 MB 21.02 MB 2.75×–5.51× JavaScript stacks are much heavier than C++ vector-based stacks
Heap 4–8 MB 21.03 MB 2.76×–5.51× JavaScript heap implementations incur substantial runtime overhead
PriorityQueue 4–8 MB 21.02 MB 2.76×–5.51× Similar to Heap; JavaScript pays extra metadata and GC costs
Trie 32–160 MB 264.39 MB 1.73×–8.66× Highly implementation-dependent; JavaScript object-based tries are very memory-intensive
RedBlackTree 48–80 MB 84.02 MB 1.10×–1.84× JavaScript trees are larger, but the gap is moderate compared to arrays
TreeCounter 56–88 MB 89.27 MB 1.06×–1.67× Additional per-node bookkeeping increases JavaScript memory usage
TreeMultiMap 56–96 MB 203.73 MB 2.23×–3.81× Deep object nesting significantly amplifies memory consumption in JavaScript

When to Use What

Decision Matrix

Need... Use... Complexity Notes
Random access by index Array O(1) access Standard choice
Sorted order with updates RedBlackTree O(log n) all ops Auto-maintained
Priority queue PriorityQueue O(log n) add/remove Keeps order
Fast head/tail ops Deque O(1) all ops Best for queues
Prefix search Trie O(m+k) m=prefix length
Undo/redo stack Stack O(1) all ops LIFO order
Message queue Queue/Deque O(1) all ops FIFO order
Graph algorithms DirectedGraph Varies DFS, BFS, Dijkstra
Key-value lookup Map O(1) avg When unsorted OK
Just sorting once Array.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

Operation Array Deque Tree Heap
1K shifts 353/sec 171K/sec - -
1K inserts 625/sec 625/sec 10K/sec 8K/sec
1K searches 2K/sec - 100K/sec 1K/sec
1K sorts 1/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.