apple / apple/swift-openapi-generator

Keep index into buffer to avoid repeatedly scanning the buffer

Open
#501 1 comment 0 reactions 0 assignees View on GitHub
area/runtime kind/enhancement size/M
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.