countvajhula / countvajhula/seq
Performance: Use type-specific implementations where possible
- 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
Assessment
This issue has not been assessed yet.