Efficient Immutable Data Structures

[rtfeldman]

ClojureScript's approach to emitting JS with high-performance immutable data structures is:

1. Use mori.js for all emitted data structures
2. Emit code that is guaranteed to fit the guidelines for the Google Closure Compiler's Advanced Optimizations, which means emitted production JS can trivially be stripped of whichever parts of Mori aren't being used. (This would also do the same for Prelude, etc., incidentally)

It seems like a low-cost way to get much better performance for functional use cases than the default JS implementations of these data structures, which are designed for mutation.

Thoughts on using some of these ideas in PureScript?

[robotlolita]

I don't think it's possible use mori directly, because the operations don't respect the type assumptions, since all of them turn any data structure in a lazy sequence, which has different semantics, etc.

Google Closure would be interesting, but depends on generating code for that particular compiler assumptions. And I guess it would require generating source maps for debugging.

[paf31]

I think adding compiler support for this might complicate things, but it should be possible to wrap the data structures' APIs using the FFI, and to give them some sensible types. There is also a plan to port the containers library which overlaps with this a little.

[rtfeldman]

Yeah, I'm less interested in specifically using mori than I am in using efficient immutable data structures. It's the type of thing that seems like an obvious eventual optimization for a language that focuses on purity, but thinking about it early could prevent breaking changes later on.

Naturally it's helpful that mori is an open-source implementation of those data structures in JS, but really I mentioned how CLJS achieves this as a starting point for discussion.

[paf31]

So, yes, I think it should become a priority at some point, because what we have now is obviously not ideal, but I think the main focus for the next milestone is going to be porting the compiler to PureScript. After that, I'm happy to revisit this.

The code base is also quite a nice place to experiment with ideas in my opinion, so if anyone had some ideas and wanted to try them out, it should be possible.

[paf31]

Note, we now have fairly efficient immutable balanced 2-3 trees for maps in purescript-maps.

[paf31]

We now have arrays, lists, lazy lists, catenable lists, maps, string maps, sequences, sets, ST arrays and maps, zippers, ... so most cases are covered from a performance point of view.

Bindings for something like Mori could be implemented in a library, but would be best tracked elsewhere I think. I'll close this.

[wires]

Hi, just a thought/remark.

I think it might be worth reconsidering the Google Closure Compiler. When it used in the ADVANCED_OPTIMIZATIONS and especially when all code is compiled in one pass, the resulting code can be really very small. It using smart function inlining and aggressive symbol name shortening. That is why some restrictions on the input JS are imposed, but at least from afar it seems doable. Here is an overview of the code transformations it does.

[robotlolita]

@wires because PureScript gives the compiler more guarantees, investing on PS-specific transformations just pays off better there wrt inlining, tree-shaking/DCE, and stuff than using GCC — afaik the current PS compiler already does all of this. People suggested implementing a supercompiler (https://github.com/purescript/purescript/wiki/GSOC-2015-Projects#supercompiler-for-functional-core) for PureScript some time ago, which would give even better performance, as it can do partial evaluation during compilation and stuff.

[jdegoes]

A supercompiler for PureScript will likely be one of Fantasyland's summer of code projects in 2017.

[wires]

Right, thanks! I was suspecting that maybe by now the compiler caught up with GCC.

Still, when used in a PS project using JS-FFI, its would be good to have some form of tree-shaking across the entire PS+JS codebase. For instance, you have probably seen http://rollupjs.org/ (it uses ES2016 import declarations to do it's work). Supporting tools like this is arguably outside the scope of psc, but is seems nice/useful.

[garyb]

There's a lengthy discussion about that sort of thing here #2207