The documentation above this class claims that it is “Lock Free”. It is not. Having no Synchronization primitives of any type does not make it lockfree.
In addition, Adding the Volatile Keyword in no way prevents out of order execution. This is done by the Computer Hardware not the compiler. The Volatile keyword tells the compiler not to cache the value, but instead always load at the last minute. BECAUSE it can change at any time from any other thread. Which most of the time causes a cache miss and a pipeline flush.
To prevent out of order execution, you must use Acquire and Release semantics on an actual synchronization primitive.
This documentation is misleading and confusing.
It should simply read, “This class is NOT thread safe.”.
You can file a bug report instead
Hey Dan, thanks for your feedback! I wrote that class and its documentation a few years ago and will give it an overhaul soon. The problems you pointed out are all valid. I’ll try to address them soon.
I took a quick stab at it using the relatively new TAtomic primitives. I’m using the default sequentially consistent model, which makes for cleaner code, but may have some extra overhead. I don’t fully understand the implications on all of our target platforms yet, so this is probably the safe way to go for now. I’ll check with our Core Team on optimizing this further.
I attached the new version. If you get a chance, please take a look and let me know if you find any problems with it, thanks!
I don’t seem to have those in 4.18… I’ll look at 4.19 when I get home.
I don’t have a problem with the class as is… But when another engineer saw that it said Lock-Free, he started putting it into multi threaded code. Which is not safe…
A new queue should be created TCircularQueue_LF<> where LF stands for Lock Free… (IE: Compare Exchange)
or TCircularQueue_TS<> where TS stands for Thread Safe (IE: critical Section).
To be truly a Lock Free implementation you need to use the Compare Exchange… That’s the only atomic operation that guarantees that 2 threads are not competing for the same resource. With the Compare exchange you have 2 types of platforms… Ones with Acquire/release semantics and ones that enforce a fence or a barrier. A fence is like having both Acquire and Release for an entire cache line. A Barrier is like a fence, but acts on ALL cache lines.
The acquire semantic says, “Nothing After this Code can execute until we have returned.”. Release semantics says, “Everything Before this must be finished before we release the lock.”. When used together they insure that the Protected sections of Code Are executed between the Acquistion and the Release.
A/R Semantics are the most lightweight form of protection against out of order execution…
I’ve avoided CAS in the past… With simple Atomic Inc Dec for the head and tail… Which I assume is what the TAtomic is doing? Atomic Set only works in SPSC as you indicated… MPMC requires CAS.
Yeah, the intent of the class is to be lock-free for SPSC scenarios, and the previous version was clearly broken. Since there isn’t really a point in having a non-thread safe queue, I’ll keep the name as is. I don’t think CAS is necessary here since we don’t need total consistency. As long as push and pop don’t interfere with each other, eventual consistency (in terms of empty / full) is fine.
TAtomic has been added recently. It might not be in 4.19 yet. Its Load and Store methods use total sequentially consistent memory order by default, i.e. both acquire and release.