[schneems]

Immutable data structures give you easy parallelism, however there's a hidden runtime cost: you have to allocate way more objects. For example, I was able to save a ton of object allocations here: https://github.com/mime-types/ruby-mime-types/pull/93 mostly by mutating. For tasks that are not easily parallelizable it may be slower to use immutable structures.

I mostly only ever hear about how fast FP languages are, so maybe they use some tricks to avoid allocations somehow. I would be interested in hearing more about it.

[yjgyhj]

Yes, mutating something at one place in memory is more efficient, because you don't need to allocate new memories.

I don't know all to much about other functional languages, as I learned perl -> ruby -> javascript -> little bit C & Java & Go -> now doing Clojure. But I find Clojures collection data structures interesting. The vector (collection like lists or array) type look immutable, but under the hood are trees. When you append to a vector, you seem get a new vector returned.

In reality, you added the new element as a node in a tree. Then just modified pointers to that the new and old version share almost all of the pointers & allocations. With simple arrays or lists, you would allocate every element anew.

Idk if I can properly explain. Found this blog post very interesting and easier to follow: http://hypirion.com/musings/understanding-persistent-vector-...

Personally, most things in business I find easily parallelisable. You mostly decouple the I/O parts of something with the logic parts of it. But yeah I still have much to learn. Thanks for the link! Interesting :)

[schneems]

That's cool, In Ruby Hash merges are really expensive. I played around with a non-mutating data structure that uses references two two hashes and behaves as if it had been merged instead of allocating. It was a fun thought experiment but wasn't 100% API backwards compatible, as mutations got ugly. Thanks for the link.

[JBiserkov]

You are of course correct. I recommend you check out this 5 posts on Persistent vectors in Clojure http://hypirion.com/musings/understanding-persistent-vector-... "Spoiler from part 4":

>Transients are an optimisation on persistent data structures, which decreases the amount of memory allocations needed. This makes a huge difference for performance critical code.

http://hypirion.com/musings/understanding-clojure-transients

[birdsbolt]

Allocations don't have to be expensive if your GC is smart. Smart as C++ destructors positioning :D

[schneems]

> if your GC is smart

Can you say more? I don't know how C++ uses destructor positioning? Seems to me if it gets to GC it's too late, you already made an allocation which is the expensive part.

[Ono-Sendai]

You can allocate stuff on the stack.

[schneems]

Allocating things on the stack is still allocating things? It's faster to mutate than to allocate?

[Ono-Sendai]

Allocating stuff on the stack is basically free. You just have to decrement the stack pointer.