Google Git
Sign in
flutter / third_party / perfetto / 3e31faf76709ce9732de039228ed086471e0807a
commit3e31faf76709ce9732de039228ed086471e0807a[log] [tgz]
authorLalit Maganti <lalitm@google.com>Thu May 23 18:04:23 2024 +0100
committerLalit Maganti <lalitm@google.com>Thu May 23 18:04:23 2024 +0100
tree55e450b8c5ae5cb0b8ab69ebd8289cf0b457fbbd
parente7d642a71ef935b454e52016e8535865e1eef944 [diff]
tp: rewrite OrderedIndexSearch to be truly O(logn)

This CL changes the implementation of OrderedIndexSearch to
do a binary search direclty at the top level instead of
passing the indices down. This is because translating
all the indices is O(n) wheras we only need O(logn) indices
to be translated.

This *significantly* improves the performance of queries
which happen to end up sorting on a nullable/selector column.

We also remove a bunch of quite complex code which is no longer
necessary.

Before:
```
BM_QEFilterNullOrderedArrangement     112494 ns       112488 ns         6115 s/out=57.6271ns s/row=3.06658ns
```

After:
```
BM_QEFilterNullOrderedArrangement        172 ns          172 ns      4114198 s/out=87.8902ps s/row=4.677ps
```

Change-Id: I34499034b720dfeb3250006e308c3e851078f5e2
35 files changed
tree: 55e450b8c5ae5cb0b8ab69ebd8289cf0b457fbbd
  1. .github/
  2. bazel/
  3. build_overrides/
  4. buildtools/
  5. debian/
  6. docs/
  7. examples/
  8. gn/
  9. include/
  10. infra/
  11. protos/
  12. python/
  13. src/
  14. test/
  15. third_party/
  16. tools/
  17. ui/
  18. .bazelignore
  19. .clang-format
  20. .clang-tidy
  21. .git-blame-ignore-revs
  22. .gitattributes
  23. .gitignore
  24. .gn
  25. .style.yapf
  26. Android.bp
  27. Android.bp.extras
  28. BUILD
  29. BUILD.extras
  30. BUILD.gn
  31. CHANGELOG
  32. codereview.settings
  33. DIR_METADATA
  34. heapprofd.rc
  35. LICENSE
  36. meson.build
  37. METADATA
  38. MODULE_LICENSE_APACHE2
  39. OWNERS
  40. perfetto.rc
  41. PerfettoIntegrationTests.xml
  42. persistent_cfg.pbtxt
  43. PRESUBMIT.py
  44. README.chromium
  45. README.md
  46. TEST_MAPPING
  47. traced_perf.rc
  48. WATCHLISTS
  49. WORKSPACE
README.md

Perfetto - System profiling, app tracing and trace analysis

Perfetto is a production-grade open-source stack for performance instrumentation and trace analysis. It offers services and libraries and for recording system-level and app-level traces, native + java heap profiling, a library for analyzing traces using SQL and a web-based UI to visualize and explore multi-GB traces.

See https://perfetto.dev/docs or the /docs/ directory for documentation.