| commit | 01cf07b53261827043cdd2f0e206633364d3d91f | [log] [tgz] |
|---|---|---|
| author | Lalit Maganti <lalitm@google.com> | Thu Oct 24 19:14:08 2019 +0100 |
| committer | Lalit Maganti <lalitm@google.com> | Thu Oct 24 19:14:08 2019 +0100 |
| tree | 23319bfa1c7a90c8be2f92f8af5f9074c6a6ad24 | |
| parent | 1ac605ab1a8858d4c16771bf08c21a735a4f666c [diff] |
trace_processor: add zero and one size fast paths for SelectRows This CL adds fast paths for RowMap::SelectRows in the case where the selector has zero and one rows. This allows SelectRows to be a O(1) function in these cases - this is important for nested subqueries in joins on index tables where this function is called repeatedly Old: ---------------------------------------------------------------------- Benchmark Time CPU Iterations ---------------------------------------------------------------------- BM_TableFilterIdColumn/1024 5037 ns 5037 ns 138821 BM_TableFilterIdColumn/4096 19222 ns 19222 ns 36437 BM_TableFilterIdColumn/32768 152193 ns 152188 ns 4607 BM_TableFilterIdColumn/262144 1217069 ns 1217007 ns 574 BM_TableFilterIdColumn/2097152 9802464 ns 9802174 ns 72 New: ---------------------------------------------------------------------- Benchmark Time CPU Iterations ---------------------------------------------------------------------- BM_TableFilterIdColumn/1024 244 ns 244 ns 2871097 BM_TableFilterIdColumn/4096 255 ns 255 ns 2743052 BM_TableFilterIdColumn/32768 429 ns 429 ns 1642865 BM_TableFilterIdColumn/262144 3319 ns 3318 ns 209343 BM_TableFilterIdColumn/2097152 19921 ns 19918 ns 34571 Analysis: As expected, filtering a single Row in an ID column is now significantly faster (20-400 times in the benchmarks) because we are no longer doing a full scan of the source RowMap. However, there is still a small sublinear multiplier between the different sizes which should not exist - this is because we are creating a large bitvector unnecessarily - this will be addressed in a followup. Change-Id: Ie36db4d9ed1c204edb1fb58df6702fc2836a8c07
Perfetto is an open-source project for performance instrumentation and tracing of Linux/Android/Chrome platforms and user-space apps.
See www.perfetto.dev for docs.
You can reach us on our Discord channel. If you prefer using IRC we have an experimental Discord <> IRC bridge synced with #perfetto-dev on Freenode.