immutable-js / immutable-js/immutable-js

Regression v4: Filtering via skipUntil vs findIndex/takeLast

Open
#1,770 2 comments 0 reactions 0 assignees View on GitHub
performance
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.