Immutability Changes Everything (2016)
queue.acm.org
queue.acm.org
For users who do not need a serialized view of events, access to "near-real-time" data can be made to scale as far as needed, even if a single machine is driving all the writes. You could theoretically have a billion readers working off a single synchronous core system.
By utilizing careful abstractions, that single core system can write something on the order of 10-100 million transactions per second. We do it every day on the various financial exchanges around the world. In many cases, a single thread is what is holding up the entire exchange. Arrays of structs, hot cache lines, correct branch prediction and full pipelines are a hell of a combo.
In some practical businesses apps, it is also feasible to coalesce logical writes before they need to enter a fully-synchronous context, so you can get some step-down ratio like 100:1 on transactions that actually need to go across the network and be handled by the core system.
They say you can solve any problem in computer science with another level of indirection - except performance, it seems, because we're paying the cost of all this indirection all the time, even if we don't need it most of the time. There's a crazy amount of unnecessary "housekeeping" done by compilers and runtimes to make sure everything always works all the time, which requires them to always do extra work to protect against pathological cases that almost never arise.
Modern compilers and runtimes are getting better and better at recognizing the common "happy case" and optimizing for that, and that's good. But it still feels backwards - both that we can't explicitly opt out of unneeded flexibility, so instead the compiler needs to deduce that we aren't using it. But also that a lot of this isn't opt-in to begin with, rather than opt out - i.e. make things immutable by default. Or let the programmer tell the compiler a little bit more about what they need and don't need the code to do, so the compiler can do a much better job if it.
I lightbulb moment I had recently was that the classic interface-based OO programming paradigm utilising virtual functions was essentially the following declaration by the programmer to the compiler: The function that is invoked can change at any time, even call-to-call; assume nothing. it is a black box with unknown, unknowable contents. Do not inline it, do not inspect it, expect the worst.
If you look at a typical web framework, with call stacks hundreds of methods deep, you'll come to the same horrifying realisation that these are all inherently un-optimisable because of that statement. The compiler can do nearly nothing, and the processor will also struggle to paper over the inefficiency. Meanwhile, in reality, the specific implementations of those interfaces never change during actual production execution! Dynamic dispatch is utilised only during development time, and even then only at compile time to inject test harnesses, mocks, or whatever.
At runtime, 99.999999% of all function calls are essentially static, and dynamic dispatch is a pure waste.
Optimizing JIT-compiling JVMs are often able to optimize virtual calls that only ever resolve to one implementation. They may even inline such calls. (edit dzaima got there first.)
The Java HotSpot Performance Engine was released on April 27, 1999, built on technologies from an implementation of the programming language Smalltalk named Strongtalk, originally developed by Longview Technologies, which traded as Animorphic. The Longview virtual machine was based on the Self virtual machine, with an interpreter replacing the fast-and-dumb first compiler. When Sun cancelled the Self project, two key people, Urs Hölzle and Lars Bak left Sun to start Longview. In 1997, Sun Microsystems purchased Animorphic.
Source: wikipedia
std::variant is almost it, but it's interface is quite horrendous as of now.
Another interesting thing is that c++ also intermingles dynamic allocation with polymorphism, which can lead to a lot of unnecessary pointer chasing
I'm always on the lookout for talks about interesting and generally useful concepts, but where I can follow only a small part of them. Makes me feel like I can learn and grow into a wiser person. This certainly fits that criteria.
Ya. I've spent the last two decades removing levels of indirection, reducing call stack depth. This has put me at odds with most everyone. I've been insulted many times for not understanding "software architecture". Heh.
I started a design pattern study group shortly after GoF's book was published. I think it's a lot like jazz. 1st time thru, mind blown. 2nd time, ah, I think I'm starting to get it. 3rd time, well, duh.
Eventually students get full circle, a la "there is no spoon", and you reject the veneer of "design patterns". Said another way, it's just another tool, learn to use it wisely. Learn to reject temptation.
Aspects, annotations, runtime code reflection, metaprogramming, frameworks, schema mappings, factories, singletons, and whatnot are just monkey work. (Most of the time.) Exquisite puzzles (finger traps) to suck smart people people in. To distract from the real work of solving customer's problems, business needs.
I think the kids these days call it "yak shaving." Yes, I am very guilty of this. Past, present, and surely future. I'm no better than anyone else. I recognize my failings and am trying to improve.
Managed/interpreted langs have a different proposition: pay up front for all the features, but your complexity never increases whether you use none, one or all of them.
• Variables are immutable by default
• The layout of a struct’s fields in memory is opaque to the programmer, allowing the compiler to reorder them to minimize padding
• As a natural consequence of the borrow checker, Rust has much more information about whether or not two references could alias than most other languages
• The programmer is very much made to feel the cost of dynamic-dispatch (via dyn), and static-dispatch is the norm
• The compiler can omit bounds checks when it can prove they’re unnecessary
• It’s easy to safely have structs that live entirely on the stack (i.e. no heap allocation)
Overall this is an unsolved problem though. It seems to me that the trend is that the more details about the internals that the language exposes to the programmer, the fewer optimizations can be made automatically. Essentially the ideal is declarative performance, where the programmer expresses the idea and the compiler figures out the optimal implementation (which is in stark contrast to most high-performance code being hand-tuned today). Take a look at something like Halide for a successful application of this philosophy: https://halide-lang.org/
You can do this today in languages like C#:
https://docs.microsoft.com/en-us/dotnet/csharp/write-safe-ef...
> Adding the readonly modifier to members that don't mutate state provides two related benefits. First, the compiler enforces your intent. That member can't mutate the struct's state. Second, the compiler won't create defensive copies of in parameters when accessing a readonly member. The compiler can make this optimization safely because it guarantees that the struct is not modified by a readonly member.
I much prefer to having a language/runtime that can handle extremely complex problem scenarios out of the box (with the need for occasional tuning), rather than the other way around. It is not very often that I find myself screwing around with performance-intensive code. Usually, a few very important things are addressed at the lowest levels and then you put all your nice abstractions back on top for daily driving.
The big picture design is simply described as an append only log of copy on write page states, with Kafka style compaction to maintain whatever window of history you want. This is supplemented with a compact in memory index that holds the LSN for the latest page states to make accessing live data as fast as possible.
The write path goes through a single batch committer thread to amortize fsync overhead (technically two threads in series so I can overlap prepping the next batch with waiting on fsync). Single writer isn't a big limit since even on consumer grade SSDs you can write at GiB/sec now. Append only log means I hit the happy case on SSDs. FTLs have come a long way in equalizing sequential vs random write performance, but this comes at the cost of a lot more write cycles behind the scenes to shuffle stuff around.
Here's two examples of how immutability has drastically simplified the design:
First, the in memory index is just a hand tweaked version of a Bagwell Trie. Since the trie is copy on write, once the fsync finishes the write thread can publish the new index state with a single atomic write. Client threads never see any intermediate state. The database moves from snapshot to snapshot atomically from their view. (This is the part I'm coding up atm)
A second example is want to have an on heap cache, to avoid overtaxing the SSD or the downfalls of a pure mmap caching approach (mmap can be the miss path for this cache however). I'm planning on using a lock free hash table. Since I'm working in a language that doesn't have such as a library, I'll have to roll my own. Ordinarily this would be an insane idea, as such structures are infamous for being nearly impossible to get correct, even when using formal modeling tools. But in my case, the relationship of LSN -> Immutable Page State is stable, so the cache can be quite sloppy. With a mutable cache I'd in essence have to ensure the CAS always went the right place, even under resizing, etc. But with immutability duplicates are only a potential memory waste, not a correctness problem, so I get to be quite a bit more sloppy.
One shouldn't treat any single thing as a panacea, but I've definitely come around to the view that immutable by default is a good approach. You get to just trivially dodge entire categories of nasty problems when doing something like the above.
I'd love to hear anything more you can share about the stuff you work on. It sounds really interesting.
I've been working on a key-value store that is purpose built for low-latency NVMe devices.
I have an append only log (spread across file segments for GC concerns), with the only contents being the nodes of a basic splay tree. The key material is randomly-derived, so I don't have to worry about the sequential integer issues on inserts. Writes to the database are modified roots of the splay tree, so the log is a continuous stream of consistent database snapshots. For readers that don't require serialization, they can asynchronously work with the historical result set as appropriate without any translation or sync required. You just point the reader to a prior root node offset and everything should work out.
I'm working in golang. Client goroutines that execute read write transactions buffer up their read and write sets, then submit them to the committer goroutine via a channel. Part of the struct they submit has a blocking channel for the committer notify them of the result. So nothing returns to the client unless it's stable on disk. Assuming I get far enough, in a future version that'll also include optionally waiting for raft replication.
I'm getting almost no google results for "Bagwell Trie". Where can I read about this?
These are the prior work for HAMTs, which have been implemented in a bunch of languages.
Without going back to school, how would I learn how to do that? (Books I should read, good open source examples, any Coursera courses?)
"Tesler's Law" [1] :-) makes sure you are looking from a different perspective. Complexity is still present.
"Immutability is not enough"
https://codewords.recurse.com/issues/six/immutability-is-not...
[1] - "Tesler's Law" https://en.wikipedia.org/wiki/Law_of_conservation_of_complex...
The author never defines, what sort of problems immutable data can help avoid, or what the benefits of immutable data are. And still, after every paragraph, he wonders why functional programming didn't help him avoid bugs in his business logic.
Like, what the hell, the author produced a bug because the order of your operations was wrong? Great, write a test and restructure your code to make it work, at least you know where to look.
Functional Programming does not fix your Game Loop, and it never promised to.
I just wanted to comment that I love your last paragraph from a conceptual level. You want immutability? Great, let's talk about what performant game design looks like in that context. Games are special, in that they kind of do everything that computers are good at, to varying degrees. The author's ideas about snapshots of relational databases inviting further schema changes in the pipeline—I guess I see the idea you're trying to introduce, but what does it actually look like in a chess program? Or a choose your own adventure game?
[link redacted]
The premise is that any edit produces a new function, but the old one still exists, so you need to migrate calls from the old version to the new version.
The benefits really start to manifest in distributed computing and package management: much less need to worry about transitive dependencies and conflicting versions.
The editable code is a projection of a data structure, so refactoring and static analysis tools will be very easy to write. Also the syntax is just a display issue and can be changed easily, everyone could read and write code in the syntax they prefer.
It does increase some complexity, but I think it is essential complexity we currently have only poor ways to manage, and explicit knobs to turn will allow us overall less effort.
> any edit produces a new function, but the old one still exists, so you need to migrate calls from the old version to the new version
I'm not the guy to expand on it further, but maybe the above commenter could answer questions.
I can see how that would work better if function references are to hashes of entire functions, rather than just the names of functions.
Thank you for your persistence though and for chiming in with the right answer!
[1] https://www.goodreads.com/book/show/52653567-the-art-of-immu...
And then events that happen less frequently. Hourly. Daily.
There is no need to ever change that data, only append to it.
Does anyone here know what I should be looking at for append-only data storage technologies?
For more modest scale you could use something like lmdb, where append only hits a happy case optimization.
I disagree here. To derive new data or from a immutable data source you still want normalized data. Denormalization can happen at some point for processing. Sometimes normalization is not feasible, because it often requires modelling/design. But it is the best general case scenario for data to be well-structured and normalized.
Also the “accountants don't use erasers” feels really glib to me, it’s hard work.
The artifact we produce, typically immutable in a package repository, then has "semantic versioning" (possibly) to convey whether they should care.
[0] https://www.unisonweb.org/
purity is to functions
as
immutability is to data
Immutability is definitely a valuable technique that can help make software faster (sometimes), more reliable, and easier to maintain. I would take it one step further and argue that we can get a similar boost by extending the idea to functions, not just data. And the way you do that is by writing pure functions (i.e. no side effects...or controlling/limiting them in some way) and using languages that can enforce that your functions are pure.
I thought all data was just a bunch of nullary functions. ;)
On the issue of bug counts, there was one huge study, that was successfully reproduced [0], which finds that there is a real but small negative correlation between FP and bug counts in large GitHub projects.
For productivity I haven't been able to find any large-scale studies that compare functional vs imperative/OOP languages. I did find one small scale study [1] that found significantly better productivity for Haskell (and a Lisp dialect) vs Ada, C++ and a few others, but it was about a specific small prototype problem with just a handful of programmers participating (the Haskell program had 85 lines, the worse, C++, had 1105; and programs took between 10h and 54h to finish - hardly representative of large-scale coding). Most other studies on productivity that I could find [2], [3] didn't include any FP languages at all.
[0] https://arxiv.org/pdf/1901.10220.pdf
[1] https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.36...
[2] https://www.e-informatyka.pl/attach/e-Informatica_-_Volume_1...
[3] https://www.researchgate.net/publication/4261726_Do_Programm...
> For productivity I haven't been able to find any large-scale studies that compare functional vs imperative/OOP languages
I'm having trouble reconciling these two statements of yours.
Very few algorithms are not faster with mutable variables.
If the compiler knows the original data is never needed, it can optimize away the old copies, too. At least that's the hope, I'm not sure how true it is.
That is the definition of an algorithm, not immutability.
Granted, some effects like this can be mitigated with sufficiently clever language design. Haskell with lazy evaluation. I believe some compilers for functional languages will reuse memory addresses they can prove nothing else refers to, so in reality they are mutating in-place even if semantically the variables are "immutable." Heck, even Python does that with the built-in immutable types. When you assign the changed data to a new name, it doesn't actually allocate new memory and just does it in-place under the hood. In cases like that, the data isn't really "immutable." It just can't be mutated by the programmer, only by the runtime or compiler.
Of course, if we want to get sufficiently pedantic, no data is ever immutable. The law may say a ledger is append-only, but nothing is stopping an accountant from just lying. A compiler may prevent you from assigning new data to an already-existing name binding, but a compiler can't stop someone from using rowhammer or an x-ray machine or something and flipping the bits in memory anyway.
This is not true. Accounting is usually a most mutable data source you ever have. Facts arrive at random times and then are entered on a schedule. Corrections await on someone to resolve analytical issues. Different accounting units have different timelines, and in a unit there is many threads of an unordered fact flow. It is all synced together only at specific points, usually when it’s time to report officially or internally. If you ask your accountant and the only thing they drop is “busy”, it’s one of these weeks of the year.
When a company's quarterly results are published, they include small corrections to the previous quarter. Small fixes are OK. They are append-only, too.
This is true, because public reports are legally binding.
On topic: in my opinion, immutability at small scales is good, because modifications do not leak accidentally into the fields of your data structures (e.g. a mutable string is a bad idea in general). But at the bigger scale immutability gets in the way, if not hidden properly. It requires a less common sort of developers who have to think in immutable/functional way, and even when they can, this increases their cognitive distance to the business logic. Properly hidden immutability helps a lot though, and we mutable guys use it a lot, despite a widespread belief. It’s transactions and execution context isolation. There is nothing wrong with mutating the operative area if these mutations cannot escape it. But if you’re short on primitives (a context object, an object model vs global.store and raw fields of a one-for-all object) you end up with setting globally visible state that can be read from the outside and trouble creeps in. Moreover, a real world code rarely looks like you’ve seen in a tutorial and instead of a clear `assemble(this(), that())` you have to resort to non-ordinary functional tricks and concepts in the name of it. As a result, you have to hire (or be one of) these functional guys who may be better in general, but also spend half their cognitive abilities on things that you couldn’t explain to an accountant.
So yes and no, immutability changes everything, but it’s not the only way to change it. It is just the easiest manual way to feel safe if you start naked in the woods.
I fail to see how any of this implies the data is mutable.
Of course one could design a system that made changesets append-only and explicit for them. But they would object, the same way you’d object if instead of updating a working tree, `git pull` simply appended a set of patches to every file in it and expected you to modify source code only by appending patches yourself. Developer’s own work model is mutable (a working tree), and you can’t expect an accountant to be surprisingly fine with what you personally are not.
once debit is posted to your account (let's say it is fraudulent transaction, or transaction entered by mistake), nobody will go and erase it as if it never happened. They would actually do reversal, by creating a new entry with the same amount and opposite sign. So you would env up with two transactions: +100 and -100.
same is true for most accounting systems. Once the accounting period is closed (daily in banking system, monthly for most other companies), you can't change the closed month. All changes go as new transaction adjustments