Properly Testing Concurrent Data Structures
There's a fascinating Rust library, loom, which can be used to thoroughly test lock-free data structures. I always wanted to learn how it works. I still do! But recently I accidentally implemented a small toy which, I think, contains some of the loom's ideas, and it seems worthwhile to write about t...
Hasnain says:
“And this is how you properly test concurrent data structures.
Postscript
Of course, this is just a toy. But you can see some ways to extend it. For example, right now our AtomicU32 just delegates to the real one. But what you could do instead is, for each atomic, to maintain a set of values written and, on read, return an arbitrary written value consistent with a weak memory model.
You could also be smarter with exploring interleavings. Instead of interleaving threads at random, like we do here, you can try to apply model checking approaches and prove that you have considered all meaningfully different interleavings.
Or you can apply the approach from Generate All The Things and exhaustively enumerate all interleavings for up to, say, five increments. In fact, why don’t we just do this?”
Posted on 2024-07-14T01:18:39+0000