Pixie
Loading...
Searching...
No Matches
Trees

This page summarizes benchmarks for tree implementation: BP, DFUDS, LOUDS and reference implementations.

tree_dfs_benchmarks contains the dfs and dfs_children families. tree_path_benchmarks contains random_path and random_path_children. Each family includes BP, DFUDS, and LOUDS in optimized (*_best) and direct (*_direct) modes, plus adjacency-list and pointer references in BFS and preorder layouts. Names start with the workload, for example dfs/bp_best/tree_size:1024.

To run one family at one size after building:

taskset -c 0 build/benchmarks/tree_dfs_benchmarks \
--benchmark_filter='^dfs/[^/]+/tree_size:1024$'
taskset -c 0 build/benchmarks/tree_path_benchmarks \
--benchmark_filter='^random_path_children/[^/]+/tree_size:1024$'

The collector accepts --workload dfs, --workload path, or --workload all (the default). --succinct-mode both collects optimized and direct modes in one dataset. It runs each implementation and size in a separate process for each binary, so large reference fixtures are released between groups.

Scan/replay, conversion, and prepared-tree diagnostics are available through the optional tree_experimental_benchmarks target.

Machine

AMD Ryzen 7 8845HS (8 cores, 16 threads, 16 MiB L3), 15 GiB RAM, WSL2 (Linux 6.6.87.2-microsoft-standard-WSL2). GCC 13.3, C++20, -O3 -DNDEBUG -march=native; measurements pinned to CPU 0. Results captured October 30, 2026, at commit 8e72c47, after the ownership refactor, before the subsequent owning-encoding change. These graphs retain that measured revision. The current API takes a combined cache/scratch budget through TreeTraversalContext(tree, byte_limit); trees now own their encodings by default.

Implementations and inputs

Random recursive trees, seed 42. All measurements cover every even power from \(2^{10}\) through \(2^{26}\), with 32 KiB and 512 KiB cache budgets for succinct trees.

Implementation Representation and navigation Space
BP Balanced parentheses, RmMBTree with compressed rank/select \(2n\) bits + navigation index + cache
DFUDS Depth-first unary degree sequence, RmMBTree with compressed rank/select \(2n-1\) bits + navigation index + cache
LOUDS Level-order unary degree sequence, compressed rank/select \(2n-1\) bits + navigation index + cache
Vectors One adjacency vector per node, storing parent followed by children \(n\) instances of std::vector<size_t> with parent + children entries, approximately \(40n\) bytes on this machine
Pointers One contiguous array of first-child, next-sibling and parent pointers \(3n\) pointers, approximately \(24n\) bytes on this machine

The reference implementations are measured in both BFS and preorder numbering, succinct representation use their native numbering and bounded cache.

Measurement

  • DFS: traverse the whole tree, consuming preorder entry events and a return event for each nonleaf after its children.
  • DFS + child inspection: also enumerate every immediate child before descending.
  • Root-to-leaf path: start from root, choose a random child at each level until reaching a leaf.
  • Path + child inspection: also enumerate every immediate child along the path.
  • Construction: build from prepared input (including indexes and cache), and full setup including input generation and conversion/reordering.
  • Memory usage: bytes/node including the representation, indexes, cache and reserved traversal scratch; excludes allocator metadata and construction scratch.

Traversal timings are median CPU times over five repetitions; construction timings are median wall times over three fresh-process repetitions. Both cache sizes share each graph: dotted, hollow-marker curves denote 32 KiB; solid colored curves denote 512 KiB. References are shown once. All succinct curves use the current runtime-adaptive configuration.

Prepared input is a bitvector for succinct trees and an adjacency list for references. Full setup generates BP and converts it to DFUDS/LOUDS for succinct trees; references use the ordinary adjacency generator and BFS/preorder reordering. These timings compare the current fixture pipelines, not a common input format. Final-object destruction is excluded from construction timing.

Reproduction

Run from the repository root with CMake and Python with Matplotlib:

cmake --preset benchmarks
cmake --build --preset benchmarks --target tree_dfs_benchmarks tree_path_benchmarks -j 2
out=build/tree-reproduction
mkdir -p "$out"
python3 scripts/benchmark_trees.py --succinct-mode best --scope succinct \
--cache-bytes 524288 --exponents 10 12 14 16 18 20 22 24 26 --random-interleaving \
--repetitions 5 --min-time 0.2 --warmup 0.1 --output-dir "$out/512"
python3 scripts/benchmark_trees.py --succinct-mode best --scope succinct \
--cache-bytes 32768 --exponents 10 12 14 16 18 20 22 24 26 --random-interleaving \
--repetitions 5 --min-time 0.2 --warmup 0.1 --output-dir "$out/32"
python3 scripts/benchmark_trees.py --scope references \
--exponents 10 12 14 16 18 20 22 24 26 --random-interleaving \
--repetitions 5 --min-time 0.2 --warmup 0.1 --output-dir "$out/references"
c++ -O3 -DNDEBUG -march=native -std=c++20 -Wall -Wextra -Werror -Iinclude \
src/benchmarks/tree_construction_probe.cpp -o "$out/construction-probe"
python3 scripts/benchmark_tree_construction.py --binary "$out/construction-probe" \
--construction-mode consume --output-dir "$out/construction" --exponents 10 12 14 16 18 20 22 24 26
python3 scripts/plot_tree_docs.py --reference "$out/references/combined.json" \
--cache32 "$out/32/combined.json" --cache512 "$out/512/combined.json" \
--construction "$out/construction/results.json" --output-dir "$out/graphs"

Use --construction-mode copy in a separate output directory to include copying prepared encoding words in construction timing. The consuming mode prepares aligned storage before construction, and includes that preparation in full setup.

Results

DFS at 32 KiB and 512 KiB

DFS with child inspection

Root-to-leaf paths

Paths with child inspection

Construction from prepared input and full setup

Memory usage including reserved traversal scratch