[Haskell-cafe] Google Summer of Code - Lock-free data structures

[Heinrich Apfelmus]

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.


Best regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com