[chenglou]

Listing complexity doesn't really help here. There's a huge difference in practical complexity than the theoretical one. Saying that "insert" has log(n) complexity is misleading when you realize the branching factor is 32. Likewise, "compare" has log(n) or mostly constant complexity in most real-life settings where you're comparing against a value that was calculated from the one you're comparing against (so shares lots of subtrees by reference). You're not e.g. sending back a fresh new copy of the data from the server to compare against. Immutable-js _could_ put "it's linear theoretically but most of the time it's really almost constant time", but that doesn't help much either.

Is it blasphemous to say that looking at runtime complexity is gradually becoming more of a premature optimization (thanks to better hardware)? You can argue all day long that your js object has constant insertion time, but the underlying implementation makes it an order of magnitude slower than array for a limited number of fields. And if you accidentally trigger the hidden class deopt that turns it into a hash map that's another order of magnitude slower. No amount of ordinary complexity analysis will help you here. Vice-versa, when Babel gradually starts supporting constant lifting for collections (somehow), you can look at a piece of code in your editor, reason that a comparison is linear, but then have the transpiler lift it out (`const liftedA = []; function foo() {return liftedA;}` instead of `function foo() {return [];}`) and not realizing yourself that the comparison is actually constant time (reference comparison). And then, if you write some overly clever optimization for that piece of code yourself, you might ironically get worse perf because the transpiler can't lift the collection anymore.

That being said, Immutable-js uses the same concept and clojure's persistent data structures (exposed as mori for JS users). Here's a nice article on it: http://hypirion.com/musings/understanding-persistent-vector-...

[davexunit]

>There's a huge difference in practical complexity than the theoretical one.

This resonates with me. I write a lot of Scheme, and often enough someone comes along saying that association lists (simple lists of pairs) are terrible because lookup time is linear and that I should be using hash tables. However, they don't realize that hash tables are only faster when the mapping is very large and come with a penalty of no longer having a persistent data structure.

[rattray]

I found this an extremely helpful comment! Thanks very much, chenglou!

EDIT: Though, I personally think it actually would be pretty helpful if ImmutableJS put something like this in their docs: "it's linear theoretically but most of the time it's really almost constant time"