3 ms·

Om is an immutable data structure library: a structure is never mutated once created, which means that the contents of the entire tree are captured

Om is an immutable data structure library: a structure is never mutated once created, which means that the contents of the entire tree are captured in the identity of the object root. Or in simpler terms, if you are passed an object that is the same object (by identity) that you saw earlier, you can be assured that it hasn't changed in the meantime. This pattern has a lot of nice properties, but also generates more garbage than mutable objects. Is this true to the extent that it typically matters? I would expect so with sort of naive immutability (copying everything whenever you make a change), but not with the kind of structural sharing that Clojure(script)? persistent data structures use.

STRML 13y ago
You're right in a sense, it generates more garbage than mutable objects because there is more data available than with mutable objects. In most cases it won't matter. Of course if you're holding a global interface undo queue for the lifetime of your page, and your page changes often, you might run into memory issues. But Clojure's immutable datastructures work as well - or better - than you'd expect.
haberman 13y ago
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.

STRML 13y ago

You're right in a sense, it generates more garbage than mutable objects because there is more data available than with mutable objects. In most cases it won't matter. Of course if you're holding a global interface undo queue for the lifetime of your page, and your page changes often, you might run into memory issues. But Clojure's immutable datastructures work as well - or better - than you'd expect.

haberman 13y ago

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.