Evaluate implementation of array backed streams
Nobody has claimed this yet.
Assessment
- Difficulty
- 5/5
- Estimated time
- Over a week
- Newbie friendliness
- 20/100
Research direction
Start by reading the Stream and StreamK representations and their array-related implementations; the issue does not name specific files or tests. Evaluate whether array-backed storage supports scalable cons, append, and indexing without harming fusion or performance, and whether it can replace StreamK and Arrays. Done requires resolving these design questions, including the proposed mutable, boxed or unboxed, and memory variants.
Written by the indexing model from the issue text.
Description
Currently the Stream type does not support scalable cons or append, we need to use StreamK for that. It may be possible to do that if the stream representation has an option to be backed by arrays or lists of opaque step functions. Along with the static step and state a Stream can have lists of arrays for storage of already generated items. The head and tail of the stream can have a cons list and snoc list of arrays for cons and snoc. The middle part of the stream could consist of a static step and state for fusion.
We can support faster indexing into stream because we have an array representation now. If the index falls after the head or before the tail we will have to evaluate the stream up to that part and store it in an array. When the cons list at head and the step function is over we can transfer the snoc list at the tail to the cons list at the head and continue appending. To implement O(1) indexing we will need fixed size array chunks and the count of arrays.
For appending of streams we will need lists of Streams in addition to arrays. When consing or snocing a stream - the head/tail list of arrays can be wrapped into a Stream and consed or snoced to the list of streams and the new Stream can then be consed/snoced to it. This may potentially block fusion though?
Instead of lists we can also use an effect to generate a stream e.g. m (Stream m a), that will keep it generic.
If this does not have fusion and performance issues then it can potentially replace StreamK and Arrays (including stream of arrays), simplifying the API significantly. For representing mutable arrays we can have a MutStream variant. Also we may need boxed and unboxed versions to represent unboxed streams more efficiently. We can also choose pinned/unpinned memory for the arrays backing the stream. This representation can also lend itself to SIMD optimizations. Though this will make the current implementation fairly complex.
- Dominant language
- Haskell
- Stars
- 926
- Forks
- 71
- Avg merge
- 6h 49m
- Merged PRs (30d)
- 3
Getting set up
- No Dockerfile or Docker Compose file
- No pull request template
- Read the contributing guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from composewell/streamly
-
takeInterval yields nothing, dropInterval drops nothingPossibly taken @GuillaumedeVolpiano claimed this 1 day ago. Open
Difficulty 2/5 1-3 hours Newbie friendliness 78/100
composewell/streamly#3271 ·
-
Parser: many accepts input that ends inside an elementPossibly taken @GuillaumedeVolpiano claimed this 1 day ago. Open
Difficulty 4/5 3-5 days Newbie friendliness 52/100
composewell/streamly#3270 ·
-
aspect:api
Difficulty 4/5 1-2 days Newbie friendliness 48/100
composewell/streamly#3206 ·
-
api:breaking aspect:api aspect:filesystem
Difficulty 4/5 1-2 days Newbie friendliness 35/100
composewell/streamly#3203 ·
-
type:performance
Difficulty 4/5 3-5 days Newbie friendliness 32/100
composewell/streamly#3200 · 2 comments ·
All issues in composewell/streamly
Similar issues
-
bug desktop
Difficulty 2/5 1-3 hours Newbie friendliness 85/100
simplex-chat/simplex-chat#8291 ·
Maintainers usually reply within 1 day
-
[BUG]: C# programs with top-level statements fail to compilePossibly taken @AsyncNigam claimed this today. Openbug
Difficulty 2/5 1-3 hours Newbie friendliness 76/100
compiler-explorer/compiler-explorer#9625 · 1 comment ·
Maintainers usually reply within 1 day
-
needs triage type: enhancement
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
Maintainers usually reply within 3 days
-
reflex-0.10Open
Difficulty 1/5 Under an hour Newbie friendliness 62/100
commercialhaskell/stackage#8180 ·
Maintainers usually reply within 1 day
-
documentation
Difficulty 2/5 1-3 hours Newbie friendliness 78/100
OpenZeppelin/canton-contracts#140 ·
Maintainers usually reply within 1 day