3 ms·
The last time I had to write a lock-free algorithm (in this case, a multi-writer, multi-reader queue), the memory reclamation strategy was straightforward: Mak
by jnwatson 9y ago
The last time I had to write a lock-free algorithm (in this case, a multi-writer, multi-reader queue), the memory reclamation strategy was straightforward:
Make 2 lock-free queues. Pre-allocate all the memory into message-sized chunks, and post them to the "upwards" queue. A writer would read/consume from the upwards queue, write into the received buffer, and then post the same buffer in the other queue. Everything is passed by reference, so it is zero-copy.
I guess I don't understand the reason for all the complexity. Perhaps for more complicated algorithms than queues?
- barrkel 9y agoIf you preallocate memory, you're not reclaiming it, are you?
- jnwatson 9y agoSure, I'm reclaiming it for future writers.
- kasey_junk 9y agoWhat do you do when your queue is full?
- jnwatson 9y agoBlock. Lock-free doesn't imply infinite RAM.
- kasey_junk 9y agoWait freedom does though, the article is about both. In wait free queues memory reclamation is the hard part in practice (most wait free queues are actually much slower than their locked or lock free counterparts). Here is a great paper describing how the memory reclamation strategy was central to speeding up their implementation: http://chaoran.me/assets/pdf/wfq-ppopp16.pdf http://chaoran.me/assets/pdf/wfq-ppopp16.pdf
- anarazel 9y agoDepending on your implementation (hard to say given the detail provided) you're quite possibly running into ABA style problems with such an such an approach. If you use cmpxchg and rely on pointer identity it could be that you see the same pointer, but in its reused form...