tp: optimize key loading and collision probing in GroupTable **Summary** Fast-path contiguous key loading and validity word scanning in `GroupTable::Load`, hoist `Salt(hash)` calculation out of collision loops, and eliminate unnecessary memory reads on hash collision probes in `FindValues` and `FindOrCreate`. **Why** `GroupTable` powers key grouping and deduplication across executor operators, including `DISTINCT` (`Distinct`), `GROUP BY` (`HashAggregate`), and `GROUPED SORT` (`GroupedSort`): - `GroupTable::Load` gathered keys element-by-element using `column.Index(selection[row])` and checked validity bit-by-bit via `validity->is_set()` on every row, even when batches were contiguous (`selection.prefix()`). For `int64_t` keys, contiguous batches can be loaded with a single `memcpy`, and validity bits can be tested in 64-row words via `ReadBits(start + row, n)`. - In `FindValues` and `FindOrCreate`, `Salt(hash)` was repeatedly recalculated on every probe collision, and `FindValues` dereferenced `group_rows_` to read `stored[1]` and `stored[0]` before verifying whether `Salt(slot) == Salt(hash)`. Because `Salt(slot)` stores the top 16 bits of the hash, 99.998% of hash probe collisions can be rejected immediately without dereferencing `group_rows_` and incurring cache line misses. - `(slot & ~Salt(slot)) - 1` performed multiple shifts and bitwise operations to extract the group number from `slot`, which can be masked directly via `(slot & kGroupMask) - 1`. **Changes** - In `Gather`, fast-path contiguous selections: copy `int64_t` keys directly via `memcpy`, and iterate contiguous arrays without index indirection for `uint32_t`, `int32_t`, and `double` keys. - In `GroupTable::Load`, read validity bits 64 rows at a time using `validity->ReadBits()` when `selection.prefix()` is true, skipping entire 64-row blocks when all rows are valid and using `CountTrailZeros64` for sparse nulls. - In `FindValues` and `FindOrCreate`, hoist `Salt(hash)` computation outside the probe loop and guard `group_rows_` dereferences behind the `Salt(slot) == salt` check. - Fast-path 1-key and 2-key comparisons in `GroupTable::Equal` and hash combining in `GroupTable::Hash`. **Benchmarks** Release benchmarks on `out/linux_clang_release`: - `BM_Distinct/0/512/1/16` (clustered int64): 215,411 ns -> 141,534 ns (1.52x faster, 34% reduction) - `BM_Distinct/0/262144/0/128` (256k distinct int64): 14.35 ms -> 9.10 ms (1.58x faster) - `BM_Distinct/1/512/0/16` (two int64 keys): 540,280 ns -> 428,601 ns (1.26x faster) - `BM_Distinct/2/512/0/16` (string): 248,961 ns -> 173,832 ns (1.43x faster) - `BM_HashAggregate/8/1`: 177,756 ns -> 128,236 ns (1.39x faster) - `BM_HashAggregate/512/1`: 233,426 ns -> 160,189 ns (1.46x faster, 31% reduction) - `BM_HashAggregate/8192/1`: 605,924 ns -> 496,023 ns (1.22x faster) - `BM_HashAggregate/32768/1`: 1,259,551 ns -> 997,989 ns (1.26x faster) - `BM_GroupBy/0/512/0/16`: 476,048 ns -> 378,874 ns (1.26x faster) - `BM_GroupBy/1/512/0/16` (nullable int64): 810,348 ns -> 624,191 ns (1.30x faster) **Testing** - `perfetto_unittests --gtest_filter="*GroupTable*:*Distinct*:*HashAggregate*:*GroupedSort*:*Exec*"` (45 passing tests). - `diff_test_trace_processor.py` on distinct and aggregate tests (17 passing tests). - Verified `SELECT DISTINCT` and `GROUP BY` execution on `test/data/example_android_trace_30s.pb`.
Perfetto is an open-source suite of SDKs, daemons and tools which use tracing to help developers understand the behaviour of complex systems and root-cause functional and performance issues on client and embedded systems.
It is a production-grade tool that is the default tracing system for the Android operating system and the Chromium browser.
Perfetto is not a single tool, but a collection of components that work together:
Perfetto was designed to be a versatile and powerful tracing system for a wide range of use cases.
ftrace, allowing you to visualize scheduling, syscalls, interrupts, and custom kernel tracepoints on a timeline.chrome://tracing. Use it to debug and root-cause issues in the browser, V8, and Blink.We‘ve designed our documentation to guide you to the right information as quickly as possible, whether you’re a newcomer to performance analysis or an experienced developer.
New to tracing? If you're unfamiliar with concepts like tracing and profiling, start here:
Ready to dive in? Our “Getting Started” guide is the main entry point for all users. It will help you find the right tutorials and documentation for your specific needs:
Want the full overview? For a comprehensive look at what Perfetto is, why it's useful, and who uses it, see our main documentation page:
For users interested in the Debian distribution of Perfetto, the official source of truth and packaging efforts are maintained at Debian Perfetto Salsa Repository
Have questions? Need help?
We follow Google's Open Source Community Guidelines.