Skip to content

Event log eviction is quadratic and the comment claims O(1) removal #27

@nficano

Description

@nficano

src/Arcp.Runtime/Store/EventLog.fs stores each session buffer in System.Collections.Generic.List<EventLogEntry> and evicts old entries with repeated RemoveAt 0 calls in both Append and EvictExpired. List<T>.RemoveAt(0) shifts every remaining element and is O(n), so expiring many entries or trimming a full resume buffer can become O(n²). The inline comment above evictOne also says RemoveAt 0 has O(1) amortised semantics, which is factually incorrect and can mislead future reviewers about the cost of the data structure.

Fix prompt: replace the per-session List<EventLogEntry> with a data structure that supports cheap front removal, such as Queue<EventLogEntry> plus snapshot copying for replay, or implement a ring buffer with a start index and count. Preserve the existing replay semantics where Replay and All return stable snapshots while holding the per-session lock only briefly. Update the comment to explain the chosen structure and add a test that appends more than MaxPerSession entries and evicts a large expired prefix without relying on repeated front-shifts.

Metadata

Metadata

Assignees

No one assigned

    Labels

    performancePerformance and allocation improvementsseverity:mediumMedium severity

    Type

    No type
    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions