Hacker News Reader

Comment by lectrick | Hacker News Reader

> I think the hard part of writing side effect free code is that it often involves more allocations

Are you saying this in spite of the existing implementation of decent persistent data structures, at least in some languages? https://en.wikipedia.org/wiki/Persistent_data_structure

I think the cost in more memory (and with persistent data structures, only the difference in memory of the change) is more than made up for by fewer bugs, easier concurrency, and a host of other benefits.

In the light of "mutability always produces more bugs," mutation should be seen as an optimization, after tests are written which cover behavior and side effects.

View on HN

> Are you saying this in spite of the existing implementation of decent persistent data structures, at least in some languages?

No, s/he's saying that because of the existing implementations of decent persistent data structures. Practically all of them allocate way more than mutable data structures - e.g. trie-based vectors/arrays, trie-base hashmaps, tree-based ordered maps, etc. Essentially each new addition, modification or removal results in one or more allocations.

Also, those allocations imply linked, rather than contiguous, data structures, which (often? always?) imply poor cache interaction, which is a major source of inefficiency.

Would love some more perspectives on this, as I've just watched a couple cppcon talks ([0], [1]) and I'm feeling a bit drunk on the kool-aid.

[0]: https://www.youtube.com/watch?v=fHNmRkzxHWs

[1]: https://www.youtube.com/watch?v=rX0ItVEVjHc

There are data structures that are a combination of linked and contiguous, such as the classic rope data structure. For persistent collections, a common backing data structure is the hash array mapped trie, which is basically a quickly-navigated tree of arrays.

Somewhere in there is the obvious tradeoff you have to make between access time and copying time, with regards to the array length.

Thanks for the info, I didn't realize the connection between hash array mapped tries and persistent collections. Are you aware of any open source (ie. linkable) implementations that work that way?

Clojure [1] - the crucial implementation is really in classes BitmapIndexedNode and ArrayNode.

Scala [2] - Scala's source is an incredibly convoluted spaghetti of abstract classes and traits, but it looks like the main bits of implementation is in methods get0 and updated0 of HashTrieMap.

There's also a C# implementation somewhere, but it's not a part of a language library, so it's likely less optimized (except for some boxing/reified generics, which make it theoretically more efficient). But all these implementations use the same basic algorithm, so it's irrelevant which one you study.

[1] https://github.com/clojure/clojure/blob/master/src/jvm/cloju...

[2] https://github.com/scala/scala/blob/2.11.x/src/library/scala...

Wow, thanks for doing the leg work for me. This is the type of thing that reminds me why the internet is so wonderful :)

Sure, the [unordered-containers](https://github.com/tibbe/unordered-containers) library is based on that IIRC, as is the [hash map in Clojure](https://github.com/clojure/clojure/blob/master/src/jvm/cloju...).

It's not just a cost in terms of memory, it's a cost in terms of performance as well. Persistent data structures tend to result in a fair bit of pointer chasing, and the cache miss penalty ain't getting any less expensive.

I find oftentimes when I'm working in F# I do the initial versions of a module using persistent data structures, but eventually the profiler tells me it's time to bite the bullet and switch to mutable structures. The change tends to end up being relatively painless because a huge portion of the time I wasn't relying on persistence anyway, the code does not explode into a confetti of bugs, and run times improve considerably.

I think that's a healthy way to view mutability. It's an amazing performance optimisation, but like any optimisation, it's not to be performed prematurely...

I think, though, that this case really highlights the extent to which Knuth's quote gets used in a much wider context than he intended. In the context he was explicitly talking about micro-optimization, not large-scale performance-impacting decisions.

The use of the word "prematurely" combined with the tendency to forget the context of that quote means it takes on connotations of implying that if you do something for performance from the get-go, that's bad. That just ain't so; sometimes you really do know what you're doing, and know that one option won't be workable and other one will. Choice of data structures is a case where this often happens. If you know up front that you're going to need O(1) random access and replacement, and O(1) typical case and O(N) worst case appending, and that persistence is not necessary, then you already know you want a mutable list. In that case starting with a persistent equivalent and planning to rework things later is likely just a waste of time and, assuming you're doing this at work, money.

Modifying an array requires no allocation; persistent vectors always do.

Linear types are another approach where you're essentially passing around exclusive access to a single mutable structure, so all effects are local. See: Rust/Clean.

Python is an awfully weird language to desire this feature in. You don't even statically know what type profile is, so checking the class you think it will be doesn't actually answer the question. Also effects would necessarily be part of the public api of a given class (preventing someone from later changing verified_email to a "property"), which is quite unpythonic.

I imagine you could do something like "const" in c++. If you're not familiar, const tends to have a lot of behaviors for one keyword, but in this context I mean const methods where basically const means "this method can't modify the state of this object." (Unfortunately it doesn't mean the method is pure, but it's better than nothing)

It does seem like a technique a bit better suited for static compilation though, just in that catching this sort of error at runtime would be slower and harder to figure out.

Even if it was a weak/easily circumvented check it might be useful though, at least as code documentation.

I'm of the opinion that argument values should never be modified by their methods, because that would result in what I've been calling "backflow" or premature state propagation backwards up the call stack. I think this not only hurts concurrency but also reasoning about the code and its flow. I think any new state should be via a return value of the method and not via its arguments.

Reply on news.ycombinator.com