Late-comer to this Q&A with already great answers, but I wanted to intrude as a foreigner used to looking at things from the lower-level standpoint of bits and bytes in memory.
I'm very excited by immutable designs, even coming from a C perspective, and from the perspective of finding new ways to effectively program this beastly hardware we have these days.
As to the question of whether it makes things slower, a robotic answer would be
yes. At this kind of very technical conceptual level, immutability could only makes things slower. Hardware does best when it's not sporadically allocating memory and can just modify existing memory instead (why we have concepts like temporal locality).
Yet a practical answer is
maybe. Performance is still largely a productivity metric in any non-trivial codebase. We typically don't find horrific-to-maintain codebases tripping over race conditions as being the most efficient, even if we disregard the bugs. Efficiency is often a function of elegance and simplicity. The peak of micro-optimizations can somewhat conflict, but those are usually reserved for the smallest and most critical sections of code.
Transforming Immutable Bits and Bytes
Coming from the low-level standpoint, if we x-ray concepts like
strings and so forth, at the heart of it is just bits and bytes in various forms of memory with different speed/size characteristics (speed and size of memory hardware typically being mutually exclusive).
The memory hierarchy of the computer likes it when we repeatedly access the same chunk of memory, such as in the above diagram, since it'll keep that frequently-accessed chunk of memory in the fastest form of memory (L1 cache, e.g., which is almost as fast as a register). We might repeatedly access the exact same memory (reusing it multiple times) or repeatedly access different sections of the chunk (ex: looping through the elements in a contiguous chunk which repeatedly accesses various sections of that chunk of memory).
We end up throwing a wrench in that process if modifying this memory ends up wanting to create a whole new memory block on the side, like so:
... in this case, accessing the new memory block could require compulsory page faults and cache misses to move it back into the fastest forms of memory (all the way into a register). That can be a real performance killer.
There are ways to mitigate this, however, using a reserve pool of preallocated memory, already touched.
Another conceptual issue that arises from a slightly higher-level view is simply doing unnecessary copies of really big aggregates in bulk.
To avoid an overly complex diagram, let's imagine this simple memory block was somehow expensive (maybe UTF-32 characters on an unbelievably limited hardware).
In this case, if we wanted to replace "HELP" with "KILL" and this memory block was immutable, we would have to create a whole new block in its entirety to make a unique new object, even though only portions of it have changed:
Stretching our imagination quite a bit, this kind of deep copy of everything else just to make one little part unique might be quite expensive (in real-world cases, this memory block would be much, much bigger to pose a problem).
However, in spite of such an expense, this kind of design will tend to be far less prone to human error. Anyone who has worked in a functional language with pure functions can probably appreciate this, and especially in multithreaded cases where we can multithread such code without a care in the world. In general, human programmers tend to trip over state changes, especially ones that cause external side effects to states outside of a current function's scope. Even recovering from an external error (exception) in such a case can be incredibly difficult with mutable external state changes in the mix.
One way to mitigate this redundant copying work is to make these memory blocks into a collection of pointers (or references) to characters, like so:
Apologies, I failed to realize we don't need to make
L unique while making the diagram.
Blue indicates shallow copied data.
... unfortunately, this would get incredibly expensive to pay a pointer/reference cost per character. Furthermore, we might scatter the contents of the characters all over the address space and end up paying for it in the form of a boatload of page faults and cache misses, easily making this solution even worse than copying the entire thing in its entirety.
Even if we were careful to allocate these characters contiguously, say the machine can load 8 characters and 8 pointers to a character into a cache line. We end up loading memory like this to traverse the new string:
In this case, we end up requiring 7 different cache lines worth of contiguous memory to be loaded to traverse this string, when ideally we only need 3.
Chunk Up The Data
To mitigate the issue above, we can apply the same basic strategy but at a coarser level of 8 characters, e.g.
The result requires 4 cache lines worth of data (1 for the 3 pointers, and 3 for the characters) to be loaded to traverse this string which is only 1 short of the theoretical optimum.
So that's not bad at all. There's some memory waste but memory is plentiful and using up more doesn't slow things down if the extra memory is just going to be cold data not frequently accessed. It's only for the hot, contiguous data where reduced memory use and speed often go hand-in-hand where we want to fit more memory into a single page or cache line and access it all prior to eviction. This representation is pretty cache-friendly.
So utilizing a representation like the above can give quite a decent balance of performance. Probably the most performance-critical uses of immutable data structures will take on this nature of modifying chunky pieces of data and making them unique in the process, while shallow copying unmodified pieces. It does also imply some overhead of atomic operations to reference the shallow copied pieces safely in a multithreaded context (possibly with some atomic reference-counting going on).
Yet as long as these chunky pieces of data are represented at a coarse enough level, a lot of this overhead diminishes and is possibly even trivialized, while still giving us the safety and ease of coding and multithreading more functions in a pure form without external side effects.
Keeping New and Old Data
Where I see immutability as potentially most helpful from a performance standpoint (in a practical sense) is when we can be tempted to make whole copies of large data in order to make it unique in a mutable context where the goal is to produce something new from something that already exists in a way where we want to keep both new and old, when we could just be making little bits and pieces of it unique with a careful immutable design.
Example: Undo System
An example of this is an undo system. We might change a small portion of a data structure and want to keep both the original form we can undo towards, and the new form. With this kind of immutable design that only makes small, modified sections of the data structure unique, we can simply store a copy of the old data in an undo entry while only paying the memory cost of the added unique portions data. This provides a very effective balance of productivity (making the implementation of an undo system a piece of cake) and performance.
Yet something awkward arises with the above case. In a local kind of function context, mutable data is often the easiest and most straightforward to modify. After all, the easiest way to modify an array is often to just loop through it and modify one element at a time. We can end up increasing the intellectual overhead if we had a large number of high-level algorithms to choose from to transform an array and had to pick the appropriate one to ensure that all these chunky shallow copies are made while the parts that are modified are made unique.
Probably the easiest way in those cases is to use mutable buffers locally inside the context of a function (where they typically don't trip us up) which commit changes atomically to the data structure to get a new immutable copy (I believe some languages call these "transients")...
... or we might simply model higher and higher-level transform functions over the data so that we can hide the process of modifying a mutable buffer and committing it to the structure without mutable logic involved. In any case, this is not a widely-explored territory yet, and we have our work cut out if we embrace immutable designs more to come up with meaningful interfaces for how to transform these data structures.
Another thing that arises here is that immutability used in a performance-critical context will probably want data structures to break down to chunky data where the chunks aren't too small in size but also not too big.
Linked lists might want to change quite a bit to accommodate this and turn into unrolled lists. Large, contiguous arrays might turn into an array of pointers into contiguous chunks with modulo indexing for random access.
It potentially changes the way we look at data structures in an interesting way, while pushing the modifying functions of these data structures to resemble a bulkier nature to hide the extra complexity in shallow copying some bits here and making other bits unique there.
Anyway, this is my little lower-level view on the topic. Theoretically, immutability can have a cost ranging from very large to smaller. But a very theoretical approach doesn't always make applications go fast. It might make them scalable, but real-world speed often requires embracing the more practical mindset.
From a practical perspective, qualities like performance, maintainability and safety tend to turn into one big blur, especially for a very large codebase. While performance in some absolute sense is degraded with immutability, it's hard to argue the benefits it has on productivity and safety (including thread-safety). With an increase to these can often come an increase to practical performance, if only because the developers have more time to tune and optimize their code without being swarmed by bugs.
So I think from this practical sense, immutable data structures might actually aid performance in a lot of cases, as odd as it sounds. An ideal world might seek a mixture of these two: immutable data structures and mutable ones, with the mutable ones typically being very safe to use in a very local scope (ex: local to a function), while the immutable ones can avoid external side effects outright and turn all changes to a data structure into an atomic operation producing a new version with no risk of race conditions.
O(pow(n, 2))for every update in its history.) Most other code is an immediate response to an event; a click, API request, or similar, and as long as execution time is constant, the cleanup of any number of objects hardly matters.
O(1)array slicing and
O(log n)inserting into a binary tree while still being able to use the old one freely, and another example is
tailswhich takes all the tails of a list
tails [1, 2] = [[1, 2], , ]only takes
O(n)time and space, but is
O(n^2)in element count