Non-blocking Allocation-free Concurrent Stack

classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

Non-blocking Allocation-free Concurrent Stack

JSR166 Concurrency mailing list
One can use ConcurentLinkedDeque as a stack by using addFirst() and
pollFirst().  However, each addFirst() call creates a
ConcurrentLinkedDeque.Node object.

I tried embedding the Node into the data stored in the stack. However, I
run into the ABA problem where one thread holds a reference to the top's
next while other threads pop the top, change the stack and push the
top.  The next reference is now invalid.  I solved this using an
AtomicStampedReference; however, this means addFirst() allocates with
every call.

Where can I find a non-blocking allocation-free concurrent stack
implementation?  Where can I find "documentation" on how to build such a
stack?

--
-Nathan

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Non-blocking Allocation-free Concurrent Stack

JSR166 Concurrency mailing list
You don't need any complex data structure for a concurrent stack,
particularly if you've embedded the "next" pointer in the data.  You
can do it simply in any class like this pseudocode:

AtomicReference<Node> top;

// push an item on the stack

oldTop = top.get();
node.next = oldTop;
while (! top.compareAndSet(oldTop, node)) {
    onSpinWait(); // optional
    oldTop = top.get();
    node.next = oldTop;
}

// pop an item off the stack

node = top.get();
newTop = node.next;
while (! top.compareAndSet(node, newTop)) {
    onSpinWait(); // optional
    node = top.get();
    newTop = node.next;
}

The 'top' field can be a volatile with Atomic*Updater or VarHandle, or
even Unsafe if you wanted to, but the algorithm is basically the same.
The key point is to freeze "node.next" when the value is successfully
put on the stack.

On Tue, Jan 8, 2019 at 2:45 PM Nathan and Ila Reynolds via
Concurrency-interest <[hidden email]> wrote:

>
> One can use ConcurentLinkedDeque as a stack by using addFirst() and
> pollFirst().  However, each addFirst() call creates a
> ConcurrentLinkedDeque.Node object.
>
> I tried embedding the Node into the data stored in the stack. However, I
> run into the ABA problem where one thread holds a reference to the top's
> next while other threads pop the top, change the stack and push the
> top.  The next reference is now invalid.  I solved this using an
> AtomicStampedReference; however, this means addFirst() allocates with
> every call.
>
> Where can I find a non-blocking allocation-free concurrent stack
> implementation?  Where can I find "documentation" on how to build such a
> stack?
>
> --
> -Nathan
>
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest



--
- DML
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Non-blocking Allocation-free Concurrent Stack

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
You have some unusual use-case in mind.

Alex

> On 8 Jan 2019, at 20:42, Nathan and Ila Reynolds via Concurrency-interest <[hidden email]> wrote:
>
> One can use ConcurentLinkedDeque as a stack by using addFirst() and pollFirst().  However, each addFirst() call creates a ConcurrentLinkedDeque.Node object.
>
> I tried embedding the Node into the data stored in the stack. However, I run into the ABA problem where one thread holds a reference to the top's next while other threads pop the top, change the stack and push the top.  The next reference is now invalid.  I solved this using an AtomicStampedReference; however, this means addFirst() allocates with every call.
>
> Where can I find a non-blocking allocation-free concurrent stack implementation?  Where can I find "documentation" on how to build such a stack?
>
> --
> -Nathan
>
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Non-blocking Allocation-free Concurrent Stack

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
David is referring to

It would occasionally be useful to offer versions of Node-based data structures that exposed and returned Nodes and allowed users to create Nodes containing user data.

ConcurentLinkedDeque is designed so that previous and next pointers can always be followed, even in the presence of concurrent modification, since that is needed for iterators, but trickery is required.  Nodes can never be reused - some other thread may still be in the middle of a traversal even after the Node is removed.


On Tue, Jan 8, 2019 at 12:45 PM Nathan and Ila Reynolds via Concurrency-interest <[hidden email]> wrote:
One can use ConcurentLinkedDeque as a stack by using addFirst() and
pollFirst().  However, each addFirst() call creates a
ConcurrentLinkedDeque.Node object.

I tried embedding the Node into the data stored in the stack. However, I
run into the ABA problem where one thread holds a reference to the top's
next while other threads pop the top, change the stack and push the
top.  The next reference is now invalid.  I solved this using an
AtomicStampedReference; however, this means addFirst() allocates with
every call.

Where can I find a non-blocking allocation-free concurrent stack
implementation?  Where can I find "documentation" on how to build such a
stack?

--
-Nathan

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Non-blocking Allocation-free Concurrent Stack

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
That code suffers from the ABA problem.  Here is how that could happen.

1) Thread 1 executes node = top.get();
2) Thread 1 executes newTop = node.next;
3) Thread 2 executes the entire pop()
4) Thread 2 executes push() for some new value
5) Thread 2 executes push() with the value from step #3
6) Thread 1 executes top.compareAndSet(node, newTop).  This loses the
value from step #4.

