So… Small aside, but List.foldr has been changed in master to not convert to an Array anymore. I also hope Ilias implementation makes it in as it’s even faster, especially for large lists, although code-size is a concern.
When it comes to your benchmark results, I saw this all the time with my work on Array, and this is my theory for why it is so:
There are two surprises here:
-
In all results, even though foldr converts the list to an array, then performs the foldr operation on that array (iterating the list twice, essentially) it’s only 9% or 32% slower.
-
In Safari, foldr is actually faster.
(1) can be explained by the second pass through the list (the actual foldr pass) doesn’t have to chase pointers in the heap to retrieve it’s results. So the second pass will always be much faster then the first (converting a list to an array). Also, the second pass doesn’t need to constantly check if one is currently holding the empty list, as one already knows the size of the array.
(2) cannot entirely be explained by (1). My theory is simply that Safari (using their FTL jit, which uses LLVM I believe) is able to optimize a loop calling a function better than a loop sometimes calling a function (only when not the empty list), and so two simple passes is faster than one tiny bit more complex pass.
However, there are two things which are kinda important to mention when it comes to benchmarking.
(1) Both foldl and foldr calls the given function through a A2 wrapper. If the JS engine only ever sees one use of A2 (like, if currying is never used…), it can inline that into the loop. Making sure that A2 is called differently, like having one benchmark which returns a curried result, could prevent inlining of the A2 call, thus giving you different results.
(2) JIT’s can do loop unrolling if the size of the array is somewhat even (like, say, 5 or 2000). JIT’s cannot do this if you loop until some special condition (like the empty list). Try benchmarking with a non-even number (some prime number bigger than 10) to prevent this optimization in the foldr benchmark.
Why create benchmarks in a way that prevents certain optimizations? Cause code in the real-world doesn’t always trigger the JIT’s happy path. This is especially true in Elm, where loops tend to be handled by the same piece of code, preventing certain optimizations to ever be made (as that looping code suddenly needs to handle many different cases instead of potentially just one).
