https://kotlinlang.org logo
#arrow-contributors
Title
# arrow-contributors
j

Jannis

12/20/2019, 4:26 PM
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.
The order actually depends on the applicative instance, which in most if not all cases is left to right.
s

simon.vergauwen

12/20/2019, 5:32 PM
Ah this is great!
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.
Is it really that slow?
j

Jannis

12/20/2019, 5:45 PM
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...
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
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
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 ...
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 🙏
s

simon.vergauwen

12/20/2019, 6:00 PM
Ah… I’ve ran into similar issues with
Sequence
. That was also my first suspect, that’s why I jumped into the code.
There are a couple of tests for
Sequence
in Arrow-optics which are horribly slow compared to the other tests
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 😄
j

Jannis

12/20/2019, 6:09 PM
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.
Regarding eval, it makes for quite the ugly api, does it offer any benefit over
Function0
other than memoization?
s

simon.vergauwen

12/20/2019, 6:20 PM
Well, there is more than meets the eye in
Sequence
since it also relies on suspension IIRC
😟 1
Not sure if that somehow causes slow down, but there is most likely a lot more bytecode present than you think
👍 1
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.
j

Jannis

12/20/2019, 10:16 PM
I should do more testing before I jump to conclusions.
Tldr: sequences are fast. foldRight was the culprit. Stuff is fast now ^-^
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.
s

simon.vergauwen

12/21/2019, 9:01 AM
Right, alright that makes sense. So it was Sequence but the issue was on our side
Exactly why our tests can use some more love!
💯 1
2 Views