why ConcurrentLinkedQueue#addAll need set tail twice?

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

why ConcurrentLinkedQueue#addAll need set tail twice?

JSR166 Concurrency mailing list
In JDK8's ConcurrentLinkedQueue, there is an addAll function, and it will set tail twice, why?

public boolean addAll(Collection<? extends E> c) {
if (c == this)
// As historically specified in AbstractQueue#addAll
throw new IllegalArgumentException();

// Copy c into a private chain of Nodes
Node<E> beginningOfTheEnd = null, last = null;
for (E e : c) {
checkNotNull(e);
Node<E> newNode = new Node<E>(e);
if (beginningOfTheEnd == null)
beginningOfTheEnd = last = newNode;
else {
last.lazySetNext(newNode);
last = newNode;
}
}
if (beginningOfTheEnd == null)
return false;

// Atomically append the chain at the tail of this collection
for (Node<E> t = tail, p = t;;) {
Node<E> q = p.next;
if (q == null) {
// p is last node
if (p.casNext(null, beginningOfTheEnd)) {
// Successful CAS is the linearization point
// for all elements to be added to this queue.
if (!casTail(t, last)) { // first set tail
// Try a little harder to update tail,
// since we may be adding many elements.
t = tail;
if (last.next == null)
casTail(t, last); // second set tail
}
return true;
}
// Lost CAS race to another thread; re-read next
}
else if (p == q)
// We have fallen off list. If tail is unchanged, it
// will also be off-list, in which case we need to
// jump to head, from which all live nodes are always
// reachable. Else the new tail is a better bet.
p = (t != (t = tail)) ? t : head;
else
// Check for tail updates after two hops.
p = (p != t && t != (t = tail)) ? t : q;
}
}

I don't quite understand, I just think the second set operation is not necessary.
--------------------------------------------------------------------------------
Regards
Liu 

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

Re: why ConcurrentLinkedQueue#addAll need set tail twice?

JSR166 Concurrency mailing list
I assume you are talking about casTail just before returning.

It will set tail at most once.

Observe that it returns true disregarding the result of casTail. It means the queue works correctly even if you don't update the tail at all.

From this we can conclude it is an optimisation to help others do less work, e.g. scan less of the queue to find an insertion point.

Then you can also see the second casTail is attempted only if the first one fails. So it isn't done twice. But the second attempt may fail too - this only means someone will hit a _slightly_ slower path, because you fail to set the tail only when someone else succeded - presumably setting the tail close enough to the end of the queue.

Alex

On Thu, 23 Jul 2020, 14:41 Liu via Concurrency-interest, <[hidden email]> wrote:
In JDK8's ConcurrentLinkedQueue, there is an addAll function, and it will set tail twice, why?

public boolean addAll(Collection<? extends E> c) {
if (c == this)
// As historically specified in AbstractQueue#addAll
throw new IllegalArgumentException();

// Copy c into a private chain of Nodes
Node<E> beginningOfTheEnd = null, last = null;
for (E e : c) {
checkNotNull(e);
Node<E> newNode = new Node<E>(e);
if (beginningOfTheEnd == null)
beginningOfTheEnd = last = newNode;
else {
last.lazySetNext(newNode);
last = newNode;
}
}
if (beginningOfTheEnd == null)
return false;

// Atomically append the chain at the tail of this collection
for (Node<E> t = tail, p = t;;) {
Node<E> q = p.next;
if (q == null) {
// p is last node
if (p.casNext(null, beginningOfTheEnd)) {
// Successful CAS is the linearization point
// for all elements to be added to this queue.
if (!casTail(t, last)) { // first set tail
// Try a little harder to update tail,
// since we may be adding many elements.
t = tail;
if (last.next == null)
casTail(t, last); // second set tail
}
return true;
}
// Lost CAS race to another thread; re-read next
}
else if (p == q)
// We have fallen off list. If tail is unchanged, it
// will also be off-list, in which case we need to
// jump to head, from which all live nodes are always
// reachable. Else the new tail is a better bet.
p = (t != (t = tail)) ? t : head;
else
// Check for tail updates after two hops.
p = (p != t && t != (t = tail)) ? t : q;
}
}

I don't quite understand, I just think the second set operation is not necessary.
--------------------------------------------------------------------------------
Regards
Liu 
_______________________________________________
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: why ConcurrentLinkedQueue#addAll need set tail twice?

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
     * - There is exactly one (last) Node with a null next reference,
     *   which is CASed when enqueueing.  This last Node can be
     *   reached in O(1) time from tail, but tail is merely an
     *   optimization - it can always be reached in O(N) time from
     *   head as well.

On Thu, Jul 23, 2020 at 6:41 AM Liu via Concurrency-interest
<[hidden email]> wrote:

>
> In JDK8's ConcurrentLinkedQueue, there is an addAll function, and it will set tail twice, why?
>
> public boolean addAll(Collection<? extends E> c) {
>     if (c == this)
>         // As historically specified in AbstractQueue#addAll
>         throw new IllegalArgumentException();
>
>     // Copy c into a private chain of Nodes
>     Node<E> beginningOfTheEnd = null, last = null;
>     for (E e : c) {
>         checkNotNull(e);
>         Node<E> newNode = new Node<E>(e);
>         if (beginningOfTheEnd == null)
>             beginningOfTheEnd = last = newNode;
>         else {
>             last.lazySetNext(newNode);
>             last = newNode;
>         }
>     }
>     if (beginningOfTheEnd == null)
>         return false;
>
>     // Atomically append the chain at the tail of this collection
>     for (Node<E> t = tail, p = t;;) {
>         Node<E> q = p.next;
>         if (q == null) {
>             // p is last node
>             if (p.casNext(null, beginningOfTheEnd)) {
>                 // Successful CAS is the linearization point
>                 // for all elements to be added to this queue.
>                 if (!casTail(t, last)) {  // first set tail
>                     // Try a little harder to update tail,
>                     // since we may be adding many elements.
>                     t = tail;
>                     if (last.next == null)
>                         casTail(t, last);  // second set tail
>                 }
>                 return true;
>             }
>             // Lost CAS race to another thread; re-read next
>         }
>         else if (p == q)
>             // We have fallen off list.  If tail is unchanged, it
>             // will also be off-list, in which case we need to
>             // jump to head, from which all live nodes are always
>             // reachable.  Else the new tail is a better bet.
>             p = (t != (t = tail)) ? t : head;
>         else
>             // Check for tail updates after two hops.
>             p = (p != t && t != (t = tail)) ? t : q;
>     }
> }
>
>
> I don't quite understand, I just think the second set operation is not necessary.
> --------------------------------------------------------------------------------
> Regards
> Liu
> _______________________________________________
> 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: why ConcurrentLinkedQueue#addAll need set tail twice?

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
Thanks for answer. I understand now. 

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