[deleted]
XACT: Lock-Free Multi-CAS for C++/x64 Built on TSX
21–30 of 31 posts
Re: XACT: Lock-Free Multi-CAS for C++/x64 Built on TSX
#22The last time I read about TSX it was a story about how Intel pushed a microcode update to disable TSX because it was flawed. Has this been fixed in newer CPUs? Is there a risk of TSX being flawed on CPUs in the wild (for example, if you're missing the latest microcode updates?) http://www.anandtech.com/show/8376/intel-disables-tsx-instru...
If you have a more-recent-than-2014 kernel, BIOS, or stepping, the feature bit ought to be accurate. So sure, there are some systems in the wild that are broken, but probably not that many.
Let's say you're deploying to a random cloud VM that may or may not have the latest microcode/BIOS. How do you know if TSX is safe to use? Can it be determined in software by looking at CPUID values? (If so, do all TSX-using libraries/compilers insert such checks?)
The risk of subtle locking bugs in multi threaded applications due to CPU bugs makes me want to shy away from the entire feature.
Re: XACT: Lock-Free Multi-CAS for C++/x64 Built on TSX
#23Earlier quoted context omitted.
If you have a more-recent-than-2014 kernel, BIOS, or stepping, the feature bit ought to be accurate. So sure, there are some systems in the wild that are broken, but probably not that many.
Let's say you're deploying to a random cloud VM that may or may not have the latest microcode/BIOS. How do you know if TSX is safe to use? Can it be determined in software by looking at CPUID values? (If so, do all TSX-using libraries/compilers insert such checks?) The risk of subtle locking bugs in multi threaded applications due to CPU bugs makes me want to shy away from the entire feature.
CPUID values would be sufficient. TSX should be correct on Haswell-EX (Xeon E7), Broadwell except for the tablet SoCs (Core M), and all Skaylake, Kaby Lake and newer.
Re: XACT: Lock-Free Multi-CAS for C++/x64 Built on TSX
#24He's assuming that retrying forever is a valid retry strategy, which it is not. For example if a page fault was needed to satisfy one of the memory access it would never finish. See https://software.intel.com/en-us/articles/tsx-anti-patterns-... and https://software.intel.com/en-us/blogs/2013/06/23/tsx-fallba... for more details/ To make his code work he likely would need a global fallback lock (or a real STM) and gu…
For anyone not aware, the parent commenter, Andi Kleene, is an expert on TSX. When I last seriously looked in to TSX, around 2013, he was maintaining a fork of glibc with support for TSX-optimized pthread primitives and had written most of the high quality blog posts and information about TSX available online.
Re: XACT: Lock-Free Multi-CAS for C++/x64 Built on TSX
#25So, I looked through the readme and at the example code. I didn't dig into the implementation code. How do you deal with group size limitations? My understanding is that the hardware transactional support makes no forward progress guarantees specifically because it's bound by what it can monitor in the cache. So if the group size is too large, then transactions can keep failing. Hopefully I am not missunderstsnding t…
You're correct: the limits on transaction size are unknown. That's mentioned in the documentation here https://github.com/scivey/xact/blob/master/docs/api/n_way.md
TSX is a black box in many ways, and I think we can expect its behavior to change over time and across implementations.
I'm not enforcing an arbitrary limit on transaction size because the primary goal is just to expose a simple C++ API to fundamental primitives. The TSX intrinsics are much more difficult to work with, and assembly is painful.
If that seems like a cop-out, consider that DCAS is effectively a transaction size of two. TSX appears to handle this trivially. Yet DCAS is already a very powerful operation, and is useful in itself.
As the docs emphasize, the goal is not general transactions but extended versions of the small atomic operations already in common use.
In terms of safety and opinionatedness, I think of XACT like a library of locking primitives: pthread_spinlock_t is very useful, but it will not stop you from introducing deadlocks. Likewise, I won't stop you from attempting transactions that are too large to succceed on current hardware. Ultimately, I expect anyone using this to test and benchmark their own code on their own machines.
Beyond a certain size, transactions will be less and less valuable even if they can be successfully completed: if you're attempting 64-way CAS, benchmarks are probably going to guide you toward traditional locking anyway.
Re: XACT: Lock-Free Multi-CAS for C++/x64 Built on TSX
#26Earlier quoted context omitted.
Agreed that the basic "store to 8 locations" API would need tweaking to allow locking. Re: adding a counter into the read set, I think the new generalized API here will support that out of the box: https://github.com/scivey/xact/blob/master/docs/api/generali... Thoughts?
Yes with a read primitive it could be done in theory. It will be just quite awkward to use however as every caller has to do all that: define a lock, pass it always in, make sure the check for "lock is free" is correct etc. Your unit tests don't seem to do it right. It would probably be easier to hide the lock in your library, and enforce all other access to follow the right protocol using some ADTs. But then you jus…
[deleted]
Re: XACT: Lock-Free Multi-CAS for C++/x64 Built on TSX
#27Earlier quoted context omitted.
Agreed that the basic "store to 8 locations" API would need tweaking to allow locking. Re: adding a counter into the read set, I think the new generalized API here will support that out of the box: https://github.com/scivey/xact/blob/master/docs/api/generali... Thoughts?
Yes with a read primitive it could be done in theory. It will be just quite awkward to use however as every caller has to do all that: define a lock, pass it always in, make sure the check for "lock is free" is correct etc. Your unit tests don't seem to do it right. It would probably be easier to hide the lock in your library, and enforce all other access to follow the right protocol using some ADTs. But then you jus…
Your feedback has been very helpful. Do you mind if I ask you for more advice down the line?
Re: XACT: Lock-Free Multi-CAS for C++/x64 Built on TSX
#28What is the motivation behind this? Multi-CAS is used as a basic building block for lock-free data structures to emulate more complicated transactional operations. But when you already have TSX, why would you use multi-CAS to emulate them? It's better to modify the algorithm and express the transactions directly using TSX.
Re: XACT: Lock-Free Multi-CAS for C++/x64 Built on TSX
#29What is the motivation behind this? Multi-CAS is used as a basic building block for lock-free data structures to emulate more complicated transactional operations. But when you already have TSX, why would you use multi-CAS to emulate them? It's better to modify the algorithm and express the transactions directly using TSX.
In an ideal world yes, but TSX has some significant limitations. andikleen2 has mentioned some of those in his comments.
TSX is somewhat unpredictable as a general tool, and there are difficulties with e.g. knowing which transactions are even feasible. Generic "complicated transactional operations" also make lock-based fallbacks very difficult and expensive, which andikleen2 also touched on.
After experimenting with more general use of TSX, I very quickly came not to trust it. So the real motivation here is to tame TSX's unpredictability by using it in a very controlled way.
TSX simply isn't suitable yet for complicated transactions, but just providing hardware-level support for multi-CAS is already a big deal.
Re: XACT: Lock-Free Multi-CAS for C++/x64 Built on TSX
#30Earlier quoted context omitted.
If you have a more-recent-than-2014 kernel, BIOS, or stepping, the feature bit ought to be accurate. So sure, there are some systems in the wild that are broken, but probably not that many.
Let's say you're deploying to a random cloud VM that may or may not have the latest microcode/BIOS. How do you know if TSX is safe to use? Can it be determined in software by looking at CPUID values? (If so, do all TSX-using libraries/compilers insert such checks?) The risk of subtle locking bugs in multi threaded applications due to CPU bugs makes me want to shy away from the entire feature.
Note that most Linux distros put the latest microcode updates into all of their kernels for any supported version. That means that an updated box with an "old" distro is still going to be OK.