Do you have any ideas on how to fix this without incurring an allocation?

I thought about using AtomicStampedReference for top but compareAndSet()
allocates an object.

-Nathan

On 1/8/2019 2:32 PM, David Lloyd wrote:

> You don't need any complex data structure for a concurrent stack,
> particularly if you've embedded the "next" pointer in the data.  You
> can do it simply in any class like this pseudocode:
>
> AtomicReference<Node> top;
>
> // push an item on the stack
>
> oldTop = top.get();
> node.next = oldTop;
> while (! top.compareAndSet(oldTop, node)) {
>      onSpinWait(); // optional
>      oldTop = top.get();
>      node.next = oldTop;
> }
>
> // pop an item off the stack
>
> node = top.get();
> newTop = node.next;
> while (! top.compareAndSet(node, newTop)) {
>      onSpinWait(); // optional
>      node = top.get();
>      newTop = node.next;
> }
>
> The 'top' field can be a volatile with Atomic*Updater or VarHandle, or
> even Unsafe if you wanted to, but the algorithm is basically the same.
> The key point is to freeze "node.next" when the value is successfully
> put on the stack.
>
> On Tue, Jan 8, 2019 at 2:45 PM Nathan and Ila Reynolds via
> Concurrency-interest <[hidden email]> wrote:
>> One can use ConcurentLinkedDeque as a stack by using addFirst() and
>> pollFirst().  However, each addFirst() call creates a
>> ConcurrentLinkedDeque.Node object.
>>
>> I tried embedding the Node into the data stored in the stack. However, I
>> run into the ABA problem where one thread holds a reference to the top's
>> next while other threads pop the top, change the stack and push the
>> top.  The next reference is now invalid.  I solved this using an
>> AtomicStampedReference; however, this means addFirst() allocates with
>> every call.
>>
>> Where can I find a non-blocking allocation-free concurrent stack
>> implementation?  Where can I find "documentation" on how to build such a
>> stack?
>>
>> --
>> -Nathan
>>
>> _______________________________________________
>> Concurrency-interest mailing list
>> [hidden email]
>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
>
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Non-blocking Allocation-free Concurrent Stack

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
Currently, I am using ConcurrentLinkedDeque as a stack.  The heavy use
creates a lot of allocations which in turns triggers a lot of GCs and
hence consumes a lot of CPU time.  So, I am looking for a stack that
does not allocate on the common path.

-Nathan

On 1/8/2019 2:49 PM, Alex Otenko wrote:

> You have some unusual use-case in mind.
>
> Alex
>
>> On 8 Jan 2019, at 20:42, Nathan and Ila Reynolds via Concurrency-interest <[hidden email]> wrote:
>>
>> One can use ConcurentLinkedDeque as a stack by using addFirst() and pollFirst().  However, each addFirst() call creates a ConcurrentLinkedDeque.Node object.
>>
>> I tried embedding the Node into the data stored in the stack. However, I run into the ABA problem where one thread holds a reference to the top's next while other threads pop the top, change the stack and push the top.  The next reference is now invalid.  I solved this using an AtomicStampedReference; however, this means addFirst() allocates with every call.
>>
>> Where can I find a non-blocking allocation-free concurrent stack implementation?  Where can I find "documentation" on how to build such a stack?
>>
>> --
>> -Nathan
>>
>> _______________________________________________
>> Concurrency-interest mailing list
>> [hidden email]
>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Non-blocking Allocation-free Concurrent Stack

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list

Thanks for the link.  I am wondering if a Treiber stack can be modified so that nothing is allocated in push() or pop().  My first attempt ran into the ABA problem.

-Nathan
On 1/8/2019 2:51 PM, Martin Buchholz wrote:
David is referring to

It would occasionally be useful to offer versions of Node-based data structures that exposed and returned Nodes and allowed users to create Nodes containing user data.

ConcurentLinkedDeque is designed so that previous and next pointers can always be followed, even in the presence of concurrent modification, since that is needed for iterators, but trickery is required.  Nodes can never be reused - some other thread may still be in the middle of a traversal even after the Node is removed.


On Tue, Jan 8, 2019 at 12:45 PM Nathan and Ila Reynolds via Concurrency-interest <[hidden email]> wrote:
One can use ConcurentLinkedDeque as a stack by using addFirst() and
pollFirst().  However, each addFirst() call creates a
ConcurrentLinkedDeque.Node object.

I tried embedding the Node into the data stored in the stack. However, I
run into the ABA problem where one thread holds a reference to the top's
next while other threads pop the top, change the stack and push the
top.  The next reference is now invalid.  I solved this using an
AtomicStampedReference; however, this means addFirst() allocates with
every call.

Where can I find a non-blocking allocation-free concurrent stack
implementation?  Where can I find "documentation" on how to build such a
stack?

--
-Nathan

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Non-blocking Allocation-free Concurrent Stack

