4 ms·
Pointer compression is a pretty nifty and simple optimization. While working on a high-performance wait-free MPSC queue, pointer compression allowed me to fit
by dist1ll 4y ago
Pointer compression is a pretty nifty and simple optimization.
While working on a high-performance wait-free MPSC queue, pointer compression allowed me to fit the tails of each ring buffer queue together into a single cache line, reducing cache pressure and cache coherency traffic. The tails were essentially 16-bit compressed indices, storing the offset from the backing array's base address.
Cool post!
- deleted 4y ago[deleted]
- pclmulqdq 4y agoPointer compression lets you do so much cheating in lock-free and wait-free data structures. A 16-byte CAS can now operate on 4+ values instead of just ~2, and you can conceivably use an 8-byte object for both a pointer and a counter (an ABA counter, perhaps) so you can use things like XCHG and XADD instead of CAS for operations that don't actually need a CAS loop.
- gavinray 4y agoDo you have a pseudo-code example of this? It sounds neat: > A 16-byte CAS can now operate on 4+ values instead of just ~2, and you can conceivably use an 8-byte object for both a pointer and a counter (an ABA counter, perhaps) so you can use things like XCHG and XADD instead of CAS for operations that don't actually need a CAS loop.
- pclmulqdq 4y agoNot without breaking any NDAs.
- gavinray 4y agoFair enough! I'd be interested if Github Copilot can take this as a prompt and spit out C/C++ for it...
- gavinray 4y agoThis is what it spit out, if anyone is curious (best of them, from what I could tell, I dunno much about concurrent programming but this looked the most reasonable to me): I started by typing this: template <typename T> struct uint64_compressed_ptr_and_counter This is one of the implementations it generated: https://godbolt.org/z/hbfY6GPzo https://godbolt.org/z/hbfY6GPzo I don't think this is correct since it doesn't use CAS/atomics but it's certainly interesting. Comments that it generated for the classes: // This is a lock-free stack that uses pointer compression to store a counter // and a tag in the pointer. The tag is used to indicate whether the stack is // empty or not, and the counter is used to detect ABA problems. template <typename T> class uint64_compressed_ptr_and_counter_stack
- pclmulqdq 4y agoThat's funny - it's far from correct, but it looks like a lot of lock free data structures in an aesthetic sense.
- deleted 4y ago[deleted]