<https://github.com/arrow-kt/arrow/pull/1868> This...

# arrow-contributors

[Jannis]

https://github.com/arrow-kt/arrow/pull/1868
This is ready for review, it fixes a lot of issues with traverse. Apart from traverse now being left to right for (all?) functors, this should not affect any existing code.

[Jannis]

The order actually depends on the applicative instance, which in most if not all cases is left to right.

[simon.vergauwen]

Ah this is great!

[simon.vergauwen]

I read your comment about performance. I checked Eval and there are a couple of small improvements that can be made that I see immediately but nothing that would significantly speed it up.

[simon.vergauwen]

Is it really that slow?

[Jannis]

Not noticable for anything but collections that are beyond a certain size. Long sequences get the heaviest penalties, generateSequence(0) { it + 1 }.take(10000).traverse(IO.applicative()) { IO { println(it) } } takes a longer than my patience offers (upwards 5-10 min the last time I think, and my laptop is by no means slow). It does the first 1k and then gradually slows down.
traverse_ is equally slow, so I think it's on foldRight and likely on Eval . Do we even need it? We just need basic laziness not all the extras Eval brings, right? That is also the reason I chose lazyAp(ff: () -> ...) instead of lazyAp(ff: Eval<...>) . This might also be on sequences, but since even traverse_ is not faster I think it's less likely. I'll retry with lists...

[Jannis]

just retried it with traverse_ , same thing, slowdown comes a bit later, but still not fast. It goes from 100s per refresh on the terminal to 10s to 1s

[Jannis]

I take that back, it's probably not traverse . generateSequence(0) { it + 1 }.take(10000).map { println(it) } is also slowing down after the ~1.5k element mark. Just not as much as traverse . Fun

[Jannis]

The list one is also plenty fast, so it's sequences, again. Why are these so slow... It's just a function with some carried state, this should not slow down ...

[Jannis]

Sorry for the misleading text about slowness, should have tested it more/better, I've just mostly been working on sequences (with this pr and in the past propCheck) and it got frustrating to watch at some point 🙏

[simon.vergauwen]

Ah… I’ve ran into similar issues with Sequence. That was also my first suspect, that’s why I jumped into the code.

[simon.vergauwen]

There are a couple of tests for Sequence in Arrow-optics which are horribly slow compared to the other tests

[simon.vergauwen]

Do we even need it? We just need basic laziness not all the extras Eval brings, right?

All the instances that can be rewritten without Eval probably should. If the laws hold then performance wins over Eval 😄

[Jannis]

I just don't really get why the slow down occurs. https://github.com/JetBrains/kotlin/blob/deb416484c5128a6f4bc76c39a3d9878b38cec8c/libraries/stdlib/src/kotlin/collections/Sequences.kt#L538 has generateSequence as a stateful iterator which means at any point it' just current state + the same lambda that was passed before. This should be fast. It also slows down considerable without take(10000) so thats not it either.

[Jannis]

Regarding eval, it makes for quite the ugly api, does it offer any benefit over Function0 other than memoization?

[simon.vergauwen]

Well, there is more than meets the eye in Sequence since it also relies on suspension IIRC

[simon.vergauwen]

Not sure if that somehow causes slow down, but there is most likely a lot more bytecode present than you think

[simon.vergauwen]

Regarding eval, it makes for quite the ugly api, does it offer any benefit over Function0 other than memoization?

Not sure actual. Haven’t used either a lot.

[Jannis]

I should do more testing before I jump to conclusions.

[Jannis]

Tldr: sequences are fast. foldRight was the culprit. Stuff is fast now ^-^

[Jannis]

I tried the generateSequence example again with fold and it worked fast. Then tried it again like I set up before and it is also fast. I probably ran something weird before.
Sequences from kotlin are plenty fast. And the reason it is slowing down in arrow is the foldRight implementation which is copied from lists. The culprit is the recursive function which expects a sequence as it's argument and it gets the tail of a sequence by calling drop(1) which creates a new DroppingSequence every time. And because dropping sequences flatten themselves out the original sequence is kept alive with all it's elements and we basically iterate from the start for every element. This has an easy fix: Just use the iterator directly in foldRight.

[simon.vergauwen]

Right, alright that makes sense. So it was Sequence but the issue was on our side

[simon.vergauwen]

Exactly why our tests can use some more love!