Repository navigation
tp: stop the sorter from churning memory between extractions #8260
Description
The sorter spends a surprising amount of time in page faults on memory it allocates and throws away again. Two places in particular:
- After extracting a run of events, SortAndExtractEventsUntilAllocId calls shrink_to_fit on the queue, which halves it as soon as it's half empty. The next batch of events then grows it straight back into fresh pages. On the trace from tp: decode track events once into self-contained records and stop carrying packet bytes through the sorter #8258 that's ~90ms (copies plus page faults in CircularQueue::ChangeCapacity).
- StableSortElementsByKey allocates its scratch, counts and gathered buffers with new on every call. They're several MB each, so every sort faults in new pages (~40ms in Queue::Sort).
Not shrinking the queue between extractions and keeping the sort's scratch buffers around took import from 3.54s to 3.42s in a prototype, with identical output.
While we're here it's worth also measuring a loser tree. I tried giving each sequence its own queue (which means nothing ever needs sorting) and merging them with the existing heap, and separately with a batched tree of std::merge calls, but neither beat one radix sorted queue (~10ns/event): with lots of finely interleaved sequences the heap sifts on nearly every event and std::merge mispredicts constantly. A loser tree only needs one comparison per level to replace the winner and can be written without branches, so it might get under the radix sort and would let us drop the sort and its scratch buffers entirely.
Activity