3 ms·
> The idea is that parallelism begins from how you structure your data Sure, but again, you're talking high-level. At a low-enough level, every operation is de
by pron 13y ago
> The idea is that parallelism begins from how you structure your data
Sure, but again, you're talking high-level. At a low-enough level, every operation is destructive, because that's how our machines work. If you're using immutable data-structures, then you're allocating memory, so you are bumping (destructively) some heap pointer. Even if that pointer is thread-local, sooner or later some garbage collection will take place, which requires some form of synchronization.
The idea is that somewhere in your software stack, be it the OS or the JVM or whatever, there will be shared mutable state, and that's where lock-free data structures are handy. Some high-level languages abstract that away from you so you don't have to deal with this stuff.
Also, parallelism is only part of the story. Parallelism, or data parallelism, divides the data so that it can be processed cooperatively in parallel, but that's not always what you have. Lock-free data structures are useful when doing concurrency rather than parallelism, i.e. lots of different computations (rather than one), competing for (rather than cooperatively sharing) limited resources.