JSR166 Concurrency mailing list
You can reduce allocations by using elimination arenas to attempt an exchange, which is helpful to avoid contention on the top of the stack by canceling operations. Most often contention is a bigger concern than the allocation rate of a concurrent stack.

I have some old code that did this, but dropped it because I found a race in the combining logic (where producers combined such that only one pushed multiple nodes in a single shot) and I no longer had a use-case to be worth trying to fix it.

On Tue, Jan 8, 2019 at 1:56 PM Nathan and Ila Reynolds via Concurrency-interest <[hidden email]> wrote:

Thanks for the link.  I am wondering if a Treiber stack can be modified so that nothing is allocated in push() or pop().  My first attempt ran into the ABA problem.

-Nathan
On 1/8/2019 2:51 PM, Martin Buchholz wrote:
David is referring to

It would occasionally be useful to offer versions of Node-based data structures that exposed and returned Nodes and allowed users to create Nodes containing user data.

ConcurentLinkedDeque is designed so that previous and next pointers can always be followed, even in the presence of concurrent modification, since that is needed for iterators, but trickery is required.  Nodes can never be reused - some other thread may still be in the middle of a traversal even after the Node is removed.


On Tue, Jan 8, 2019 at 12:45 PM Nathan and Ila Reynolds via Concurrency-interest <[hidden email]> wrote:
One can use ConcurentLinkedDeque as a stack by using addFirst() and
pollFirst().  However, each addFirst() call creates a
ConcurrentLinkedDeque.Node object.

I tried embedding the Node into the data stored in the stack. However, I
run into the ABA problem where one thread holds a reference to the top's
next while other threads pop the top, change the stack and push the
top.  The next reference is now invalid.  I solved this using an
AtomicStampedReference; however, this means addFirst() allocates with
every call.

Where can I find a non-blocking allocation-free concurrent stack
implementation?  Where can I find "documentation" on how to build such a
stack?

--
-Nathan

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Non-blocking Allocation-free Concurrent Stack

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
You could maybe use a one-bit spin lock for mutual exclusion instead
of CAS, which would guarantee a clean handoff of ownership between a
pushing and popping thread.  If you're not doing allocation, then the
critical section should only be a couple of field accesses.

On Tue, Jan 8, 2019 at 3:51 PM Nathan and Ila Reynolds
<[hidden email]> wrote:

>
> That code suffers from the ABA problem.  Here is how that could happen.
>
> 1) Thread 1 executes node = top.get();
> 2) Thread 1 executes newTop = node.next;
> 3) Thread 2 executes the entire pop()
> 4) Thread 2 executes push() for some new value
> 5) Thread 2 executes push() with the value from step #3
> 6) Thread 1 executes top.compareAndSet(node, newTop).  This loses the
> value from step #4.
>
> Do you have any ideas on how to fix this without incurring an allocation?
>
> I thought about using AtomicStampedReference for top but compareAndSet()
> allocates an object.
>
> -Nathan
>
> On 1/8/2019 2:32 PM, David Lloyd wrote:
> > You don't need any complex data structure for a concurrent stack,
> > particularly if you've embedded the "next" pointer in the data.  You
> > can do it simply in any class like this pseudocode:
> >
> > AtomicReference<Node> top;
> >
> > // push an item on the stack
> >
> > oldTop = top.get();
> > node.next = oldTop;
> > while (! top.compareAndSet(oldTop, node)) {
> >      onSpinWait(); // optional
> >      oldTop = top.get();
> >      node.next = oldTop;
> > }
> >
> > // pop an item off the stack
> >
> > node = top.get();
> > newTop = node.next;
> > while (! top.compareAndSet(node, newTop)) {
> >      onSpinWait(); // optional
> >      node = top.get();
> >      newTop = node.next;
> > }
> >
> > The 'top' field can be a volatile with Atomic*Updater or VarHandle, or
> > even Unsafe if you wanted to, but the algorithm is basically the same.
> > The key point is to freeze "node.next" when the value is successfully
> > put on the stack.
> >
> > On Tue, Jan 8, 2019 at 2:45 PM Nathan and Ila Reynolds via
> > Concurrency-interest <[hidden email]> wrote:
> >> One can use ConcurentLinkedDeque as a stack by using addFirst() and
> >> pollFirst().  However, each addFirst() call creates a
> >> ConcurrentLinkedDeque.Node object.
> >>
> >> I tried embedding the Node into the data stored in the stack. However, I
> >> run into the ABA problem where one thread holds a reference to the top's
> >> next while other threads pop the top, change the stack and push the
> >> top.  The next reference is now invalid.  I solved this using an
> >> AtomicStampedReference; however, this means addFirst() allocates with
> >> every call.
> >>
> >> Where can I find a non-blocking allocation-free concurrent stack
> >> implementation?  Where can I find "documentation" on how to build such a
> >> stack?
> >>
> >> --
> >> -Nathan
> >>
> >> _______________________________________________
> >> Concurrency-interest mailing list
> >> [hidden email]
> >> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
> >
> >



--
- DML
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest