Sign in to follow this  
Hodgman

CAS2

Recommended Posts

Hodgman    51234
I've been reading quite a few lock-free papers recently, and a lot of them resort to solving the hard problems by using CAS2 instead of CAS. Do any popular platforms (e.g. x86/WinXP/Linux, PS3/Cell, 360) actually implement CAS2? I thought x86 only implemented CAS, which would mean all these papers that I'm reading are "ivory tower" stuff... In the meantime I've resorted to hiding dirty bits in my 32-bit pointers to avoid the ABA problem.

Share this post


Link to post
Share on other sites
Drigovas    509
Good news! All of this will be moot in a few years, as the first hardware implementations of transactional memory are coming around, which will render all of this work meaningless. Ivory tower my ass.

Anyway, to your question. CAS2, which typically refers to a double word compare/swap, is implemented on virtually all major ISAs in some way or another (or something is implemented that supersedes it), though most interesting problems have a lot of trouble functioning with just CAS2. 'x86', at least how you likely know it best, implements CAS2 as cmpxchg8b on 32 bit archs and cmpxchg16b on 64 bit archs, if memory serves me well. Many other ISAs actually use single and double word versions of LL/SC, the later of which is far more powerful than cas2, and far easier to implement as far as hardware is concerned. I don't know about CELL specifically, but I'd bet it has something.

So all of that neat stuff you see in the papers is perfectly implementable. If you weren't stuck using such an awful ISA as x86, or any of it's mutated variants, you would have access to the much more powerful LL/SC double word, or even hardware aided bulk memory writes, which would make implementing lockfree stuff a cakewalk.

Share this post


Link to post
Share on other sites
Hodgman    51234
Quote:
Original post by Drigovas
Good news! All of this will be moot in a few years, as the first hardware implementations of transactional memory are coming around, which will render all of this work meaningless. Ivory tower my ass.

Even if CPUs start coming out *now* with transactional memory, I'd still want to support people with current/older CPUs, which means making use of the currently available lock-free primitives ;(

Quote:
'x86', at least how you likely know it best, implements CAS2 as cmpxchg8b on 32 bit archs and cmpxchg16b on 64 bit archs, if memory serves me well. Many other ISAs actually use single and double word versions of LL/SC, the later of which is far more powerful than cas2, and far easier to implement as far as hardware is concerned.

Ahh, excellent! I assume 8b and 16b refer the the number of bytes being compared/written?
To begin with, I'm prototyping all this stuff on Win32, so my first task is just to get a 64-bit CAS operation working on WinXP/32bit.

So far, I've only been using the Microsoft-specific 'InterlockedCompareExchange' family of intrinsic functions to implement my lock-free stuff (not direct assembly).
However it seems they only provide the 64-bit overload of these functions on Windows Vista!
I guess I'll have to get my feet wet and actually start doing these functions in x86 assembly then?

Share this post


Link to post
Share on other sites
Hodgman    51234
Quote:
Original post by Hodgman
I guess I'll have to get my feet wet and actually start doing these functions in x86 assembly then?

If anyone is in the same boat as me and trying to dabble in lock-free design, I just stumbled across LibLTX, which includes portable macros for using CAS, CAS2 and memory barriers, as well as an implementation of Transactional Memory. It's licensed under BSD too ;)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this