Skip to content

Performance Release Notes

Scope

This page preserves the results and reasoning from the performance work recorded in October 2026. The original working notes and raw JSONL benchmark output were kept under agent/ while the work was in progress. They are now summarized here so the repository keeps the durable conclusions without carrying a temporary experiment archive.

The measurements were taken on an Azure VM with 8 physical cores, 16 vCPUs, and 62 GB of RAM. Unless noted otherwise, runs used release builds, 8 threads, synthetic data generated by scripts/make_perf_data.py with seed 0, 256 bins, learning rate 0.1, depth 5, and one evaluation set. Timings vary by roughly 5-10% between runs.

Executive Summary

The main bottleneck was tree construction, not prediction or evaluation. In the original 1,000-iteration workload with 100,000 rows and 200 columns, tree building accounted for 93.3% of total time. The optimization work moved the largest serial sections into parallel execution, reduced repeated allocations and copies, and made binning parallel.

The recorded end-to-end results were:

Workload Before After Result
100 iterations, 1M x 200, 8 threads 52.7 s 26.1 s 2.0x faster
1,000 iterations, 100k x 200, default threads 80.8 s 37.2 s 2.2x faster
Tree time, 8 threads, 25k-250k rows baseline -39% to -81% substantially lower
Binning, 8 threads, 1M x 200 24.7 s 1.8 s 91-93% less
8-thread speedup over serial 1.0-3.1x 4.6-5.2x much better scaling

Every kept change was checked for byte-identical model output. The recorded Python test suite passed with 112 tests during the main optimization work and 121 tests during the histogram follow-up.

Tree-Building Optimizations

The following changes were measured and kept:

Change Recorded effect
Parallel split search 17-38% faster at 8 threads
Borrow gradients instead of copying 3-10% faster
Write histograms in place 15-33% faster at 8 threads
Parallel histogram subtraction Up to 28% faster at 8 threads
Parallel binning with one sort per column Binning 11-14x faster
Configurable num_threads Makes thread-count tuning explicit
Run parallel work on a pool thread 4-40% faster at 8 threads

The analysis found that histogram accumulation was only part of the problem. Split search, histogram subtraction, gradient/Hessian gathering, per-column histogram assembly, and row partitioning remained serial and dominated smaller or deeper trees. Parallelizing independent feature scans and per-column work improved scaling while preserving the existing tie-breaking behavior.

The recommended setting on the benchmark host was 8 threads, one per physical core. The default 16 threads was 2-18% slower at depth 5 and 25-66% slower at depth 8. This is workload and machine dependent; applications should measure on their own hosts before changing thread settings.

Histogram follow-up

Two additional changes were kept:

  • Skip histogram construction for children at max_depth, reducing tree time by 10-35% in the measured cases.
  • Remove the redundant cut_value field from Bin, reducing tree time by up to 21% on small nodes and deep trees.

The combined before/after measurements were:

Data Rows Setting Before After Change
w200 100k none 3.47 s 2.49 s -28.1%
w200 100k random80 3.21 s 2.30 s -28.3%
w200 100k GOSS 2.31 s 1.94 s -16.0%
w200 250k none 7.91 s 5.60 s -29.2%
w200 250k random80 7.13 s 5.18 s -27.4%
w200 250k GOSS 4.42 s 3.46 s -21.7%
w500 100k none 7.92 s 5.76 s -27.3%
w500 100k random80 7.20 s 4.98 s -30.9%
w500 100k GOSS 4.88 s 3.57 s -26.8%
w200-1m 1M none 26.74 s 19.53 s -27.0%
w200-1m 1M random80 24.10 s 18.35 s -23.8%
w200-1m 1M GOSS 15.35 s 12.92 s -15.8%

These are median total fit times for 100 iterations with one evaluation set. Evaluation logloss was identical before and after for these comparisons.

GOSS Sampling

