Evaluate implementation of array backed streams
还没有人认领这个 Issue。
评估
调研方向
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.
由索引模型根据 Issue 内容生成。
描述
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.
- 主要语言
- Haskell
- 星标
- 926
- 派生
- 71
- 平均合并
- 6 小时 49 分钟
- 30 天内合并 PR
- 3
环境准备
- 没有 Dockerfile 或 Docker Compose 文件
- 没有 Pull Request 模板
- 阅读贡献指南
从这里开始
- 先读完整个 Issue,再读项目的贡献指南。
- 在 Issue 下留言说明你要接手 —— 这能避免两个人做同样的事。
- Fork 仓库,在一个分支上完成修改。
- 提交 Pull Request,并在描述里引用这个 Issue 编号。
composewell/streamly 的其他 Issue
-
takeInterval yields nothing, dropInterval drops nothing可能已有人在做 @GuillaumedeVolpiano 于 1 天前认领。 未关闭
难度 2/5 1-3 小时 新手友好度 78/100
composewell/streamly#3271 ·
-
Parser: many accepts input that ends inside an element可能已有人在做 @GuillaumedeVolpiano 于 1 天前认领。 未关闭
难度 4/5 3-5 天 新手友好度 52/100
composewell/streamly#3270 ·
-
aspect:api
难度 4/5 1-2 天 新手友好度 48/100
composewell/streamly#3206 ·
-
api:breaking aspect:api aspect:filesystem
难度 4/5 1-2 天 新手友好度 35/100
composewell/streamly#3203 ·
-
type:performance
难度 4/5 3-5 天 新手友好度 32/100
composewell/streamly#3200 · 2 条评论 ·
查看 composewell/streamly 的全部 Issue
相似的 Issue
-
bug desktop
难度 2/5 1-3 小时 新手友好度 85/100
simplex-chat/simplex-chat#8291 ·
维护者通常 1 天内回复
-
[BUG]: C# programs with top-level statements fail to compile可能已有人在做 @AsyncNigam 今天认领。 未关闭bug
难度 2/5 1-3 小时 新手友好度 76/100
compiler-explorer/compiler-explorer#9625 · 1 条评论 ·
维护者通常 1 天内回复
-
needs triage type: enhancement
难度 2/5 1-3 小时 新手友好度 72/100
维护者通常 3 天内回复
-
reflex-0.10未关闭
难度 1/5 1 小时以内 新手友好度 62/100
commercialhaskell/stackage#8180 ·
维护者通常 1 天内回复
-
documentation
难度 2/5 1-3 小时 新手友好度 78/100
OpenZeppelin/canton-contracts#140 ·
维护者通常 1 天内回复