Re: why ConcurrentLinkedQueue#addAll need set tail twice?

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, <
[email protected]> 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
> [email protected]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>

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