Forust now supports Gradient-based One-Side Sampling (GOSS), following the LightGBM approach. GOSS keeps the rows with the largest gradients and samples from the remaining rows, scaling the retained small-gradient rows to keep split statistics close to unbiased. With the default top_rate=0.2 and other_rate=0.1, the first int(1 / learning_rate) trees use all rows as a warm-up.

Against random 80% row sampling (random80), fixed 100-iteration runs showed:

Data random80 GOSS Speedup
w200, 100k 3.21 s 2.31 s 1.39x
w200, 250k 7.13 s 4.42 s 1.61x
w500, 100k 7.20 s 4.88 s 1.48x
w200-1m, 1M 24.10 s 15.35 s 1.57x

Across these datasets, fixed-iteration GOSS logloss was within -0.55% to +0.19% of the random80 baseline. Early stopping was within +0.98% on w200 100k and -0.11% on w500 100k, but was +1.63% worse on w200 250k. That last case exceeded the recorded 1% tolerance and is an important caveat rather than a result to hide. The early-stopping runs usually reached the 1,000-tree cap, so they were not all fully converged comparisons.

GOSS-specific implementation measurements on 1M x 200 were:

Configuration Tree Row selection Subset copy Total
No sampling 220.5 ms - - 220.5 ms
GOSS, serial selection 111.1 ms 17.6 ms - 128.7 ms
GOSS plus contiguous row subset 89.2 ms 15.2 ms 11.6 ms 116.0 ms
GOSS plus parallel block selection 85.5 ms 4.8 ms 11.1 ms 101.4 ms

The subset tree output was byte-identical to the full-data tree output in the recorded checks. Parallel and serial GOSS block selection also produced identical models.

Model-Identical Follow-up

Four more changes, each in its own commit, keep trained trees and evaluation history byte-identical. perf_golden.py now also compares evaluation history and covers 15 configurations (adding a missing branch at depth 8, DepthWise with max_leaves, colsample_bytree and serial GOSS), and 120 random configurations were compared against the previous build.

Change What it does
Parallel gradients and hessians Each row is independent, so blocks of rows are computed in parallel.
Leaf rows for training predictions Rows a tree was fit on get the weight of the leaf the partition left them in, instead of walking the tree again. Sampled-out rows walk the tree on their bins.
Binned evaluation predictions Evaluation sets are binned once with the training cuts and trees are walked on u16 bins instead of f64 values.
Depth-wise trees grown a level at a time All nodes of a level search for splits together, then are partitioned and get child histograms together, instead of several parallel steps per node.

The training predictions rely on the partition matching prediction. The partition functions are only wrong when no row goes right, which a chosen split can't do with a positive min_leaf_weight; Tree::fit checks each split and falls back to predicting every row if one could be affected.

Per-iteration time of each section, 8 threads, baseline to final:

Case Gradients Training predictions Evaluation predictions Tree Whole iteration
100k, depth 5 0.8 to 0.3 ms 1.1 to 0.2 ms 0.4 to 0.2 ms 19.3 to 14.4 ms 23.9 to 17.7 ms
100k, depth 8 0.8 to 0.3 ms 3.1 to 0.3 ms 0.9 to 0.5 ms 68.0 to 46.1 ms 76.6 to 51.4 ms
250k, depth 5, GOSS 1.9 to 0.5 ms 2.3 to 1.9 ms 0.7 to 0.4 ms 18.3 to 14.6 ms 33.8 to 27.7 ms
1M, depth 5 7.7 to 1.4 ms 8.1 to 3.2 ms 2.2 to 1.1 ms 161.6 to 128.4 ms 251.9 to 207.1 ms
1M, depth 8 7.7 to 1.4 ms 31.7 to 4.9 ms 8.0 to 4.1 ms 458.7 to 350.7 ms 611.2 to 462.8 ms

Median total fit time with one evaluation set (5 interleaved rounds at 8 threads, 3 at the default 16 threads; 100 iterations at 100k and 250k rows, 60 at depth 8 or with the missing branch, 30 at 1M rows and 20 at 1M depth 8):

