Regression v4: Filtering via skipUntil vs findIndex/takeLast

[Methuselah96]

From @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

Copied from original issue: https://github.com/immutable-js/immutable-js/issues/1770

[Methuselah96]

Might be worth looking into why skipUntil is so slow.