Hacker News Reader

Comment by ehvatum | Hacker News Reader

Neat! x86_64 has CMPXCHG16B. Learn something new every day.

It has to - to mitigate ABA problem.

Depending what you use it for.

The bigger problem with it is you can't just load/store a 128 bit value without this instruction. An SSE 128bit load/store is turned into two 64 bit operations under the hood. So to actually get atomic loads and stores you need to use this very expensive compare exchange operation. That really limits the number of algorithms it's useful for.

Why would it? The crucial part is usually a variation of comparing and swapping a 64 bit pointer and a 64 version number at the same time.

If you can do that, for most algorithms it doesn't matter much if you do two 64 bit loads to get the values. If you are out of sync your compare and swap is going to fail anyway, which is likely to be rare.

I've personally found it limiting many times. I know the one place where I did actually end up using it, I had 128 bits of information where I had to be very careful with ordering of loads and stores and had to detect torn writes and retry.

Maybe my experience is not representative, but it's something to be aware of when designing algorithms with it.

Why would you need to do that unless you were writing over individual 128 bit ints from one thread while reading them at the same time from another thread?

There are many better ways to do something like that. Anything that writes a buffer, then makes it available atomically would work much better, or you could just use the compare and swap.

There is always going to be a limit of what is atomic. At some point you have to work with a data structure meant for larger data. The cut off has to be somewhere.

It was the primary key index in a database using MVCC. It stored various flags and a version (transaction timestamp) and data pointer. It also stored something else that I don't recall, maybe a previous version record pointer. All packed into 128 bits. Adding a new record version required cmpxchg16b, but reading it or just updating a flag was tricky because the 64bit words only had meaning together so I had to detect torn writes and retry the read with appropriate memory barriers.

This means though, that you were somehow synchronizing a larger record using this technique. Maybe you were writing it in one thread, then atomically changing your 128 bit struct to make it available to other threads.

Whatever else was part of your 128 bit struct could probably be part of the record instead. You could use a 64 bit address and a 64 bit version number. Looking up could be done by atomically reading the 64 bit version number only. Writing a new record would then require the compare and swap.

Yes, that's correct, that's actually the obvious way to write it. I think the logic behind putting it in the index was to be able to check the transaction timestamp without the extra indirection and cache miss, and to have that information there if the data is on disk, and there is no record loaded in memory. Not having the indirection was a big deal for the cache eviction algorithm which sampled many records and then evicted the coldest %, weighted for frequency of access and size.

There are other ways of doing that though, I'm not sure the trade off was the best one in the end.

Right, so it isn't about lots of algorithms being prevented, it is actually a pretty reasonable constraint and not a huge deal.

If you were worried about cache and indirection, the indices could be aligned to the start of a 64 byte or 128 byte boundary, since 64 bytes is the cache line size but (Intel) cpus will load two cache lines at a time. Because of this, loading in your 64 bit/8 byte index should mean that the 120 bytes after it are going to be cached.

Let’s keep 80s music out of this ;)

Looks like I need to resort to ASM for visual c++. Might do.

Reply on news.ycombinator.com