Case Before, 8 threads After, 8 threads Change Before, 16 threads After, 16 threads Change
100k, depth 5 2.53 s 2.00 s -21% 2.65 s 1.88 s -29%
100k, depth 8 4.52 s 3.12 s -31% 5.55 s 2.81 s -49%
25k, depth 8 2.04 s 1.39 s -32% 2.54 s 1.27 s -50%
250k, depth 5 5.61 s 4.58 s -18% 5.48 s 4.14 s -24%
250k, depth 5, GOSS 3.48 s 2.85 s -18% 3.50 s 2.69 s -23%
100k, depth 5, missing branch 1.91 s 1.43 s -25% 2.06 s 1.33 s -36%
100k, LossGuide, 32 leaves 1.52 s 1.38 s -9% 1.51 s 1.47 s -3%
1M, depth 5 7.43 s 6.50 s -12% 6.77 s 5.61 s -17%
1M, depth 8 12.02 s 9.48 s -21% 11.26 s 8.59 s -24%
1M, depth 5, GOSS 5.80 s 5.14 s -11% 5.15 s 4.43 s -14%

Level-at-a-time growth is most of the gain (3-31% on its own at 8 threads), largest for deep trees and many small nodes. The other three save 2-37 ms per iteration, mostly at 1M rows and depth 8. LossGuide still grows one node at a time, so it only gets those three.

With depth-wise growth, the default 16 threads is now 6-14% faster than 8 threads in these runs, where it used to be slower; LossGuide was still about 7% slower at 16 threads.

Rust API changes: Tree::fit returns the rows in each node (Option<TreeRows>), and Splitter::handle_split_info receives only the node's rows of the index.

Experiments That Were Not Kept

Several ideas were measured and rejected, and recording those results prevents repeating the same investigations:

  • Reusing histogram buffers was slower at depth 5: about 6% slower at 250k rows and 7% slower at 1M rows.
  • Reusing the per-column sums buffer was 6-30% slower in the tested cases.
  • u8 bins were 7-20% faster in the histogram-fill microbenchmark, but only apply when all columns fit within 255 bins. The default 256-bin layout needs u16, and the required generic plumbing was not justified by the measured end-to-end gain.
  • u32 row indices showed no useful microbenchmark gain.
  • Building small nodes serially was slower at every tested threshold.
  • A faster weighted pair sort gained about 2% but carried a small risk of changing last-digit cut values.

The remaining likely bottlenecks are row partitioning after each split, split evaluation for every bin and histogram accumulation. Rayon scheduling for many small deep-tree nodes was addressed for depth-wise growth by growing a level at a time (see above). These are candidates for future profiling, not claims of completed work.

Reproducing the Measurements

Synthetic datasets can be regenerated with:

python scripts/make_perf_data.py --out /tmp/forust-perf/w200 --rows 250000 --eval-rows 62500 --cols 200
python scripts/make_perf_data.py --out /tmp/forust-perf/w500 --rows 100000 --eval-rows 25000 --cols 500
python scripts/make_perf_data.py --out /tmp/forust-perf/w200-1m --rows 1000000 --eval-rows 250000 --cols 200

The benchmark helpers are kept under scripts/. Their generated result files default to ignored target/perf/, while the larger datasets and golden files use /tmp/forust-perf/. The main tools are:

  • perf_sweep.py for steady-state tree timing and thread scaling.
  • perf_grid.py for repeatable before/after grids.
  • perf_compare.py for markdown comparisons between labels.
  • perf_golden.py for byte-identical tree checks.
  • perf_goss.py for GOSS accuracy and speed checks.
  • perf_reference.py and perf_xgboost.py for external reference timings.
  • perf_serial_share.py for Linux perf sampling of serial work.

These numbers are historical engineering measurements, not a promise of a fixed speedup for every dataset or machine. Hardware, feature cardinality, tree depth, sampling, thread count, and evaluation frequency all affect the result.