"Chris M. Thomasson" <cristom@charter.net> wrote in message news:hgfqaj$k90$1@ger.gmane.org...
"Helge Bahmann" <hcb@chaoticmind.net> wrote in message news:alpine.DEB.1.10.0912101115460.456@m65s28.vlinux.de...
On Wed, 9 Dec 2009, Anthony Williams wrote:
So far I have not yet met any 64-bit platform that provides 64 bits of (user-space!) address space (the same cannot be said of 32-bit platforms), so I would say that any use of spare bits on 64 bit is safe (for user-space!).
As Chris also noted, I would be wary of using them for ABA checking though: it's easy to overflow a 16-bit counter quite quickly, and that's all you've got even if the OS only uses 48 of your 64 bits for address space.
This concern is certainly valid for basically any algorithm that uses "generation counters" or similar constructs for disambiguation (it could be argued that even 32 bits may not be enough). Using spare bits at all should however be considered a valid technique.
FWIW there are other ways to avoid ABA than tagging pointers, and without DCAS on 32-bit, see e.g. this sample implementation of a lock-free stack:
http://www.chaoticmind.net/~hcb/projects/boost.atomic/stack.hpp
Yup. Incidentally, you don't even need to count the nodes in push, provided you're careful when reclaiming nodes in pop.
hm, I'm not sure what you mean, I don't think I am counting anything but the number of threads in the critical section?
The downside of this technique is that if the traffic is too heavy then the ref count never reaches zero, so the nodes can never be reclaimed.
Right, and although I would argue that such a highly contended hotspot is a design flaw in itself,
You have created a proxy garbage collector that reminds me of one I did a long time ago which also suffered from this exact same problem.
FWIW Helge, here is a new proxy garbage collector algorithm of mine that I am currently experimenting with: http://groups.google.com/group/comp.programming.threads/browse_frm/thread/a5... is basically a simplified version of the following lock-free algorithm: http://webpages.charter.net/appcore/misc/pc_sample_h_v1.html The new algorihtm is a *wait-free solution to the ABA problem and memory reclamation issues in general wrt non-blocking algorithms. The usage pattern is basically identical to you're collector wrt the following code: http://www.chaoticmind.net/~hcb/projects/boost.atomic/stack.hpp you do it like: __________________________________________________________________ bool pop(T &data) throw() { enter_crit(); node * n=stack.pop(); if (n) { data=n->data; expired.push(n); } leave_crit(); return n!=0; } ___________________________________________________________________ The equivalent code for my collector would be: ___________________________________________________________________ bool pop(T& data) throw() { proxy_type::collector& c = m_proxy.acquire(); node* n = m_stack.pop(); if (n) { data = n->m_data; m_proxy.collect(c, n); } m_proxy.release(c); return (n != NULL); } ___________________________________________________________________ [*] The algorithm is wait-free in practice on systems with native fetch-and-add and swap instructions like x86-32/64. If the architecture forces you to implement fetch-and-add with a damn LL/SC or CAS loop, well, then it's not really wait-free now is it? No, I am afraid it's lock-free, or whatever semantics the LL/SC is which could even be obstruction-free. Sad... ;^(...