Regression v4: Filtering via skipUntil vs findIndex/takeLast

[Methuselah96]

---

Migrated from don't!
Originally created by @netzwerg on Tue, 05 May 2020 08:16:17 GMT

---

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

[Methuselah96]

---

Migrated from don't reference!
Original comment by @Methuselah96 on Fri, 14 Aug 2020 21:17:29 GMT

---

Correct me if I'm wrong, but it looks like 4.0.0-rc.12 is actually an improvement over 3.8.2. I say this because findndex/takeLast operates at 680,918 op/s in 4.0.0-rc.12 compared to only 5 op/s in 3.8.2. It looks like filter and skipUntil have maintained about the same speed between versions at 5-7 op/s. It might be worth looking into what sped up findIndex/takeLast so much in 4.0.0-rc.12 compared to 3.8.2, but overall this doesn't look like a regression to me, but actually an improvement.

[Methuselah96]

---

Migrated from don't reference!
Original comment by @Methuselah96 on Fri, 14 Aug 2020 21:27:43 GMT

---

It could be that immutable-js#1077 is what made the difference in takeLast.