Hacker News Reader

Comment by mikewarot | Hacker News Reader

The recent focus on adapting functional programming is a reaction from the shift to the dangerous quadrant of the immutable-mutable/unshared-shared "Magic Quadrant" chart.

Before multi-core, multi-threading, it didn't matter how or when you decided to update your local variables, they were YOUR local variables... unshared.

With threading, and multiple cores, we all just blindly moved right to the mutable/shared quadrant... the one in bright red... which effectively changes the laws of physics of your programs. Effectively every piece of code now runs in it's own time and space, and if you don't coordinate things correctly, it's like killing your own grandparents.

It took me a long time to understand why you'd want to refactor your code until everything was immutable[1], but now that I get the lesson, its something I won't forget.

Functional programming avoids mutable data, and thus, intentionally or not, works well in a world of shared data. Because pure functions have no side effects, they are timeless - they need no synchronization.

Spend a few nights watching everything Kevlin Henney has said in the last few years, and you'll have a much better handle on things.

  [1] - https://youtu.be/APUCMSPiNh4

[Edit] Incorporate wording suggestion from DonaldPShimoda

View on HN

> Functional programming is a reaction from the shift to the dangerous quadrant of the immutable-mutable/unshared-shared "Magic Quadrant" chart.

This makes it sound like you’re saying that’s why functional programming was created, which isn’t the case. I assume you mean that this is why it’s gained popularity but I don’t really agree with that - it’s certainly valuable but most functional programmers will never touch threads. I’d argue that programs without state are just easier to reason about and debug and for most software this is where the value comes from.

> I’d argue that programs without state are just easier to reason about and debug

Right, isn't the fundamental trade-off between programmer efficieny and runtime efficiency?

Immutable structures are easier to reason about, but almost always run slower than their mutable counterparts.

The holy grail would be immutable structures that are equally performant, but I'm not sure that's even mathematically possible in general.

Is there data supporting the notion that immutable structures are slower?

There are many cases where there won't be a single difference in performance and there are a bunch of cases where immutable structures will be way faster than mutable ones.

The most obvious case I'm aware of is with numerical simulations in scientific computing. I worked on molecular simulations in graduate school. The core data structures are large (many-gigabytes) arrays, and almost every element of the array is updated on every iteration. Everything that requires more memory or even more memory accesses is going to be slower. In business applications you're usually not updating everything in a data structure all the time, so I can see how clever immutability may improve performance.

But a huge mutable data structure means you can't cache the content between cores of a CPU or between systems in a cluster. So you're describing a scenario where mutability incurs a serious performance penalty.

And why are you saying that requiring more memory would make a program slower? I don't see the link.

In one of these simulations, the logic is something like "calculate all the new positions and velocities of the molecules in a box, updated by one micro time step." It's implemented by updating a bunch of matrices in-place by mutation, often using linear algebra subroutines provided by a high performance BLAS like OpenBLAS or the one from Intel's MKL. The matrices are large enough that you'll have to page to disk if you return a new matrix from an old matrix instead of updating the matrix in-place. That's why requiring more memory makes it slower.

At the hardware level, transforming a numerical array M1 into M2 by mutation in-place requires a certain number of memory reads and writes. Leaving the old matrix M1 untouched and returning M2 as a new value (in the immutable style) means that you require at least as many memory accesses as before, but cache locality is likely worse because you're not updating the same address region you are reading from. So I'd expect numerical simulations based on immutable programming techniques to run slower than current simulation tools (like NAMD, AMBER, GROMACS) that perform mutation in-place.

I wonder if the loss of locality would be compensated by the better concurrency of the overall process…

I'd be interested to see benchmarks.

> There are many cases where there won't be a single difference in performance and there are a bunch of cases where immutable structures will be way faster than mutable ones.

Have you maybe written this backwards? It's literally not possible for this to be true.

Mutable data structures have strictly more operations that they're allowed to do, how would they be slower? At very worst they could ignore modifications and be exactly as fast as an immutable data structure.

When you use a mutable data structure, and your code is concurrent, you'll force the CPU to put locks everywhere in your code so that several cores won't see stale data in their internal caches.

Even when you aren't writing concurrent code, mutability will prevent the CPU from using its internal concurrency to execute it faster.

Also, immutable data structures can include caches that are extremely simple whereas mutable data structure would face the problem if cache invalidation if they tried.

And a mutable data structure that would operate as if it's immutable? That's a nice recipe for an epic disaster.

> When you use a mutable data structure, and your code is concurrent, you'll force the CPU to put locks everywhere in your code so that several cores won't see stale data in their internal caches.

Do you mean to say the compiler will insert locks? As far as I'm aware, on AMD64/Intel64, the processor won't lock the bus for ordinary loads and stores unless an instruction has the lock prefix. The processor is otherwise perfectly happy to let different cores observe loads and stores to different addresses in different orders (except for stores being reordered past each other).

> Even when you aren't writing concurrent code, mutability will prevent the CPU from using its internal concurrency to execute it faster.

For an out-of-order superscalar machine, mutability has nothing to do with it; register renaming takes care of that. The things to watch out for are tight dependencies chains.

If you're referring to loads and stores, store-forwarding and coalescing can spare you from having to hit the cache repeatedly for reads and writes to the same location.

> Do you mean to say the compiler will insert locks?

I think you're right, it's the compiler that'll insert the locks according to the semantics of the language.

> For an out-of-order superscalar machine, mutability has nothing to do with it;

Yes it does, because it creates data dependencies. If a piece of code B loads the contents of memory where a piece of code A writes that's before B, then you can never execute B before or in parallel with A.

> If a piece of code B loads the contents of memory where a piece of code A writes that's before B, then you can never execute B before or in parallel with A.

This is a description of what a data dependency is; I'm still not sure what your point is regarding mutable data structures specifically.

A mutable data structure will have such data dependencies all around. An immutable data structure cannot, because it will never be written in after creation.

But an immutable data structure will cause data dependencies – the only way it couldn't cause a data dependency would be if it was never read.

But once it is created, all pieces of code accessing it can be executed in any order because there will never be a write on it again.

Take your favorite immutable data structure. Fix it in your mind.

Now, call it mutable, but don't change a thing. Congratulations, it's now a mutable data structure that's exactly as fast as your favorite immutable one.

_But_ you now have extra opterations you can perform to optimize slow parts if you can. You have strictly more power than you started with, because you can modify data. You don't have to, but you can.

Just don't make any bad optimizations. If some attempt to make it better instead makes it worse, go back to the starting point and try something else.

Do you have examples of this idea that were implemented and weren't insanely error-prone?

The key is that you can start with any immutable data structure you like and change it as much as you want until it stops performing as desired. If that's errors (inability to reason about it correctly) or some other issue, doesn't really matter.

The point is that this procedure applies to anything. Immutable data structures are a strict subset of mutable ones. Every immutable data structure is open to moving any number of steps, in any direction, in the space of data structures. It's _purely_ extra freedom that immutable data structures don't have.

If you want specific ones, first things that would come to mind for me is to start with any immutable tree impl, and start adding small mutable ~caching things on top. Batch up updates a bit to try to avoid repeated deep traversals maybe. You can do this without adding much complexity at all, and it's very flexibly for whatever operations or access patterns you want to improve.

Look for actual examples in the wild that weren't error prone and I'd be surprised you'll find any.

I get that you can imagine it. I'm saying it wouldn't work in practice.

Searching wide and far for a data structure that's that niche in implementation is not really sensible, I'd probably have to implement one myself. If the sketch above doesn't satisfy you, that's about the end for me. Have a good one.

You need to sketch it and possibly implement it yourself because actual examples don't exist. QED

You seem to forget that the CPU and memory system, on which you're executing your immutable data structure implementations, provide a fundamentally mutable interface. So the compiler of your immutable language will still have to insert locks and atomic instructions (although not necessarily the same or at the same places).

> So the compiler of your immutable language will still have to insert locks

No it won't, not at the myriads of places they're needed when there are mutations all over the place.

Of course there are mutations in FP, so of course sometimes we need write locks and use things like CAS.

The point is not that FP doesn't use them, but that it uses them far less because they are needed only in a very limited number of places.

When I write code with STM, for example, the only uses of locks or CAS are in the STM engine, not in my Haskell code, and not even in my compiled code, because my code only ever reads memory that's immutable, and immutable data structures.

When I write pure code, there are no locks at all. And that makes it trivial to execute in parallel, either out of order or on several cores.

> It's literally not possible for this to be true.

The most obvious operation that's much faster for an immutable data structure is cloning.

