Summary
The stream reassembly buffer in quinn-proto/src/connection/assembler.rs keeps chunks in a BinaryHeap<Buffer> and goes through it even when the stream arrives in order, which is the common case for a bulk transfer.
Avoiding the heap on the in-order path seems worth 2 to 3% of client CPU on the receive side. It will not show as throughput on x86, where the receive path is dominated by AES-GCM; as with #2735, the value is CPU on constrained hardware. Two options for your consideration, neither of which I have written yet:
- Hold contiguous chunks in a
VecDeque and fall back to the heap when a gap appears. This removes the per-chunk heap work on the in order path. Cost: there would be two containers, and buffered, allocated, end and defragmentation all touch the heap today.
- Something smaller. A partial read in
read() advances the front chunk's offset through PeekMut. Mutating through a PeekMut makes the heap sift the root back down when the PeekMut is dropped, in case the mutation broke the ordering. Usually it did not: the offset moves forward only within the chunk that was already at the front, so that chunk still sorts first and the sift changes nothing. Avoiding it on that path would be a much smaller change than option 1.
Measurements
I added a temporary counter to Assembler::insert to see what the heap holds during a bulk download. Over 900k inserts on a link with a 10ms delay:
- average heap length at insert: 25
- maximum heap length: 127
- chunks starting beyond the highest offset seen so far, ie a gap: 5, or 0.001%
The heap sits around 25 deep while the data is essentially always in order. The depth looks like the receive batch filling the assembler faster than the application drains it, rather than reordering. Every insert does data.push() and every read does data.peek_mut(), so each one sifts a 56 byte Buffer through about five levels to keep an order the data already has.
BinaryHeap<Buffer>::push plus PeekMut<Buffer>::pop are 2.1% of client CPU on a 3 GiB loopback download, and about 3% on the 10ms link. Setup: quinn-perf, main plus #2730 and #2735, release build with debuginfo and frame pointers, perf record -F 999.
One caveat. I could not get tc netem's reorder to actually reorder in my test environment: at 25%, 50% and 99% it moved about one packet in fifty, and the assembler counters agree. So everything above is an in-order path. If you want the reordered case measured first, I can try again with two delay bands.
Summary
The stream reassembly buffer in
quinn-proto/src/connection/assembler.rskeeps chunks in aBinaryHeap<Buffer>and goes through it even when the stream arrives in order, which is the common case for a bulk transfer.Avoiding the heap on the in-order path seems worth 2 to 3% of client CPU on the receive side. It will not show as throughput on x86, where the receive path is dominated by AES-GCM; as with #2735, the value is CPU on constrained hardware. Two options for your consideration, neither of which I have written yet:
VecDequeand fall back to the heap when a gap appears. This removes the per-chunk heap work on the in order path. Cost: there would be two containers, andbuffered,allocated,endand defragmentation all touch the heap today.read()advances the front chunk's offset throughPeekMut. Mutating through aPeekMutmakes the heap sift the root back down when thePeekMutis dropped, in case the mutation broke the ordering. Usually it did not: the offset moves forward only within the chunk that was already at the front, so that chunk still sorts first and the sift changes nothing. Avoiding it on that path would be a much smaller change than option 1.Measurements
I added a temporary counter to
Assembler::insertto see what the heap holds during a bulk download. Over 900k inserts on a link with a 10ms delay:The heap sits around 25 deep while the data is essentially always in order. The depth looks like the receive batch filling the assembler faster than the application drains it, rather than reordering. Every insert does
data.push()and every read doesdata.peek_mut(), so each one sifts a 56 byteBufferthrough about five levels to keep an order the data already has.BinaryHeap<Buffer>::pushplusPeekMut<Buffer>::popare 2.1% of client CPU on a 3 GiB loopback download, and about 3% on the 10ms link. Setup:quinn-perf, main plus #2730 and #2735, release build with debuginfo and frame pointers,perf record -F 999.One caveat. I could not get
tc netem'sreorderto actually reorder in my test environment: at 25%, 50% and 99% it moved about one packet in fifty, and the assembler counters agree. So everything above is an in-order path. If you want the reordered case measured first, I can try again with two delay bands.