apple / apple/swift-openapi-generator
Keep index into buffer to avoid repeatedly scanning the buffer
- Dominant language
- Swift
- Stars
- 2k
- Forks
- 182
- Avg merge
- 13h 28m
- Merged PRs (30d)
- 5
Description
(Creating this issue from discussion on PR: https://github.com/apple/swift-openapi-runtime/pull/91#discussion_r1442861113).
There are a number of state machines in the runtime library for transforming async sequences of bytes into async sequences of some other structure, e.g. JSON Lines, SSE, JSON Sequences.
Each of these is searching for a delimiter in the currently buffered data and emitting elements if/when it finds a delimiter.
If no delimiter is present in the buffer, it waits for more bytes. But each time it receives more bytes, it will search all buffered bytes for delimiter, including through the bytes that have already been searched.
In the event of any fragmentation of the elements in the byte stream this will be more work than necessary and, with pathological fragmentation, leads to quadratic algorithm that would otherwise be linear.
On the surface, this could be solved by maintaining an index /cursor in the state machine to keep track of which bytes have already been searched for the delimiter. But the devil will be in the detail.
Contributor guide
Research direction
Start with the runtime library's state machines for JSON Lines, SSE, and JSON Sequences, following the linked PR discussion for context. Run the existing fragmented-byte-stream tests, then verify that delimiter searches resume from a cursor without changing emitted elements or handling of partial buffers.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- swift
- Domain
- performance
- Issue type
- Refactor
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 38/100