Re: [boost] boost.lockfree proposal

From: Lance.Diduck_at_[hidden]
Date: 2008-04-28 18:26:43

 >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_at_[hidden]
[mailto:boost-bounces_at_[hidden]] On Behalf Of Cory Nelson
Sent: Monday, April 28, 2008 5:06 PM
To: boost_at_[hidden]
Subject: Re: [boost] boost.lockfree proposal

On Mon, Apr 28, 2008 at 11:25 AM, Tim Blechmann <tim_at_[hidden]> 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.