[Haskell-cafe] Google Summer of Code - Lock-free data structures
apfelmus at quantentunnel.de
Thu Mar 29 14:30:12 CEST 2012
Florian Hartwig wrote:
> Heinrich Apfelmus wrote:
> So while the two are related, CAS is a machine primitive that works
> for a single operation and on a single word while STM is a software
> abstraction that isolates sequences of operations on multiple memory
> locations from each other.
>> Is it possible to implement every data structure
>> based on CAS in terms of STM? What are the drawbacks? The other way round?
> I think so. Atomically reading and writing a single memory location
> (which CAS does) is just a very simple transaction. But using a CAS
> instruction should be more efficient, since STM has to maintain a
> transaction log and commit transactions, which creates some overhead.
Ah, I see. In that case, it may be worthwhile to implement the CAS
instruction in terms of STM as well and measure the performance
difference this makes for the final data structure. After all, STM is a
lot more compositional than CAS, so I'd like to know whether the loss of
expressiveness is worth the gain in performance.
More information about the Haskell-Cafe