mirror of
https://github.com/hanzoai/next.js.git
synced 2026-10-30 14:46:38 +00:00
3d3def23a1
### What? Optimize the `SelfTimeTree` data structure in the Turbopack trace server for better performance and lower memory usage when loading large trace files, and fix a correctness bug in range queries. ### Why? Two issues were identified: 1. **Performance**: The tree was splitting and rebalancing on every insert during bulk loading, and each `distribute_entries` call recursively triggered further split checks per entry, creating significant overhead. 2. **Correctness**: Range query boundary conditions used exclusive comparisons (`<`/`>`), incorrectly excluding entries that touched the exact start or end timestamp of the queried range. ### How? **Performance optimizations:** 1. **Batch split checks**: Add `insert_without_check` for inserting entries without triggering a split check per entry. In `distribute_entries`, entries are moved to children using `insert_without_check`, and `check_for_split` is called once per child after all entries are distributed (rather than once per entry). 2. **Lazy optimization with memory reclamation**: Add an `optimize()` method and a `for_each_in_range_optimize()` traversal method that distribute and rebalance nodes lazily: - `store.optimize()` is called when the reader reaches end-of-data (before waiting for more), doing a bulk pass to properly structure the tree after initial load. After distributing entries to children, each node calls `shrink_to_fit()` on its entries vec to release excess capacity. - `for_each_in_range_optimize()` distributes and rebalances each node it visits, so query paths are progressively optimized during normal use. 3. **Fix `rebalance()` bug**: `check_for_split()` was incorrectly called after merging subtrees during rebalance — replaced with `distribute_entries()` since the node already has children and needs redistribution, not a fresh split. **Correctness fix:** All range boundary comparisons in `for_each_in_range`, `for_each_in_range_optimize`, and `lookup_range_count` updated from exclusive (`<`/`>`) to inclusive (`<=`/`>=`), ensuring entries with timestamps exactly equal to the range endpoints are included in results. <!-- NEXT_JS_LLM_PR --> --------- Co-authored-by: Tobias Koppers <[email protected]> Co-authored-by: Claude <[email protected]>