countvajhula / countvajhula/seq

Performance: Use type-specific implementations where possible

Open
#2 0 comments 0 reactions 0 assignees View on GitHub
help wanted
Dominant language
Racket
Stars
6
Forks
0
PR merge metrics
No merged PRs in 30d

Description

All `seq` functions are implemented on streams, and produce streams as output (unless `(require seq/iso)` is used, but that is just a facade on the underlying stream-based implementations). This works for all sequence types, but it usually isn't as efficient as a type-specific implementation could be, and sometimes doesn't take advantage even of generic optimizations that could be used.

For instance, the [implementation of `init`](https://github.com/countvajhula/seq/blob/5f39a40242d8690c01bcbdcabb0b7880ee75d11b/base.rkt#L181-L184) could be done in constant time by returning a view of the immutable underlying data structure instead of constructing a new one, like [the implementation of `reverse` in data/collection](https://github.com/lexi-lambda/racket-collections/blob/c4822fc200b0488922cd6e86b4f2ea7cf8c565da/collections-lib/data/collection/private/random-access.rkt#L32-L33).

It would be great to (1) add benchmarks to get a sense of baseline performance, and (2) implement optimizations.

It may also be worth considering a `gen:sequence-api` generic interface containing all of the Seq APIs, if that would make type-specific optimizations more seamless, as it would extend to user-defined types as well.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.