4 ms·
FSM’s are a good way to think about any problem you’d like to address lock-free, since they map so well to CAS.
by twoodfin 9y ago
FSM’s are a good way to think about any problem you’d like to address lock-free, since they map so well to CAS.
- eternalban 9y agoHis FSM is a bit more elaborate than merely modeling a CAS. 3 states, if I recall correctly. [edit: https://web.stanford.edu/class/ee380/Abstracts/070221_LockFreeHash.pdf https://web.stanford.edu/class/ee380/Abstracts/070221_LockFr... See page 32]
- twoodfin 9y agoRight, but you can implement atomic state transitions quite naturally with CAS.
- eternalban 9y agoI suggest you actually listen to Cliff explain why he did what he did before you belabor the obvious. (Those state transitios are all CASed ..)
- twoodfin 9y agoI have no idea what you think we’re disagreeing about. I’ve watched Cliff’s presentation a handful of times over the past decade and implemented something similar (albeit simpler) myself. Yes, the particular FSM in his hash table is interesting and novel, but just as insightful to me was his argument that data structures implemented as state machines built on atomic CAS can save you much of the trouble of proving you’ve put memory barriers in the right places. “All” you have to do is demonstrate that every possible state is valid.