Cloning, say, an array in a mutable system takes O(n) time. Cloning in an immutable system is just returning the pointer (or whatever pointer + length struct you're using to represent an array).

Updating an element in a mutable array is O(1). With an immutable array you have to make a clone with one element changed which is O(n).

Cloning a mutable array is also O(1) if you use copy-on-write.

> Cloning a mutable array is also O(1) if you use copy-on-write.

Note that this is just an example of the idea that mutable structures can achieve anything immutable structures can, by just treating them as if they're immutable. While you're using copy-on-write, your mutable array can be cloned in constant time and updated in linear time, presenting the exact characteristics of an immutable array.

The mutable "equivalent" algorithm is much nastier, though, since, after you do the cloning, you'll need to create the new object (the slow, O(n) clone) as soon as you want to update either the new structure or the old one. In the functional paradigm, this is also the case -- but you're always generating a new object that you're about to use, as opposed to generating a new object because something else somewhere else in the code was watching you. For example, if you have an array, and you update it (forcing it to be realized), and then you update it a second time, you can't rely on the first time you updated it to prove that the second update will be fast. Maybe it was cloned between the updates.

> Updating an element in a mutable array is O(1).

Yes. Yes it is. The structures have different performance characteristics for different operations.

> It's literally not possible for this to be true

When you need a state that you can rollback, an immutable data structure lets you share the parts of the structure that didn't change between states. That's what ZFS does and that's also how many transactional databases store data.

A mutable data structure would need an entire copy at each state change or it would need to store deltas and apply them backwards when you rollback. Both options are significantly slower than the immutable data structure (where rollback means updating a single pointer).

Those immutable data structures of ZFS are implemented in C and C++, where everything is mutable. You're actually confirming kadoban's point: Mutable data structures can pretend to be immutable or partially immutable, so there can never be an immutable data structure that's faster than all possible mutable data structures.

And I'm pretty sure that if ZFS creates an updated version of some immutable node, under the hood it does this via something that resembles a memcpy() followed by a mutable modification of one or more struct members.

You're misunderstanding ZFS' persistent data structure. It's the whole point that it's not doing a copy then modifying something.

Also no one claims there's one immutable data structure that's faster than all mutable data structures. That's a ridiculous strawman argument.

> You're misunderstanding ZFS' persistent data structure. It's the whole point that it's not doing a copy then modifying something.

I'm talking about the internal implementation of those data structures, not about their API. Neither C nor C++ have built-in immutable data structures, so those persistent data structures with their immutable API are implemented using mutable C structs or C++ classes.

> Also no one claims there's one immutable data structure that's faster than all mutable data structures. That's a ridiculous strawman argument.

No, you're misunderstanding what I said: For any given abstract functionality or interface (like a key->value map, or a graph composed of vertices and edges), there exists a mutable data structure which is at least as fast as all immutable data structures that provide the same interface. That's because the set of mutable data structures is a strict superset of (i.e., contains all) the set of immutable data structures.

> Neither C nor C++ have built-in immutable data structures

First of all, yes they do, you can use const on structs and objects and methods to ensure your C/C++ data structure is immutable.

But this is moot anyway:

> so those persistent data structures with their immutable API are implemented using mutable C structs or C++ classes

ZFS isn't something that's in memory, it's a file system… It's a data structure on disk, it's language-agnostic.

> That's because the set of mutable data structures is a strict superset of (i.e., contains all) the set of immutable data structures.

In theory, that's true. It's just a useless fact.

We use immutable data structures because they have benefits. Using the same data structure without immutability may just render it worse as a software tool. So people don't use immutable data structures with the immutability removed.

Immutable data structures are shaped by trade-offs like any other design.

It's not possible to do always but it feels like it should be possible in special cases. If you can prove that a value V2 is ultimately derived from a modification of V1, and V1 is never referenced after creating V2, then it should be possible to invisibly convert this to an in-place mutation [1]. In the case of applying a bunch of text normalization rules to a string, for example, I care about the final string but not the intermediate states. It could be mutation underneath and I'd be none the wiser, except that the runtime performance would be better.

In Scala you can add a "@tailrec" annotation to recursive functions. The annotation means that the function is guaranteed to recurse efficiently (without growing the stack) OR that the compiler will give an error telling you why it can't be guaranteed. I could imagine a similar annotation like "@withmutation" for functions where you want to guarantee efficient in-place mutation at runtime. As it is, when I run into performance pain points in Scala I redo the critical bits with (manually written) while-loops and imperative mutation.

[1] Unless you later attach a debugger and expect to be able to observe V1 and V2 simultaneously. But I presume this sort of issue already comes up and is somehow dealt with regarding other compiler optimizations.

I think this is the idea behind Richard Feldman's Roc programming language https://www.roc-lang.org/

And just like that, you’ve invented Rust!

AFAIK this is the idea behind ImmutableJS: https://immutable-js.com/

Isn’t it similar to linear types in haskell?

That's basically exactly the same idea, yes.

Haskell didn't invent linear types. Eg Clean had them for ages to do IO. (They didn't use Monads in Clean.)

Immutability is something that happens at the level of the programming language. Runtime efficiency is a concept that, unsurprisingly, lives at runtime.

When eg a Haskell program runs, its supposedly immutable datastructures get mutated all the time. For example laziness is one way that happens.

Another example is that a (pure) Scheme program will overwrite the same memory addresses over and over again while it is running, just like a C program would. Conceptually, no mutation happens, it's just that the garbage collector constantly frees up memory that will be get re-used immediately.

Just a small nitpick about your comment:

> Functional programming is a reaction from the shift to the dangerous quadrant of the immutable-mutable/unshared-shared "Magic Quadrant" chart.

I might rather say "The recent focus on adapting functional programming is a reaction...". Functional programming itself is nearly as old as the modern computer (McCarthy's first LISP paper was published in 1960), but your phrasing kind of suggests that the entirety of FP is a recent innovation.

Functional programming itself is really old. Practical functional programming for scale is the new trend.

What's new is the scale of software being developed right now. Developers simply can't afford to create mutable and shared state as if their program was just another desktop program, executed on a computer disconnected from the internet.

Sooner or later we learn that focusing on the human value of code (I mean, making the code clear, concise and simple to read) pays off way better on the long run rather than optimizing for CPU cycles or memory footprint.

Your global variables were / are shared with yourself, even in no-concurrency case. With typical control flow being far from linear, it's easy to surprise yourself with unexpected state mutation.

Hence the value of immutability even for single-threaded code.

Giving me flashbacks to inherited codebases from old-school FORTRAN coders...

  // 500 variables shared by everything
  main loop
    "task" 1
    "task" 2
    "task" 3
    ...
    "task" n

So t121 is now supposed to only be used by task 3, but "t" as a prefix means it is temp. However, we don't want to change all the references. So just don't use it everyone else, please?

Right. Pure functions make it considerably easier to reason about code, even in the absence of concurrency.

It's a shame D's pure modifier (to statically guarantee purity) isn't available in many other languages. [0] SPARK Ada has something similar in that functions must always be pure, forcing procedures to be used for impure functionality. [1] edit I think that's mistaken, SPARK appears to permit functions to read globals but not to modify them.

edit John Carmack has written about this kind of thing. From [2]:

> if a function only references a piece or two of global state, it is probably wise to consider passing it in as a variable. It would be kind of nice if C had a "functional" keyword to enforce no global references.

[0] https://dlang.org/spec/function.html#pure-functions

[1] https://learn.adacore.com/courses/intro-to-spark/chapters/01...

[2] https://cbarrete.com/carmack.html

What are the advantages of complete immutability when we can write compilers that specifically prevent shared mutability? You're avoiding the dangerous quadrant but also excluding a valid one. I'd definitely prefer FP's solution over Python's GIL, but it still feels like an unnecessary compromise.

Most functional languages allow mutability when you need it, they just default to immutable data. Haskell might be the exception, where everything has to be immutable all the time

Everything does not have to be immutable in Haskell. It's only that mutability can only exist in IO or some other context that deals with it. The language enforces purity, not immutability.

This is not true, Haskell of course allows you to mutate state. It just forces you to declare it: For example, there's a MutableByteArray type whose operations only work in a specific Monad (because Haskell...) [1].

There's also more basic stuff like IORef which represents an assignable variable [2]. Again, you're constrained to use this in IO contexts.

Etc.

Haskell basically just forces you to do that thing someone else in this thread mentioned: Write functional APIs, allow side effects but make them explicit and confined to very specific places.

[1]: https://hackage.haskell.org/package/primitive-0.7.4.0/docs/s... [2]: https://hackage.haskell.org/package/base-4.16.3.0/docs/Data-...

I've worked in two functional codebases so far and I'd say that in both cases the mutation of shared state was just moved to database and its transaction semantics. The FP code itself was about mostly stateless server-side processing. So, FP wasn't doing anything for us on that front. The main selling point for it was that it makes program more composable, more concise and easier to refactor (as you're effectively working with higher-level abstractions).

>> in both cases the mutation of shared state was just moved to database and its transaction semantics. The FP code itself was about mostly stateless server-side processing. So, FP wasn't doing anything for us on that front.

Sure it was. While it didn't force devs to stop using mutable state, you just called out that it -did- force them to move that state out of the service and into something with ACID guarantees, and write their server code in a way that was far more stateless. That sounds like a win to me?

You can also do something like that by using a vanilla ORM and/or batteries include web framework (which includes that) in any popular language of your choice (Spring, Rails, Django, etc).

Sure, if you ensure that every bit of state is going to the ORM, and the ORM caches nothing. Of course, that tends to ensure that what is and what isn't side effect free is massively obfuscated, which seems like you're including some new negatives, but I will totally agree there are other ways to ensure state goes to the state store; I already did.

