3 ms·

It's hard for me to say how much it matters, because that would depend a lot on the efficiency of the GC and how many copies are forced (which is a property of

It's hard for me to say how much it matters, because that would depend a lot on the efficiency of the GC and how many copies are forced (which is a property of the application's data structures). Even with Clojure's sharing, it is still the case (as I understand it) that you're forced to copy all nodes between the root and any node that actually changed. A mutating approach doesn't have to do any copies; it can just mutate the interior node of the tree. As an example of a degenerate case, imagine that your root has 10,000 children. If I understand correctly, any mutation to any object in the entire graph requires duplicating the root and the entire 10,000-element array. I honestly have no idea if this would be an important issue in practice or not, I just wanted to mention it as a super-brief pro/con list of immutable data structures.

swannodette 13y ago
Clojure and ClojureScript data structures use 32 way branching nodes. This means even with >2 billion elements in say a persistent vector you'll never have more than 7 hops on any particularly path. This means in the worst case you will need to copy and update 7 children all which are small arrays. I did a bunch of GC testing with Om, the GC profile wasn't dramatically different than naive Backbone.js on TodoMVC which is also working GC by blowing away the DOM on every update.
- haberman 13y ago
  Ah, that's clever. Thanks for the info.
drfloob 13y ago
Part answer to your question, part shameless plug. Node cloning can be done fairly quickly if the bulk of the node data is shared. The `_tree` immutable tree library (https://github.com/drfloob/_tree#quality-metrics https://github.com/drfloob/_tree#quality-metrics) has a 1,024 child-node benchmark. On my slow laptop, it can build 1024 node trees at ~10/second, and the performance appears logarithmic on node count (http://jsfiddle.net/9x7aJ/2734/ http://jsfiddle.net/9x7aJ/2734/). I found it fast enough for my client-side use cases, but Clojurescript's optimized branching scheme could probably be implemented to boost performance. And anyway, if 10ops/second isn't fast enough, `_tree.Tree.batch()` lets you temporarily bypass immutability if needed, making modifications much quicker.

swannodette 13y ago

Clojure and ClojureScript data structures use 32 way branching nodes. This means even with >2 billion elements in say a persistent vector you'll never have more than 7 hops on any particularly path. This means in the worst case you will need to copy and update 7 children all which are small arrays. I did a bunch of GC testing with Om, the GC profile wasn't dramatically different than naive Backbone.js on TodoMVC which is also working GC by blowing away the DOM on every update.

haberman 13y ago
Ah, that's clever. Thanks for the info.

drfloob 13y ago

Part answer to your question, part shameless plug. Node cloning can be done fairly quickly if the bulk of the node data is shared. The `_tree` immutable tree library (https://github.com/drfloob/_tree#quality-metrics https://github.com/drfloob/_tree#quality-metrics) has a 1,024 child-node benchmark. On my slow laptop, it can build 1024 node trees at ~10/second, and the performance appears logarithmic on node count (http://jsfiddle.net/9x7aJ/2734/ http://jsfiddle.net/9x7aJ/2734/). I found it fast enough for my client-side use cases, but Clojurescript's optimized branching scheme could probably be implemented to boost performance. And anyway, if 10ops/second isn't fast enough, `_tree.Tree.batch()` lets you temporarily bypass immutability if needed, making modifications much quicker.