immutable-js / immutable-js/immutable-js
Regression v4: Filtering via skipUntil vs findIndex/takeLast
- Dominant language
- TypeScript
- Stars
- 33k
- Forks
- 1.9k
- Avg merge
- 6d 7h
- Merged PRs (30d)
- 1
Description
### What happened
Comparing three approaches to filtering a list of 1 million already sorted elements.
The filter predicate matches after 10 elements, i.e. relatively early.
* via `filter`: expected to be slow because all elements have to be traversed
`list.filter(predicate)`
* via `skipUntil`: expected to be fast
`list.skipUntil(predicate)`
* via `findIndex/takeLast`: expected to be fast (similar to `skipUntil`)
`list.takeLast(list.size - list.findIndex(predicate))`
Performance of `3.8.2` is according to expectations:
```
via filter:
6 ops/s, ±1.89% | 14.29% slower
via skipUntil:
7 ops/s, ±2.49% | fastest
via findIndex/takeLast:
5 ops/s, ±6.30% | slowest, 28.57% slower
```
Performance of `4.0.0-rc.12` differs from expectations, `skipUntil` is very slow, indicating a **potential regression**:
```
via filter:
6 ops/s, ±11.66% | 100% slower
via skipUntil:
5 ops/s, ±7.81% | slowest, 100% slower
via findIndex/takeLast:
680 918 ops/s, ±5.81% | fastest
```
### How to reproduce
https://github.com/netzwerg/immutable-js-perf
Contributor guide
Research direction
Start with the reproduction benchmark at https://github.com/netzwerg/immutable-js-perf and run the filter, skipUntil, and findIndex/takeLast comparisons against the reported versions. Trace the relevant collection methods to identify the regression; done means skipUntil no longer shows the reported performance loss relative to the other approaches.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- typescript
- Domain
- performance
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 30/100