I want intrusive versions of stack/queue. The freelist could also be made to use the stack. In my design I did make the free list allocator use the stack. The stack assumes that its nodes are intrusive style. However, I have never seen published an intrusive queue. The Micheal Scott queue relies on dummy nodes, where the last node dequed serves as the new dummy node, the previous one being freed. This makes it difficult (or impossible) to make the nodes intrusive.
A simple freelist allocator that grabs blocks in pages would be fantastic in a lot of cases. The one I have does this. The drawback is that it make pointer compression difficult. Compression is a good way to solve many ABA problems on architectures where CAS2 is not available. A compressing allocator/pointer pair would be required for any hope of portability. Of course, noncompressing version should be available for platofrm that could support it (such as Intel) The algo works inefficiently on IA64 because it copies the pointer when IA64 only needs to copy the ABA counter >(it has cmp8xchg16b). I have not seen an algorithm published that makes use of cmp8xchg16b. Most algs I have seen want to swap both the pointer and the count, and not just the pointer if the count is different.
-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Cory Nelson Sent: Monday, April 28, 2008 5:06 PM To: boost@lists.boost.org Subject: Re: [boost] boost.lockfree proposal On Mon, Apr 28, 2008 at 11:25 AM, Tim Blechmann <tim@klingt.org> wrote:
hi all,
i would be curious, if some people might want to work together in order to implement a boost-style lockfree library ...
I'd be interested in contributing. This seems well designed already, but I see some improvements: I want intrusive versions of stack/queue. The freelist could also be made to use the stack. The allocator should put blocks on cache-line boundaries. A simple freelist allocator that grabs blocks in pages would be fantastic in a lot of cases. The algo works inefficiently on IA64 because it copies the pointer when IA64 only needs to copy the ABA counter (it has cmp8xchg16b). This can be reworked to have a tagged_ptr<>::cmp_type instead of comparing with another tagged_ptr. CAS on x86 will give you the old value if it fails. CAS should be changed to modify the compare arg, so you can write a loop without constantly loading the destination: cmp_type cmp = dest; do { ... } while(!CAS(dest, exch, cmp)); -- Cory Nelson _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost Visit our website at http://www.ubs.com This message contains confidential information and is intended only for the individual named. If you are not the named addressee you should not disseminate, distribute or copy this e-mail. Please notify the sender immediately by e-mail if you have received this e-mail by mistake and delete this e-mail from your system. E-mails are not encrypted and cannot be guaranteed to be secure or error-free as information could be intercepted, corrupted, lost, destroyed, arrive late or incomplete, or contain viruses. The sender therefore does not accept liability for any errors or omissions in the contents of this message which arise as a result of e-mail transmission. If verification is required please request a hard-copy version. This message is provided for informational purposes and should not be construed as a solicitation or offer to buy or sell any securities or related financial instruments.