Hacker News Reader

Comment by overgard | Hacker News Reader

I totally agree with all of this, but I think the hard part of writing side effect free code is that it often involves more allocations. (Since you're constantly constructing new values and objects, and transferring them around on the stack). I think this is why you see a lot more mutation (and bugs) in C: managing allocations is annoying. Having a garbage collected language mitigates the burden on the programmer, but if you're writing performance sensitive code that means you're putting pressure on the garbage collector so you're going to get more pauses. Not to say you shouldn't write in this style, you should, but there's a pretty big opportunity for languages to get better in this regard.

View on HN

> 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.

> 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...).

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.

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.

The article advocates explicitly typed effects rather than less effects in code. Effect systems are also useful for making high-performance code safer (or enforce considerably static safety at small or no runtime cost). The core feature of Rust is statically safe direct mutation, and also we have the ST monad in Haskell which lets us do mutation behind safe immutable API-s.

This is an objection that people seem to raise disproportionately often - particularly when they have no performance tests and never profile their code. The one time I've seen a real-world head-to-head comparison between C and Haskell, the Haskell version performed 5x better than the C version. In fact I've literally never known a real-world Haskell program to have serious performance problems (I've known some that needed a small amount of time to be spent on profiling).

I realise this is much less satisfactory than a convincing theoretical solution; all I can say is that it just doesn't come up in practice.

> In fact I've literally never known a real-world Haskell program to have serious performance problems... all I can say is that it just doesn't come up in practice.

Considering how few real-world Haskell programs are, and how small they tend to be, I think it's best to say that we don't yet know how serious the effect is. If anyone ever writes an ERP or an air-traffic control system in Haskell, then we'll have pertinent evidence to support or contradict the claim.

Well, Erlang is also basically immutable at its core, and seems to do reasonably well. It's definitely not up there with C (that'd be ridiculous) but within its domain I haven't heard many performance complains either.

Most performance-sensitive Erlang programs use C for the performant bits (they use Erlang for the control plane and C for the data plane). So it's fast enough only for things that don't need to be fast.

This isn't real world, but it's useful to see:

http://benchmarksgame.alioth.debian.org/u64q/compare.php?lan...

2-6x slower, more memory, roughly same amount of code.

> The one time .... Performed 5x...

Ah! I see that totally seals the deal and is so much more better than the claims of the other people you were complaining about. That BLAS author must be an idiot same for Nginx. 5x here I come. Heck why are these js runtime writers wasting there time. Its 5x do you hear me.

I am sure comments like these would help Haskell so much

This is essentially the same argument that people made against Java, Python, and Ruby (amongst others). But that didn't prevent them from being enormously popular languages used by tons of people to get things done. I don't see any reason to expect that controlled side effects ala Haskell will be any different.

> constantly constructing new values and objects, and transferring them around on the stack

This is not necessary, as long as your type system doesn't allow aliasing of mutable values (such as pointer arithmetic, eww)

https://en.wikipedia.org/wiki/Substructural_type_system#Line...

http://clojure.org/transients

Some of the languages have gotten better! Clojure, for example, has smart data structures that share elements to speed up operations and minimize copying:

http://hypirion.com/musings/understanding-persistent-vector-...

Reply on news.ycombinator.com