tree 1674d293ba03b07a7dad88291a4a52eeae8bdd58
parent fd734301165726c46786e8c3895e07007c78f0d6
author Primiano Tucci <primiano@google.com> 1550531286 +0000
committer Primiano Tucci <primiano@google.com> 1550739948 +0000

Introduce base::CircularQueue and improve trace processor sorter

This CL introduce a queue container backed by a circular array.
This vastly improves TraceSorter's performance, because it makes
delete-front O(1) (% invoking dtors), but still allows std::sort()
of the elements with the same cost of a vector.

This solution is also faster than using a std::deque for |events_|
instead of the std::vector, this is because CircularBuffer is way
simpler than a std::deque.

Benchmark of sorting-stage, obtained commenting out the parsing
stage and running on a 7GB trace [1] on a macbook pro 15 2018.

std::vector: 70 MB/s
std::deque: 260 MB/s
CircularBuffer: 285 MB/s

More CLs will further improve the sorter, but for now this CL alone
makes the trace processor cope better with large traces.

[1] SHA1: ad54e7de3a7,
    trace-walleye-QP1A.190211.001-2019-02-15-20-27-27.perfetto-trace
    from www/~primiano/perfetto/sample_traces

Test: perfetto_unittests --gtest_filter=CircularBufferTest.*
Change-Id: Ie804f54e08d7a9d374aefbe6141cbba65ddf25ec