Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
2  
this is mostly useful in multithreading, where a reader can atomically grab a snapshot and be safe in the knowledge that it won't mutate while he's reading it –  ratchet freak Apr 4 '13 at 16:14
    
@ratchetfreak I get that from the programming standpoint that your code get's more safety guarantees, but my curiosity is about the memory controller on the CPU and how this behaviour matters to it (or if it doesn't) as I've heard claims bandied about a hand full of times that said it was more efficient for the memory controller, and I don't know the low level details well enough to say whether or how this might be true. –  Jimmy Hoffa Apr 4 '13 at 17:03
    
Even if it were true, I wouldn't think that less modification of memory is the best selling point for immutability. Memory is there to be modified, after all, and CPUs and memory managers have gotten pretty good at it over the years. –  Rein Henrichs Apr 4 '13 at 17:58
1  
I'd also like to point out that memory efficiency doesn't necessarily have to depend on compiler optimizations when using immutable structures. In this example let a = [1,2,3] in let b = 0:a in (a, b, (-1):c) sharing reduces the memory requirements, but depends on the definition of (:) and [] and not the compiler. I think? Not sure about this one. –  user39685 Apr 4 '13 at 19:05

1 Answer 1

up vote 20 down vote accepted
+100

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.