Performance of single-assignment ADT oriented code on modern CPUs

Question

Working in immutable data with single assignments has the obvious effect of requiring more memory, one would presume, because you're constantly creating new values (though compilers under the covers do pointer tricks to make this less of an issue).

But I've heard a few times now that the losses there in performance are outweighed by the gains in the way that the CPU (its memory controller specifically) can take advantage of the fact that the memory is not mutated (as much).

I was hoping someone could shed some light on how this is true (or if it's not?).

In a comment on another post it was mentioned that Abstract Data Types (ADT's) have to do with this which made me further curious, how do ADTs specifically effect the way the CPU deals with memory? This is however an aside, mostly I'm just interested in how purity of language necessarily affects the performance of the CPU and its caches etc.

Answer 1

CPU (its memory controller specifically) can take advantage of the fact that the memory is not mutated

Advantage is, this fact saves compiler from using membar instructions when data is accessed.

A memory barrier, also known as a membar, memory fence or fence instruction, is a type of barrier instruction which causes a central processing unit (CPU) or compiler to enforce an ordering constraint on memory operations issued before and after the barrier instruction. This typically means that certain operations are guaranteed to be performed before the barrier, and others after.

Memory barriers are necessary because most modern CPUs employ performance optimizations that can result in out-of-order execution. This reordering of memory operations (loads and stores) normally goes unnoticed within a single thread of execution, but can cause unpredictable behaviour in concurrent programs and device drivers unless carefully controlled...

---

You see, when data is accessed from different threads, at multi-core CPU it goes about as follows: different threads run at different cores, each using its own (local to their core) cache - a copy of some global cache.

If the data is mutable and programmer needs it to be consistent between different threads, measures need to be taken to guarantee the consistency. For programmer, this means using synchronization constructs when they access (eg read) data in particular thread.

For compiler, synchronization construct in the code means it needs to insert a membar instruction in order to make sure that changes made to the copy of data at one of the cores are properly propagated ("published"), to guarantee that caches at other cores have the same (up-to-date) copy.

Somewhat simplifying ^{see note below}, here's what happens at multi-core processor for membar:

1. All cores stop processing - to avoid accidentally writing to cache.
2. All updates made to local caches are written back to global one - to ensure that global cache contains most recent data. This takes some time.
3. Updated data is written back from global cache to local ones - to ensure that local caches contain most recent data. This takes some time.
4. All cores resume execution.

You see, all the cores are doing nothing while data is being copied back and forth between global and local caches. This is necessary to ensure that mutable data is properly synchronized (thread safe). If there are 4 cores, all 4 stop and wait while caches are being synced. If there are 8, all 8 stop. If there are 16... well you've got 15 cores doing exactly nothing while waiting for stuff needed to do at one of these.

Now, let's see what happens when data is immutable? No matter what thread accesses it, it is guaranteed to be the same. For programmer, this means no need to insert synchronization constructs when they access (read) data in particular thread.

For compiler, this in turn means no need to insert a membar instruction.

As a result, access to data doesn't need to stop cores and wait while data is being written back and forth between global and local caches. That's an advantage of the fact that the memory is not mutated.

---

Note somewhat simplifying explanation above drops some more complicated negative effects of data being mutable, for example on pipelining. In order to guarantee required ordering, CPU has to invalidate pilelines affected by data changes - that's yet another performance penalty. If this is implemented by straightforward (and thus reliable:) invalidation of all pipelines, then the negative effect is further amplified.