5 ms·

There's a reason that there aren't many lock free implementations. If you don't get one from your CPU vendor then there's a high chance that it's not correct.

wfunction 10y ago
Are you saying this one isn't correct? Confused what point you're trying to make.
- vvanders 10y ago
  The atomic compare and swap is only one part of getting it right. You also have to deal with memory and instruction fences. Certain architectures have different semantics when it comes to that ordering so something that works on x86 for instance might explode on PPC or ARM. If you want to verify that the algorithms are correct you basically have to do static analysis and the only way you'll do that is if you have access to the microcode and register models(I.E. you make CPUs). [edit] To put this into practical terms I spent some time working with a popular game engine that used a lockfree queue at it's core rendering path. It wasn't until 2 or 3 titles had shipped on this engine that it was discovered that there was a bug in the lockfree algo. We're talking trillions of operations under many different threading and context switching loads and at least 3 different CPU architectures.
  - jdright 10y ago
    Can you cite the name of the tech or any of the games?
  - panic 10y ago
    How was the bug discovered? Sounds like a fun story.
  - jjawssd 10y ago
    What was the solution?
    - vvanders 10y ago
      More fences :) (and the overhead that came with them)
  - trungaczne 10y ago
    I don't get the point you're trying to make. Aren't std::memory_order's guarantees supposed to work with all support archs? The code in the OP does use memory fences. Are you implying that their implementation are incorrect?
    - vvanders 10y ago
      I'm not implying their implementation is incorrect. Just that these types of things are very easy to get wrong and when you do it's usually the type of bugs that take months to track down after you've eliminated every other subsystem involved. Generally if there's not a huge organization putting their reputation(and $$$) on the line there is going to be bugs. Most of the time if you're going lockfree for performance reasons there's usually much large gains to be found in your cache usage or overall architecture.
      - sillysaurus3 10y ago
        Generally if there's not a huge organization putting their reputation(and $$$) on the line there is going to be bugs. This argument applies to any hard problem, so it doesn't seem valid. Whether there's an important bug in a project depends on someone's skill and on how much time they've dedicated to it, and it's hard to know how skilled or dedicated someone is.
        je42 10y ago
        this is less about "skill" but about the awareness how the different CPUs are implemented and where the algorithm is not behaving correctly in conjunction with the CPU spec. In addition the error class is a mean one: doesn't happen often statistically and difficult to reproduce and as such can be very expensive to track down.
        sillysaurus3 10y ago
        The specs are quite clear about memory fences. Just because something has a failure mode that's hard to detect doesn't mean that luck has anything to do with implementing it correctly. And if luck isn't a factor, then that leaves skill and dedication.
  - TeMPOraL 10y ago
    Assuming I don't have access to CPU specs, how could I debug constructs like this queue? Should I set aside a machine and have it pound the queue with random data for the next six months, alerting me each time the error rate rises above cosmic ray threshold?
    - vvanders 10y ago
      > a machine In the absence of formal proof think 50+ machines. You basically setup a lab to run 24/7 and a/b with a hope that you repro. Same technique works for really gnarly intermittent driver bugs. It's still no guarantee but at least you get in the same range assuming the execution profile is diverse and robust.
DSMan195276 10y ago
I would agree, but I'd add that it has been made a little bit easier to handle with the addition of `atomic` in C11 and C++11, since it means you can write atomic code without having to drop to inline assembly to ensure you use the right instructions to make it lock-free. That said, that's only one piece of the puzzle, and you really have to know what you're doing to ensure you write it correctly. That said, after looking at this code the author appears to know what they're doing. I'd have to read it a lot closer to really make sure though.
- ape4 10y ago
  `atomic` may require a lock, depending on the CPU.
  - DSMan195276 10y ago
    True. In that event though, there's little other options. Locking those variables individually like that is probably worse then other locking options though, so it is worth keeping in mind. but while it would be slower, it would still be just as 'correct' as using actual atomic variables.
  - eloff 10y ago
    You wouldn't use this kind of queue on an architecture like that anyway, just use a lock and a regular queue (the lock is not avoidable anyway)
- flamedoge 10y ago
  As far as atomic 'types' are concerned, they rely on CPU hardware for atomicity. I wouldn't be surprised if generated code for non-supported width is done using lock. http://en.cppreference.com/w/cpp/atomic/atomic http://en.cppreference.com/w/cpp/atomic/atomic
  - gambiting 10y ago
    I've been to a C++11 presentation on multithreading recently, and x86 CPUs guarantee that all reads/writes on from std::atomic are indeed, atomic and they always happen in order they were called in. Code generated on ARM guarantees that even multi-byte reads/writes happen in one instruction, but there's no guarantee on the order.
kitsuac 10y ago
Not true at all - the core atomic operations are very well understood by now and are supported on any modern CPU.
- dbaupp 10y ago
  This is a little optimistic: being able to tractibly reason about atomicity in weak memory models like C11 is still at the cutting edge of CS research. It is really hard to prove nontrivial data structures are correct.

