When can I call a function using mutable variables in parallel?

Question

After seeing an interesting lecture by Phil Trelford

https://www.youtube.com/watch?v=hx2vOwbB-X0

I was intrigued about the possibility of accelerating my code by replacing lists with arrays and more generally, of using mutable variables. So I did a simple test:

let xs = [0.0..1000000.00]
let axs = List.toArray xs

let f x = sin (x * x)

List.map f xs // Real: 00:00:00.170, CPU: 00:00:00.187, GC gen0: 5, gen1: 3, gen2: 1

Array.map f axs // Real: 00:00:00.046, CPU: 00:00:00.046, GC gen0: 0, gen1: 0, gen2: 0

Mapping through the array was more than three times faster than mapping through the list. At this point I have not yet tested the speed difference when the function called is more computationally intensive. The difference could be due just to being faster to move through the items in an array, and could become insignificant when each iteration is computationally intensive.

Still, there must be cases in which using arrays or more generally mutable variables could make a significant difference.

Before changing my code to use arrays instead of lists I would like to have a clearer picture of the consequences when the code is parallelized.

In general, when can one use mutable variables without risking having problems with parallelized code? Is there a simple test that would allow me to ascertain the robustness of a function when called in parallel?

score 9 · Accepted Answer · answered Jun 03 '18 at 22:27

The speed difference with arrays has nothing to do with mutability; it's all about cache locality. Arrays are contiguous in memory, so they are faster to iterate through than lists: F# lists are singly-linked lists, so every item can be (and usually is) at a different memory location. This means that you don't benefit from the CPU's cache, whereas with arrays, once you've paid the cost of retrieving the first item from memory, then the 2nd through Nth items (where the value of N depends on the size of the items you're retrieving) are already in the cache and ready for nearly-instant retrieval. If F# had an ImmutableArray class and you used that, you'd get the same speed benefits when mapping through that ImmutableArray as from your mutable array.

As for your main question, about when it's safe to use mutable variables with parallel code, the simple test is to ask "Am I actually mutating the data that multiple threads are using?" If you're not mutating your data, then it's safe to have multiple threads accessing it in parallel. Even if the data could be mutated (e.g., an array), as long as you aren't actually mutating it, then your parallel code won't run into problems. If you do mutate the data, then you have to deal with locking, and all the host of problems that come along with locking such as resource starvation, deadlocks, and so on.

So the simple rule of thumb is "Mutating data + Parallelism = Pain". If you mutate your data but aren't running parallel code, you'll have far less pain. If you aren't mutating your data, then parallel code won't cause you pain. But if you're doing both, get ready for headaches.

It occurred to me that a list which was initialized in one go might actually be memory-local, due to how .NET memory allocation works. — Fyodor Soikin, Jun 04 '18 at 20:53

score 3 · Answer 2 · answered Jun 04 '18 at 16:07

While @rmunn has provided an excellent answer to the actual question, I feel that I must write this addendum, because I consider it very important, and it is too long to fit in a comment.

This is to answer the implied question, which I read as "Since mutable data is faster, shouldn't I always use mutable data?"

It is indeed true that, generally, mutable data structures, if you get them right, are faster on the surface, so why don't we use them all the time? It is also true that jumping, if you get it right, is faster than a function call, so why don't we use goto all the time? It is also true that manual memory management, if you get it right, uses up less memory, and is faster than garbage collection, so why do we use garbage collection? And it is (arguably) true that writing directly in assembly, or even binary code, if you get it really, really right, is faster than compiling, so why do we have high-level languages at all?

The answer to all of the above is that performance is not the only concern in software development. It is not even the most important concern. It could be even argued that it is not anywhere near the top of most important concerns. Much more important in the modern times are readibility, stability, maintainability, overall resiliency.

When designing your system, first try to guess where the bottlenecks are likely to be, then design those places carefully and put some logging and instrumentation around them. When coding the programs, make them readable, understandable, maintainable first. Then measure performance - in production, or in a staging environment if you can afford it. And by "measure" I don't mean "is it the fastest it can be?", I mean "is it fast enough for our purposes?". If it is, well and good. If it is not, find out where the slowdown is exactly, and optimize that place. Over time, with experience, your guess for potential bottlenecks will become better and better.

Don't try to optimize in advance: you'll just end up with a mess on your hands, and you'll have to throw it away soon. Premature optimization is the root of all evil.

When can I call a function using mutable variables in parallel?

2 Answers2