Performance
Time complexity for every public method and guidance on what to watch for.
Notation
The tables below use these shorthand variables:
| Symbol | Meaning |
|---|---|
| N | Total log entries |
| S | Number of unique snapshots |
| H_n | Number of log entries that mutated a given node |
| H_e | Number of log entries that mutated a given edge |
| E | Total unique edges ever created |
| M | Mutations per entry |
| K | Entries between two cursor positions |
| R | Results returned |
Iterator methods (liveNodes, liveEdges, getNeighbors, etc.) return in O(1) — the cost of iteration is paid per item by the caller.
Current-state reads
All O(1) Map/Set lookups.
| Method | Time |
|---|---|
hasNode(id) | O(1) |
getNode(id) | O(1) |
hasEdge(id) | O(1) |
getEdge(id) | O(1) |
getEdgesForNode(id) | O(1) |
degree(id) | O(1) |
inDegree(id) | O(degree) |
outDegree(id) | O(degree) |
liveNodes() | O(1) to obtain iterator |
liveEdges() | O(1) to obtain iterator |
getNeighbors(id) | O(1) to obtain iterator |
inNeighbors(id) | O(1) to obtain iterator |
outNeighbors(id) | O(1) to obtain iterator |
nodeCount | O(1) |
edgeCount | O(1) |
entryCount | O(1) |
currentSnapshot | O(1) |
Historical reads
Point-in-time queries without moving the cursor.
| Method | Time | Notes |
|---|---|---|
getNodeAt(id, snapshot) | O(H_n) | Scans only entries that touched this node |
getEdgeAt(id, snapshot) | O(H_e) | Scans only entries that touched this edge |
getEdgesForNodeAt(id, snapshot) | O(E × H_e) | Scans all edge histories — see warning below |
getNodeAt scales with mutation frequency, not graph size
getNodeAt only scans entries that touched that specific node. A node set once and never changed is cheap regardless of how large the graph is. A node updated thousands of times becomes slower proportional to its own history depth.
getEdgesForNodeAt is slow on large graphs
getEdgesForNodeAt must scan every edge's full history to check whether it was alive and connected at the target snapshot. For graphs with many edges that mutate frequently, a single call can be expensive. If you need to call this repeatedly, use seekTo(snapshot) followed by getEdgesForNode(id) instead — the seek is O(K × M) and the read is O(1).
Writes
| Method | Time | Notes |
|---|---|---|
append(entry) | O(M) | Cursor must be at head |
ingest(entries[]) | O(N × M) | Single diff across the whole batch |
Time travel
| Method | Time |
|---|---|
advance(snapshot) | O(K × M) |
rewind(snapshot) | O(K × M) |
seekTo(snapshot) | O(K × M) |
Cost scales with the number of mutations between the current and target position, not the number of snapshots.
Log queries
| Method | Time | Notes |
|---|---|---|
getSnapshotIds() | O(N) | Single pass |
getEntriesBySnapshot(snapshot) | O(log N + R) | Binary search then scan |
getEntriesBetween(from, to) | O(log N + R) | Binary search then scan |
getEntriesTouchingNode(id) | O(H_n) | Index lookup |
getEntriesTouchingEdge(id) | O(H_e) | Index lookup |
getEventsAt(snapshot) | O(log N + R) | Binary search then scan |
getNodeHistory(id) | O(H_n) | Index lookup |
Serialization
| Method | Time | Notes |
|---|---|---|
export() | O(N) | Shallow-copies the entries array |
import(data) | O(N × M) | Full log replay to rebuild state and indexes |
Running the benchmarks
npm run benchRuns the benchmark suite at 1K, 10K, and 100K scales and prints ops/sec for each scenario.