Benchmarks¶

The benchmark report for 0.3.0 (the API 1.0 is meant to freeze): speed and memory of every source, strategy and sink, a comparison with the usual "build the whole tree, then filter it" code, and the targets from SPEC §10 with a verdict each. How the model works and how to make a pipeline cheap is in Performance; this page is only measurements. The historical log of how the implementation got here (prototypes, rejected ideas) is benchmarks/RESULTS.md.

Summary¶

Medians, PHP 8.4, opcache on. "JIT off" is the default configuration of PHP; "JIT on" is opcache.jit=tracing. Balanced-300k is a balanced tree of 299,593 nodes, category-100k a random shop tree of 100,000 nodes. Every number has a range and a variance in the full matrix.

Streaming a generator of 1,111,111 rows (time includes generating the rows, about 370 ms of it, which is a stand-in for a database cursor) through Prune into iterate(): 603 ms with the JIT off, 388 ms with it on, in 1.1 MiB of memory (2.2 MiB with the JIT, which allocates for itself), the same as at 11,111 rows.

What to take from it:

• With the JIT off, reading a nested set costs 95 to 110 ns per node, Prune (90 % kept) 135 to 165 ns, KeepAncestors and Promote 165 to 190 ns. Building the nested array is the largest single cost of a typical pipeline.
• The JIT makes the library 1.2× to 1.75× faster on PHP 8.4 and 8.5 alike (geometric mean of the time ratio 0.57 to 0.84, see JIT effect); the biggest gains are on the strategies, the smallest on streaming, where generating the rows dominates.
• PHP 8.5 is within ±3 % of PHP 8.4 everywhere (comparison).

Targets from SPEC §10¶

The adjacency list in arbitrary order has to build an index before it can emit the first node, so its speed is that of the naive code (with the JIT on, KeepAncestors is 1.2× to 1.7× faster; Prune into a nested array stays at 0.7× to 1.3×). When you control the query, order it by lft or by path and use the nested set or pre-ordered source.

Environment¶

The machine was otherwise idle (no other benchmarks, tests or containers running; a desktop session was open). It is a laptop-class CPU, so absolute numbers on a server will differ; ratios between pipelines, and the memory figures, are what carries over.

Method¶

• Harness. phpbench, one process per iteration (a fresh PHP, so every iteration starts with a cold opcache and, with the JIT on, a cold JIT), --iterations=8, --retry-threshold=5 (phpbench repeats a variant until its rstdev is under 5 %). Revs and warm-up come from the attributes in benchmarks/*Bench.php: two revolutions with one warm-up revolution for the in-memory benchmarks, one revolution for streaming. The configurations ran one after another, never in parallel, 7.6 to 8.5 minutes each (see Reproduce).
• What is measured. Time per revolution (phpbench time-avg), reported as the median of the iterations with the relative standard deviation (rstdev) next to it. Peak memory: mem_peak, which includes the fixture (the input rows are built before the measurement and the peak is reset afterwards), and "own peak" = mem_peak − mem_final, the working memory of the subject itself without the input (its result is freed by the time mem_final is read).
• Fixtures. benchmarks/Support/Fixture.php builds deterministic trees and renders them in every input format; all rows are PHP arrays already in memory, so the numbers are the library's cost without a database. Shapes: balanced (branching 8, depth 5 and 6: 37,449 and 299,593 nodes), wide (1 root with 1,000 or 100,000 children), a deep chain (depth 10,000, which also shows there is no recursion limit), and random category trees (1,000 and 100,000 nodes). The 1k shapes run 100 passes per revolution (… x100; divide the time by 100) so that they stay well above timer noise.
• Predicates. hit matches about 10 % of the nodes (a search), visible about 90 % (hide unpublished; roots always visible).
• Matrix. Sources × shapes (SourceBench), strategies × shapes (StrategyBench, always from a nested set), sinks × shapes (SinkBench, always from a nested set), naive baseline × shapes (NaiveBaselineBench) and streaming × three sizes (StreamingBench). The three axes are measured separately, not as a full cross product: sources are compared through count(), strategies through count(), sinks with no strategy. KeepAncestorsToNestedArray and the naive pairs cover the combination that matters.
• Naive baseline. benchmarks/Support/Naive.php: build the full nested tree recursively (from adjacency rows, or from a nested set), then filter it recursively, with the same semantics as KeepAncestors or Prune. It is the code most projects write by hand. benchmarks/verify.php checks that every compared pair, the library and the baseline, produces identical output; run it before trusting any benchmark.
• Size cut. The in-memory shapes stop at about 300k nodes: the fixture is PHP arrays (about 240 MiB at 300k rows), the naive baseline needs 2× to 3× that again, and 1M-node fixtures would not fit the 2 GiB benchmark memory limit in every configuration. The 1.1M-node size exists where it matters, in the streaming benchmark (rows generated lazily, no fixture). Per-node costs are flat from 37k to 300k nodes, so the in-memory numbers extrapolate linearly (memory too, except for streaming, which stays constant).
• Not measured. A real database (query time dominates there; see Doctrine and Gedmo for what the bridge pushes into SQL), and sortSiblings(), MinMatches and the other stages, which have no benchmark yet.

Reproduce¶

make bench-report                                  # all four configurations, then rewrites the tables below

That is, for each of PHP 8.4 and 8.5 and off / on:

PHP_VERSION=8.4 docker compose run --rm php sh benchmarks/run-report.sh off var/bench-report/php8.4-jit-off.xml
PHP_VERSION=8.4 docker compose run --rm php sh benchmarks/run-report.sh on  var/bench-report/php8.4-jit-on.xml
PHP_VERSION=8.5 docker compose run --rm php sh benchmarks/run-report.sh off var/bench-report/php8.5-jit-off.xml
PHP_VERSION=8.5 docker compose run --rm php sh benchmarks/run-report.sh on  var/bench-report/php8.5-jit-on.xml
docker compose run --rm php php benchmarks/render-report.php var/bench-report docs/benchmarks.md
docker compose run --rm php php benchmarks/verify.php   # output equivalence of every compared pair

benchmarks/run-report.sh runs vendor/bin/phpbench run on SourceBench, StrategyBench, SinkBench, NaiveBaselineBench and StreamingBench with --iterations=8 --retry-threshold=5 and the PHP settings above, and benchmarks/render-report.php turns the dumps into the tables below. Run it alone on a quiet machine; a full make bench-report takes about 35 minutes. Only the block between the results markers is generated; the text around it is edited by hand when the environment changes.

Results¶

All tables in this section are generated from the four dumps of one run (2026-11-05). Cells read "median ±rstdev".

Run quality¶

Relative standard deviation (rstdev) of the iterations of each variant, per configuration. Each iteration is a fresh process; phpbench retried variants above 5 %.

Target 1: streaming memory does not grow with n¶

Rows come from a generator (balanced tree, branching 10), through the pipeline into iterate(). Peak memory of the process (mem_peak, maximum over all iterations and both PHP versions), JIT off / JIT on (the JIT's compiler allocates about 1.2 MiB of its own, independent of the tree):

Target 2: Prune over an array nested set, nodes per second¶

StrategyBench: nested set rows → Prune → count(); Prune 90 % keeps about 90 % of the nodes (the realistic "hide unpublished" filter), Prune 10 % about 10 %. Nodes per second counts every input row. Median of the iterations; the time table further down has the spread.

Targets 3 to 5: against the naive build-then-filter baseline¶

NaiveBaselineBench: same input rows, same output (checked by benchmarks/verify.php). Speed-up is naive time ÷ library time (above 1 means the library is faster); memory ratio is naive ÷ library own peak (mem_peak − mem_final).

Speed-up

Memory (naive own peak / library own peak, PHP and JIT make no difference; shown for PHP 8.4, JIT off)

JIT effect¶

Median time with the JIT on ÷ median time with it off, per class, as the geometric mean over all variants of at least 1 ms (below that, timer noise dominates). Below 1.00 the JIT helps.

PHP 8.4 compared with 8.5¶

Median time on 8.5 ÷ median time on 8.4 (geometric mean over variants of at least 1 ms). Below 1.00 means 8.5 is faster.

Full matrix¶

Time per revolution, "median ±rstdev". Variants named … x100 run 100 passes per revolution (divide by 100 for one pass). nodes/s and the memory columns are for PHP 8.4, JIT off; mem_peak includes the fixture, own peak is the subject's own working memory.

Sources¶

Each source read to the end through count(); the rows are plain arrays in memory. "own peak" is the working memory of the read.

Strategies¶

Nested set rows → strategy → count(). NoFilter is the source alone; Prune and ActiveTrailSingle are the realistic cases, PruneHit, ActiveTrailHit and Annotate stress cases (see the benchmark file).

Sinks¶

Nested set rows → sink. KeepAncestorsToNestedArray adds the strategy in front of the nested array sink.

Naive baseline¶

Naive* rows are the recursive build-the-whole-tree-then-filter code in benchmarks/Support/Naive.php; Library* rows the same result through the library.

Streaming from a generator¶

Rows generated lazily (time includes generating them; GeneratorOnly is that part alone). Sizes are the node counts of balanced trees with branching 10.