Skip to content

perf: Improve BufferList and StreamHub pruning efficiency #2094

Description

@coderabbitai

Problem

Both BufferList<T> and QuoteHub (StreamHub) exhibit O(n²) time complexity when processing data sets larger than their default cache/list size caps, due to the way pruning is implemented.

BufferList

BufferList<T> defaults MaxListSize = 100,000. Once the internal list reaches that cap, AddInternal calls PruneList() on every subsequent add:

protected virtual void PruneList()
{
    int overflow = _internalList.Count - MaxListSize; // = 1 each time
    _internalList.RemoveRange(0, overflow);           // shifts ~100,000 elements on each call
}

For 500k input items, this results in ~400,000 calls to RemoveRange(0, 1), each requiring ~100,000 element shifts — approximately 40 billion element moves in total.

QuoteHub / StreamHub

QuoteHub has the same pattern with maxCacheSize = 100,000. After the cap is exceeded, PruneCache() is called on every item via IsOverflowing(), performing Cache.RemoveRange(0, 1). This also cascades to observer caches via NotifyObserversOnPrune / OnPrune, doubling (or more) the total work in a streaming pipeline.

Observed impact

Measured with ADL indicator, 500,000 periods:

Style Expected Actual (with pruning O(n²))
BufferList ~43 ms ~7,555 ms
StreamHub ~50–150 ms ~7,645 ms

Suggested directions

  • Replace List<T> backing store with a circular/ring buffer or LinkedList<T> to achieve O(1) front removal instead of O(n).
  • Or batch-prune in larger chunks (e.g., remove 10% of MaxListSize at once) to amortize the RemoveRange cost.
  • Apply the same fix to both BufferList<T> and StreamHub cache pruning, and to the OnPrune observer cascade.

References

Metadata

Metadata

Assignees

Labels

No labels
No labels

Type

No type
No fields configured for issues without a type.

Projects

No projects

Relationships

None yet

Development

No branches or pull requests

Issue actions