| commit | 9129fad985163ea6114812a319754db19f967c3c | [log] [tgz] |
|---|---|---|
| author | Lalit Maganti <lalitm@google.com> | Thu Nov 14 10:26:45 2019 +0000 |
| committer | Lalit Maganti <lalitm@google.com> | Thu Nov 14 11:34:40 2019 +0000 |
| tree | da0bd33131d909f4e59d676335528a096cf83eca | |
| parent | 06d9a50ca1e53758615d11a967e0fbc5de433233 [diff] |
trace_processor: add special handling of constraints on sorted cols This CL adds special handling for sorted columns. This makes queries on timestamp a lot faster and also allows for future optimizations based on sorted indices. Before: ----------------------------------------------------------------------------------- Benchmark Time CPU Iterations ----------------------------------------------------------------------------------- BM_TableFilterParentSortedEq/1024 2600 ns 2600 ns 272855 BM_TableFilterParentSortedEq/4096 9390 ns 9390 ns 74820 BM_TableFilterParentSortedEq/32768 72911 ns 72912 ns 9502 BM_TableFilterParentSortedEq/262144 585848 ns 585835 ns 1098 BM_TableFilterParentSortedEq/2097152 4503316 ns 4503373 ns 157 BM_TableFilterChildSortedEq/1024 2553 ns 2553 ns 276663 BM_TableFilterChildSortedEq/4096 9305 ns 9305 ns 74081 BM_TableFilterChildSortedEq/32768 70177 ns 70176 ns 9863 BM_TableFilterChildSortedEq/262144 561311 ns 561311 ns 1243 BM_TableFilterChildSortedEq/2097152 4508840 ns 4508755 ns 155 BM_TableFilterChildSortedEqInParent/1024 7009 ns 7009 ns 99503 BM_TableFilterChildSortedEqInParent/4096 26632 ns 26631 ns 26264 BM_TableFilterChildSortedEqInParent/32768 208580 ns 208581 ns 3350 BM_TableFilterChildSortedEqInParent/262144 1669341 ns 1669350 ns 418 BM_TableFilterChildSortedEqInParent/2097152 14231266 ns 14230854 ns 51 After: ----------------------------------------------------------------------------------- Benchmark Time CPU Iterations ----------------------------------------------------------------------------------- BM_TableFilterParentSortedEq/1024 465 ns 465 ns 1493888 BM_TableFilterParentSortedEq/4096 516 ns 516 ns 1369966 BM_TableFilterParentSortedEq/32768 587 ns 587 ns 1192771 BM_TableFilterParentSortedEq/262144 663 ns 663 ns 1066564 BM_TableFilterParentSortedEq/2097152 737 ns 737 ns 961824 BM_TableFilterChildSortedEq/1024 547 ns 547 ns 1294004 BM_TableFilterChildSortedEq/4096 603 ns 603 ns 1154728 BM_TableFilterChildSortedEq/32768 675 ns 675 ns 1020955 BM_TableFilterChildSortedEq/262144 745 ns 745 ns 896101 BM_TableFilterChildSortedEq/2097152 830 ns 830 ns 854048 BM_TableFilterChildSortedEqInParent/1024 931 ns 931 ns 758200 BM_TableFilterChildSortedEqInParent/4096 1068 ns 1068 ns 662916 BM_TableFilterChildSortedEqInParent/32768 1280 ns 1280 ns 545694 BM_TableFilterChildSortedEqInParent/262144 1543 ns 1543 ns 454513 BM_TableFilterChildSortedEqInParent/2097152 1886 ns 1886 ns 373064 Analysis: As expected there is a significant improvement at all levels as we have turned an O(n) query into a O(logn) query. Context: go/perfetto-tp-refactor Bug: 135177627 Change-Id: I2d0f14f4c826556989ee6cdd2f28b0ea585ca5c9
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.