![]() |
Pixie
|
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:
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.
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.
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.
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.
Run from the repository root with CMake and Python with Matplotlib:
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.