wfunction 10y ago

Are you saying this one isn't correct? Confused what point you're trying to make.

vvanders 10y ago
The atomic compare and swap is only one part of getting it right. You also have to deal with memory and instruction fences. Certain architectures have different semantics when it comes to that ordering so something that works on x86 for instance might explode on PPC or ARM. If you want to verify that the algorithms are correct you basically have to do static analysis and the only way you'll do that is if you have access to the microcode and register models(I.E. you make CPUs). [edit] To put this into practical terms I spent some time working with a popular game engine that used a lockfree queue at it's core rendering path. It wasn't until 2 or 3 titles had shipped on this engine that it was discovered that there was a bug in the lockfree algo. We're talking trillions of operations under many different threading and context switching loads and at least 3 different CPU architectures.
- jdright 10y ago
  Can you cite the name of the tech or any of the games?
- panic 10y ago
  How was the bug discovered? Sounds like a fun story.
- jjawssd 10y ago
  What was the solution?
  - vvanders 10y ago
    More fences :) (and the overhead that came with them)
- trungaczne 10y ago
  I don't get the point you're trying to make. Aren't std::memory_order's guarantees supposed to work with all support archs? The code in the OP does use memory fences. Are you implying that their implementation are incorrect?
  - vvanders 10y ago
    I'm not implying their implementation is incorrect. Just that these types of things are very easy to get wrong and when you do it's usually the type of bugs that take months to track down after you've eliminated every other subsystem involved. Generally if there's not a huge organization putting their reputation(and $$$) on the line there is going to be bugs. Most of the time if you're going lockfree for performance reasons there's usually much large gains to be found in your cache usage or overall architecture.
    - sillysaurus3 10y ago
      Generally if there's not a huge organization putting their reputation(and $$$) on the line there is going to be bugs. This argument applies to any hard problem, so it doesn't seem valid. Whether there's an important bug in a project depends on someone's skill and on how much time they've dedicated to it, and it's hard to know how skilled or dedicated someone is.
      - je42 10y ago
        this is less about "skill" but about the awareness how the different CPUs are implemented and where the algorithm is not behaving correctly in conjunction with the CPU spec. In addition the error class is a mean one: doesn't happen often statistically and difficult to reproduce and as such can be very expensive to track down.
        sillysaurus3 10y ago
        The specs are quite clear about memory fences. Just because something has a failure mode that's hard to detect doesn't mean that luck has anything to do with implementing it correctly. And if luck isn't a factor, then that leaves skill and dedication.
- TeMPOraL 10y ago
  Assuming I don't have access to CPU specs, how could I debug constructs like this queue? Should I set aside a machine and have it pound the queue with random data for the next six months, alerting me each time the error rate rises above cosmic ray threshold?
  - vvanders 10y ago
    > a machine In the absence of formal proof think 50+ machines. You basically setup a lab to run 24/7 and a/b with a hope that you repro. Same technique works for really gnarly intermittent driver bugs. It's still no guarantee but at least you get in the same range assuming the execution profile is diverse and robust.

DSMan195276 10y ago

I would agree, but I'd add that it has been made a little bit easier to handle with the addition of `atomic` in C11 and C++11, since it means you can write atomic code without having to drop to inline assembly to ensure you use the right instructions to make it lock-free. That said, that's only one piece of the puzzle, and you really have to know what you're doing to ensure you write it correctly. That said, after looking at this code the author appears to know what they're doing. I'd have to read it a lot closer to really make sure though.

ape4 10y ago
`atomic` may require a lock, depending on the CPU.
- DSMan195276 10y ago
  True. In that event though, there's little other options. Locking those variables individually like that is probably worse then other locking options though, so it is worth keeping in mind. but while it would be slower, it would still be just as 'correct' as using actual atomic variables.
- eloff 10y ago
  You wouldn't use this kind of queue on an architecture like that anyway, just use a lock and a regular queue (the lock is not avoidable anyway)
flamedoge 10y ago
As far as atomic 'types' are concerned, they rely on CPU hardware for atomicity. I wouldn't be surprised if generated code for non-supported width is done using lock. http://en.cppreference.com/w/cpp/atomic/atomic http://en.cppreference.com/w/cpp/atomic/atomic
- gambiting 10y ago
  I've been to a C++11 presentation on multithreading recently, and x86 CPUs guarantee that all reads/writes on from std::atomic are indeed, atomic and they always happen in order they were called in. Code generated on ARM guarantees that even multi-byte reads/writes happen in one instruction, but there's no guarantee on the order.

kitsuac 10y ago

Not true at all - the core atomic operations are very well understood by now and are supported on any modern CPU.

dbaupp 10y ago
This is a little optimistic: being able to tractibly reason about atomicity in weak memory models like C11 is still at the cutting edge of CS research. It is really hard to prove nontrivial data structures are correct.