5 ms·
I have to say that even though it is nice to write about lock free algorithms, it would be probably worth noting that this implementation is dismissing the prob
by recentdarkness 12y ago
I have to say that even though it is nice to write about lock free algorithms, it would be probably worth noting that this implementation is dismissing the problem of CPU caches which eventually and most likely lead to race conditions.
- augustl 12y agoWhat kind of race conditions are you talking about? Something along the lines of memory access that causes the CPU caches to be purged a lot more than they normally would? Genuine question, I know little about CPU cache internals :)
- jacquesm 12y agoOut of order execution and possible cache consistency issues can cause your careful order to be upset. The solution is memory barriers: http://en.wikipedia.org/wiki/Memory_barrier http://en.wikipedia.org/wiki/Memory_barrier
- brigade 12y ago? That's the point of this post (well, the second I guess) - the lock free version has those via atomics.
- jacquesm 12y agoSo CDS_ATOMIC:: and friends expands into barrier instructions that take care of both re-ordering and cache consistency issues? edit: reading the http://en.cppreference.com/w/cpp/atomic/memory_order http://en.cppreference.com/w/cpp/atomic/memory_order there is tons of data on re-ordering but nothing on cache consistency so I am assuming that's a job farmed out to the hardware somehow. In that case ignore above comment :)
- pkolaczk 12y agoI don't know if this implementation got it right (I don't have a spare month to prove/disprove its correctness)but my advice would be: be very, very careful with lockfree code in C++. This the area where dragons live. Let me cite Herb Sutter: "Second, it's hard even for experts. It's easy to write lock-free code that appears to work, but it's very difficult to write lock-free code that is correct and performs well. Even good magazines and refereed journals have published a substantial amount of lock-free code that was actually broken in subtle ways and needed correction. To illustrate, let's dissect some peer-reviewed lock-free code that was published here in DDJ just two months ago [2]. The author, Petru Marginean, has graciously allowed me to dissect it here so that we can see what's wrong and why, what lessons we should learn, and how to write the code correctly. That someone as knowledgable as Petru, who has published many good and solid articles, can get this stuff wrong should be warning enough that lock-free coding requires great care."
- 12y ago