For most standard web applications, it is true that the RDBMS stores all durable application state; it's also the case that you avoid ORM caching because it introduces more problems than it solves.

Saying "that tends to ensure what is and isn't side effect free is massively obfuscated" really depends on the ORM; if it's an ORM that tries to make an RDMBS "quick" like an object, then I agree (this is something I hate about Django's ORM), but if it's a query builder style ORM then I disagree, as it basically creates a DSL that wraps around the SQL which is already purely functional.

What I'm getting at is that we shouldn't conflate what should take credit for creating sanity in how applications persist state. I think that credit should go to the RDBMS because it exposes the power of the benefits you ascribe to FP, to any programming language that can bind to an RDBMS. If that is the case, what do you really need FP for in general purpose line of business software engineering?

I’ve been bitten by mutable data changing behind my back even without concurrency. It can happen in code that is too magical, eg by having various listeners trigger that aren’t explicit in code (for example “pre_save” hooks in an ORM I have to use in work). It can also happen in deeply heated call chains (my code calls code that calls code that calls code… that mutates data it was given access to at some prior point).

The change is technically in your call stack, but it’s indirect and not necessarily related to your code.

If it were immutable data, then some distant code that holds a reference can’t mutate it unless that data is explicitly marked as mutable.

To me, immutable data is a guarantee that a variable keeps its value, unless I explicitly say it can change (eg by wrapping it in a mutable “box” whose content can be changed). This way, I always know whether I’m giving something write access or only read access. Technically this can be achieved without immutable types (eg constant parameters, pass by value or just documented API promises) but having immutable data as per of the language gives an extra layer of guarantee that’s harder to violate and therefore more predictable.

That is why I like immutable by default, even in single threaded code.

This resembles a situation when I got a new boss who once tried to write a 2-threaded app and got burnt, so from then onward he mandated to never use multiple threads (despite me using it safely on 65000+ threads before). A better answer would be "most devs aren't skilled enough to use many threads/mutable shared objects, so lets mandate immutable for basic devs so that they don't get burnt". But why would you prevent proven experts from operating in the dangerous quadrant? Does everything have to become dumb to make it safe?

That dangerous quadrant has a track record of chewing up and spitting out "proven experts". I'd put your question in the same class of question as "Look, I know memory management in C is just dangerous, but do we have to make everything dumb to make it safe?" False dichotomy; the solution to everything isn't to "make it dumb", but the proven experts have a long track record of being chewed up and spit out and the answer isn't to tell them to just Git Gud either. We tried that. We tried that a lot. It doesn't work.

The solutions to concurrency pretty much all involve staying out that quadrant as much as possible. Immutability isn't the only solution. Another is to confine all variables to one thread. Erlang, for instance, superficially uses immutability to achieve this, but a deeper reason it achieves it is that there is simply no way for a "thread" (what Erlang calls "process") to modify a variable that another thread can see; this is sufficient. (See what Elixir does.) Rust implements a super-rich system of variable ownership that allows you to implement the constraint that no variable can be unexpectedly just modified by an arbitrary thread in a far richer fashion than just hard-locking all memory to a particular owner thread. This is also sufficient. I program a lot in Go, and while it lacks compiler support for forcing you to stay out of that quadrant, my code runs at high concurrency rates precisely because I've learned how to stay out of there, and my code looks very Erlang-ish when you look at the concurrency patterns in play.

new boss who once tried to write a 2-threaded app and got burnt, so from then onward he mandated to never use multiple threads

An unfortunate overreaction, I agree.

Does everything have to become dumb to make it safe?

I don’t think trying to avoid shared mutable state is dumb. It’s deliberately choosing a safer default, just like not allowing all references to be null or not accepting the string "123" where an integer like 123 is needed.

Sometimes it can be useful to have shared mutable state, or to make a reference nullable, or to accept different types of data and quietly reinterpret them the same way internally. But these are inherently more dangerous styles of programming — they create opportunities for mistakes that are otherwise systematically prevented — so it seems reasonable to encourage the safer alternatives unless there is a good reason not to use them, and to make the more dangerous choices the ones you have to make explicitly.

I'd ask the opposite question: why would you use a dangerous paradigm when a safe one exists and the dangerous one doesn't offer much benefit?

The question is if the "unsafe" one really doesn't offer much benefit. If the unsafe one leads to a 3x speed up or a 10x lower memory consumption, then I'll use it.

Do you know an unsafe paradigm that has those advantages over, say, STM or Actors?

Functional programming is representing the program state as a single expression, so that the compiler could do funky maths stuff in reordering things in it. It has little to do with immutability or functions per se.

Reply on news.ycombinator.com