Explore optimisations for list prepending in JavaScript

[schurhammer]

The expression [x, ..xs] currently gets complied to the javascript toList([x], xs);. Creating a list and concatenating them seems rather wasteful. I think we should compile to a dedicated function like prepend(x, xs), or just call the list constructor directly.

To validate this I made a modified version of list.range where I manually replaced the toList calls with a prepend function that calls the list constructor, and constructed some lists. The old version took ~230ms and the new version took ~100ms (tested with deno).

[lpil]

I'm surprised there's quite such a different as toList(first, rest) is just first.reduceRight((xs, x) => new NonEmpty(x, xs), rest);, but any faster approach would be gladly accepted.

[schurhammer]

Hi lpil, I've started working on this.

The only down side I can see so far is the readability of the output JS for long lists. Do we particularly care about that?

e.g. this is pretty ugly (although from my testing, the fastest) new $NonEmpty(1, new $NonEmpty(2, new $NonEmpty(3, new $Empty())))

We could put a cons function in the prelude which would help clean it up a bit, and empty can be a constant. The cons function adds very minor overhead, imo negligible. These could also have even shorter aliases in the import (?). $cons(1, $cons(2, $cons(3, $EMPTY)))

Another idea is switching back to toList when there are many elements added at once, say >2 or so. Could be used in combination with aliases of course.

[lpil]

Wonderful! Thank you.

An alias could be good too, rather than a function wrapper. There would be no overhead in that case.

Would just a single character such as $ be too opaque? Assuming that one is free.

[schurhammer]

The problem with an alias without the wrapper function is that you still need to put the new keyword every time, so the minimum you can get is 5 characters.

Single character is fine with me :shrug: $ is being used for asserts though (probably could free it up)

What should we do about lists without a rest param e.g. just [1,2,3,4,5]? I imagine they have the same performance gain to be had from switching, but also they are more likely to be large and thus ugly.

[schurhammer]

My thoughts after some testing:

1. Wrapper function good. Seems to make things more predictable for some reason.
2. Single character was hard to read, I think just go with $prepend. The vast majority of prepends are just one item anyway.
3. Leave lists that are not prepends as-is. I didn't measure a performance improvement from changing these.