Concurrent Queue Sizes and Hot Fields

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

Concurrent Queue Sizes and Hot Fields

JSR166 Concurrency mailing list
Most likely too basic for this audience ... :-)

Abstract: ConcurrentLinkedQueue's size() method is not very useful in a
multi-threaded environment, because it counts the number of elements in
the queue, rather than relying on a "hot field" to store the size. The
result might be completely incorrect, or in strange situations, never
return.

Full article: https://www.javaspecialists.eu/archive/Issue261.html

Regards

Heinz
--
Dr Heinz M. Kabutz (PhD CompSci)
Author of "The Java™ Specialists' Newsletter" - www.javaspecialists.eu
Java Champion - www.javachampions.org
Oracle Developer Champion - www.twitter.com/dev_champions
JavaOne Rock Star - www.oracle.com/javaone/rock-star-wall-of-fame.html
Tel: +30 69 75 595 262
Skype: kabutz


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

Re: Concurrent Queue Sizes and Hot Fields

JSR166 Concurrency mailing list
Hi Heinz,

Thanks for the article.  How can we do better?  The problem affects
all methods that iterate over a concurrent queue, so not just size()
but also contains(), toArray().  We surely want all these methods to
return the correct result when the queue is quiescent.  The semantics
of the current implementation  "traverse all elements from head until
the end is found" are pretty intuitive.  It wouldn't work to first
find the last node, then traverse from head until the last node is
encountered, because there is no guarantee this node will remain in
the queue.

If it was important to fix, we can probably do it with heroic effort
and a tax on the dequeue methods.  First enqueue a special end marker
node that will only be unlinked by the traversing method.  (harder
than it sounds!)

Users can work-around by creating a subclass maintaining a count in a LongAdder.

On Thu, Sep 20, 2018 at 8:32 AM, Dr Heinz M. Kabutz via
Concurrency-interest <[hidden email]> wrote:

> Most likely too basic for this audience ... :-)
>
> Abstract: ConcurrentLinkedQueue's size() method is not very useful in a
> multi-threaded environment, because it counts the number of elements in the
> queue, rather than relying on a "hot field" to store the size. The result
> might be completely incorrect, or in strange situations, never return.
>
> Full article: https://www.javaspecialists.eu/archive/Issue261.html
>
> Regards
>
> Heinz
> --
> Dr Heinz M. Kabutz (PhD CompSci)
> Author of "The Java™ Specialists' Newsletter" - www.javaspecialists.eu
> Java Champion - www.javachampions.org
> Oracle Developer Champion - www.twitter.com/dev_champions
> JavaOne Rock Star - www.oracle.com/javaone/rock-star-wall-of-fame.html
> Tel: +30 69 75 595 262
> Skype: kabutz
>
>
> _______________________________________________
> 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: Concurrent Queue Sizes and Hot Fields

JSR166 Concurrency mailing list
I am baffled by the suggestions both to use size() in any circumstances, and to use LongAdder.

What use is the size() in a concurrent setting? It can only be an estimate, and any implementation on top of the current ConcurrentLinkedQueue will permit invalid values, including negative size, unless the queue updates the count atomically with adding or removing an element.

Alex

On 22 Sep 2018, at 21:32, Martin Buchholz via Concurrency-interest <[hidden email]> wrote:

Hi Heinz,

Thanks for the article.  How can we do better?  The problem affects
all methods that iterate over a concurrent queue, so not just size()
but also contains(), toArray().  We surely want all these methods to
return the correct result when the queue is quiescent.  The semantics
of the current implementation  "traverse all elements from head until
the end is found" are pretty intuitive.  It wouldn't work to first
find the last node, then traverse from head until the last node is
encountered, because there is no guarantee this node will remain in
the queue.

If it was important to fix, we can probably do it with heroic effort
and a tax on the dequeue methods.  First enqueue a special end marker
node that will only be unlinked by the traversing method.  (harder
than it sounds!)

Users can work-around by creating a subclass maintaining a count in a LongAdder.

On Thu, Sep 20, 2018 at 8:32 AM, Dr Heinz M. Kabutz via
Concurrency-interest <[hidden email]> wrote:
Most likely too basic for this audience ... :-)

Abstract: ConcurrentLinkedQueue's size() method is not very useful in a
multi-threaded environment, because it counts the number of elements in the
queue, rather than relying on a "hot field" to store the size. The result
might be completely incorrect, or in strange situations, never return.

Full article: https://www.javaspecialists.eu/archive/Issue261.html

Regards

Heinz
--
Dr Heinz M. Kabutz (PhD CompSci)
Author of "The Java™ Specialists' Newsletter" - www.javaspecialists.eu
Java Champion - www.javachampions.org
Oracle Developer Champion - www.twitter.com/dev_champions
JavaOne Rock Star - www.oracle.com/javaone/rock-star-wall-of-fame.html
Tel: +30 69 75 595 262
Skype: kabutz


_______________________________________________
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: Concurrent Queue Sizes and Hot Fields

JSR166 Concurrency mailing list
On Sat, Sep 22, 2018 at 2:53 PM, Alex Otenko <[hidden email]> wrote:
> What use is the size() in a concurrent setting? It can only be an estimate

Some library methods call size(), in the hope that it might optimize
some other code.

Even when size() is only an estimate, it may be useful.

Surely we would want size() to never return a negative value (we
probably have buglets where size overflows 32-bit).
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Concurrent Queue Sizes and Hot Fields

JSR166 Concurrency mailing list
Right.

If the counter update is not atomic with the adding/removing of the elements, then you may get to add an element, then remove the element, then reduce the count as part of removing, then read a negative size(), and only then increment the count as part of the adding.


Alex

> On 22 Sep 2018, at 23:12, Martin Buchholz <[hidden email]> wrote:
>
> On Sat, Sep 22, 2018 at 2:53 PM, Alex Otenko <[hidden email]> wrote:
>> What use is the size() in a concurrent setting? It can only be an estimate
>
> Some library methods call size(), in the hope that it might optimize
> some other code.
>
> Even when size() is only an estimate, it may be useful.
>
> Surely we would want size() to never return a negative value (we
> probably have buglets where size overflows 32-bit).

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

Re: Concurrent Queue Sizes and Hot Fields

JSR166 Concurrency mailing list
We could increment before actually adding.  Both queues where this would apply are unbounded so we can assume it will add eventually. For remove we could decrement only if it was successfully removed. 

To avoid one hot field, Nathan suggested to me to use two AtomicLongs, one for adds and one for removes.  Size would return the difference. 

Heinz

On Sun, 23 Sep 2018 at 01:48, Alex Otenko <[hidden email]> wrote:
Right.

If the counter update is not atomic with the adding/removing of the elements, then you may get to add an element, then remove the element, then reduce the count as part of removing, then read a negative size(), and only then increment the count as part of the adding.


Alex

> On 22 Sep 2018, at 23:12, Martin Buchholz <[hidden email]> wrote:
>
> On Sat, Sep 22, 2018 at 2:53 PM, Alex Otenko <[hidden email]> wrote:
>> What use is the size() in a concurrent setting? It can only be an estimate
>
> Some library methods call size(), in the hope that it might optimize
> some other code.
>
> Even when size() is only an estimate, it may be useful.
>
> Surely we would want size() to never return a negative value (we
> probably have buglets where size overflows 32-bit).

--
Dr Heinz M. Kabutz (PhD CompSci)
Author of "The Java(tm) Specialists' Newsletter"
Sun/Oracle Java Champion
JavaOne Rockstar Speaker
http://www.javaspecialists.eu
Tel: +30 69 75 595 262
Skype: kabutz

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

Re: Concurrent Queue Sizes and Hot Fields

JSR166 Concurrency mailing list
The impl. hasn't changed in 15 years, right? Since Java 5.

Likewise, the warning has existed for 15 years:

Beware that, unlike in most collections, this method is NOT a constant-time operation. Because of the asynchronous nature of these queues, determining the current number of elements requires an O(n) traversal. Additionally, if elements are added or removed during execution of this method, the returned result may be inaccurate. Thus, this method is typically not very useful in concurrent applications.

What's the benefit in changing this now?

I claim the current impl. is by design.

On Sat, Sep 22, 2018 at 8:37 PM Dr Heinz M. Kabutz via Concurrency-interest <[hidden email]> wrote:
We could increment before actually adding.  Both queues where this would apply are unbounded so we can assume it will add eventually. For remove we could decrement only if it was successfully removed. 

To avoid one hot field, Nathan suggested to me to use two AtomicLongs, one for adds and one for removes.  Size would return the difference. 

Heinz

On Sun, 23 Sep 2018 at 01:48, Alex Otenko <[hidden email]> wrote:
Right.

If the counter update is not atomic with the adding/removing of the elements, then you may get to add an element, then remove the element, then reduce the count as part of removing, then read a negative size(), and only then increment the count as part of the adding.


Alex

> On 22 Sep 2018, at 23:12, Martin Buchholz <[hidden email]> wrote:
>
> On Sat, Sep 22, 2018 at 2:53 PM, Alex Otenko <[hidden email]> wrote:
>> What use is the size() in a concurrent setting? It can only be an estimate
>
> Some library methods call size(), in the hope that it might optimize
> some other code.
>
> Even when size() is only an estimate, it may be useful.
>
> Surely we would want size() to never return a negative value (we
> probably have buglets where size overflows 32-bit).

--
Dr Heinz M. Kabutz (PhD CompSci)
Author of "The Java(tm) Specialists' Newsletter"
Sun/Oracle Java Champion
JavaOne Rockstar Speaker
http://www.javaspecialists.eu

Tel: +30 69 75 595 262
Skype: kabutz
_______________________________________________
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: Concurrent Queue Sizes and Hot Fields

JSR166 Concurrency mailing list
It is giving incorrect answers by design.

And ConcurrentLinkedQueue has been revised and improved several times in the last 15 years. 

It is the one thing that programmers get most surprised by in my concurrency classes, especially how incorrect the answer can be.  And it is trivial to fix or at least improve. 

Heinz 

On Sun, 23 Sep 2018 at 07:04, Joe Bowbeer <[hidden email]> wrote:
The impl. hasn't changed in 15 years, right? Since Java 5.

Likewise, the warning has existed for 15 years:

Beware that, unlike in most collections, this method is NOT a constant-time operation. Because of the asynchronous nature of these queues, determining the current number of elements requires an O(n) traversal. Additionally, if elements are added or removed during execution of this method, the returned result may be inaccurate. Thus, this method is typically not very useful in concurrent applications.

What's the benefit in changing this now?

I claim the current impl. is by design.

On Sat, Sep 22, 2018 at 8:37 PM Dr Heinz M. Kabutz via Concurrency-interest <[hidden email]> wrote:
We could increment before actually adding.  Both queues where this would apply are unbounded so we can assume it will add eventually. For remove we could decrement only if it was successfully removed. 

To avoid one hot field, Nathan suggested to me to use two AtomicLongs, one for adds and one for removes.  Size would return the difference. 

Heinz

On Sun, 23 Sep 2018 at 01:48, Alex Otenko <[hidden email]> wrote:
Right.

If the counter update is not atomic with the adding/removing of the elements, then you may get to add an element, then remove the element, then reduce the count as part of removing, then read a negative size(), and only then increment the count as part of the adding.


Alex

> On 22 Sep 2018, at 23:12, Martin Buchholz <[hidden email]> wrote:
>
> On Sat, Sep 22, 2018 at 2:53 PM, Alex Otenko <[hidden email]> wrote:
>> What use is the size() in a concurrent setting? It can only be an estimate
>
> Some library methods call size(), in the hope that it might optimize
> some other code.
>
> Even when size() is only an estimate, it may be useful.
>
> Surely we would want size() to never return a negative value (we
> probably have buglets where size overflows 32-bit).

--
Dr Heinz M. Kabutz (PhD CompSci)
Author of "The Java(tm) Specialists' Newsletter"
Sun/Oracle Java Champion
JavaOne Rockstar Speaker
http://www.javaspecialists.eu

Tel: +30 69 75 595 262
Skype: kabutz
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
--
Dr Heinz M. Kabutz (PhD CompSci)
Author of "The Java(tm) Specialists' Newsletter"
Sun/Oracle Java Champion
JavaOne Rockstar Speaker
http://www.javaspecialists.eu
Tel: +30 69 75 595 262
Skype: kabutz

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

Re: Concurrent Queue Sizes and Hot Fields

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
Hi guys!

To echo what Dr. Heinz suggested, on JCTools queues is being used a similar method https://github.com/JCTools/JCTools/blob/master/jctools-core/src/main/java/org/jctools/queues/IndexedQueueSizeUtil.java#L21
The only downside I see is that both producer/consumer sequences (given the multi producer/consumer nature) would fall into some perf penalty with both LongAdder (due to the many pointer chasing indirections) or incrementAndAdd-ish operations (due to the sequential consistent semantic). Only measuring would say the truth...

Cheers,
Francesco


Il 23 set 2018 05:37, "Dr Heinz M. Kabutz via Concurrency-interest" <[hidden email]> ha scritto:
We could increment before actually adding.  Both queues where this would apply are unbounded so we can assume it will add eventually. For remove we could decrement only if it was successfully removed. 

To avoid one hot field, Nathan suggested to me to use two AtomicLongs, one for adds and one for removes.  Size would return the difference. 

Heinz

On Sun, 23 Sep 2018 at 01:48, Alex Otenko <[hidden email]> wrote:
Right.

If the counter update is not atomic with the adding/removing of the elements, then you may get to add an element, then remove the element, then reduce the count as part of removing, then read a negative size(), and only then increment the count as part of the adding.


Alex

> On 22 Sep 2018, at 23:12, Martin Buchholz <[hidden email]> wrote:
>
> On Sat, Sep 22, 2018 at 2:53 PM, Alex Otenko <[hidden email]> wrote:
>> What use is the size() in a concurrent setting? It can only be an estimate
>
> Some library methods call size(), in the hope that it might optimize
> some other code.
>
> Even when size() is only an estimate, it may be useful.
>
> Surely we would want size() to never return a negative value (we
> probably have buglets where size overflows 32-bit).

--
Dr Heinz M. Kabutz (PhD CompSci)
Author of "The Java(tm) Specialists' Newsletter"
Sun/Oracle Java Champion
JavaOne Rockstar Speaker
http://www.javaspecialists.eu

Tel: +30 69 75 595 262
Skype: kabutz
_______________________________________________
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: Concurrent Queue Sizes and Hot Fields

JSR166 Concurrency mailing list
I ran some basic tests to see under what circumstances a LongAdder or AtomicInteger would show up as a bottleneck and came up empty.   CLQ is a good general unbounded MPMC implementation, but there are faster approaches in JCTools when we can restrict the use case somewhat.  Or maybe my tests were just a bit too basic.

LongAdder can use a lot of memory if there is contention, so I’d probably use two long fields with VarHandle access.

Heinz

On Sun, 23 Sep 2018 at 09:57, Francesco Nigro <[hidden email]> wrote:
Hi guys!

To echo what Dr. Heinz suggested, on JCTools queues is being used a similar method https://github.com/JCTools/JCTools/blob/master/jctools-core/src/main/java/org/jctools/queues/IndexedQueueSizeUtil.java#L21
The only downside I see is that both producer/consumer sequences (given the multi producer/consumer nature) would fall into some perf penalty with both LongAdder (due to the many pointer chasing indirections) or incrementAndAdd-ish operations (due to the sequential consistent semantic). Only measuring would say the truth...

Cheers,
Francesco


Il 23 set 2018 05:37, "Dr Heinz M. Kabutz via Concurrency-interest" <[hidden email]> ha scritto:
We could increment before actually adding.  Both queues where this would apply are unbounded so we can assume it will add eventually. For remove we could decrement only if it was successfully removed. 

To avoid one hot field, Nathan suggested to me to use two AtomicLongs, one for adds and one for removes.  Size would return the difference. 

Heinz

On Sun, 23 Sep 2018 at 01:48, Alex Otenko <[hidden email]> wrote:
Right.

If the counter update is not atomic with the adding/removing of the elements, then you may get to add an element, then remove the element, then reduce the count as part of removing, then read a negative size(), and only then increment the count as part of the adding.


Alex

> On 22 Sep 2018, at 23:12, Martin Buchholz <[hidden email]> wrote:
>
> On Sat, Sep 22, 2018 at 2:53 PM, Alex Otenko <[hidden email]> wrote:
>> What use is the size() in a concurrent setting? It can only be an estimate
>
> Some library methods call size(), in the hope that it might optimize
> some other code.
>
> Even when size() is only an estimate, it may be useful.
>
> Surely we would want size() to never return a negative value (we
> probably have buglets where size overflows 32-bit).

--
Dr Heinz M. Kabutz (PhD CompSci)
Author of "The Java(tm) Specialists' Newsletter"
Sun/Oracle Java Champion
JavaOne Rockstar Speaker
http://www.javaspecialists.eu

Tel: +30 69 75 595 262
Skype: kabutz
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

--
Dr Heinz M. Kabutz (PhD CompSci)
Author of "The Java(tm) Specialists' Newsletter"
Sun/Oracle Java Champion
JavaOne Rockstar Speaker
http://www.javaspecialists.eu
Tel: +30 69 75 595 262
Skype: kabutz

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

Re: Concurrent Queue Sizes and Hot Fields

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
It is possible to round negative sizes to zero, too. Counting “accurately” is not the point. The point is whether the consumer is capable of coping with overestimated or underestimated queue size.

Alex

On 23 Sep 2018, at 04:13, Dr Heinz M. Kabutz <[hidden email]> wrote:

We could increment before actually adding.  Both queues where this would apply are unbounded so we can assume it will add eventually. For remove we could decrement only if it was successfully removed. 

To avoid one hot field, Nathan suggested to me to use two AtomicLongs, one for adds and one for removes.  Size would return the difference. 

Heinz

On Sun, 23 Sep 2018 at 01:48, Alex Otenko <[hidden email]> wrote:
Right.

If the counter update is not atomic with the adding/removing of the elements, then you may get to add an element, then remove the element, then reduce the count as part of removing, then read a negative size(), and only then increment the count as part of the adding.


Alex

> On 22 Sep 2018, at 23:12, Martin Buchholz <[hidden email]> wrote:
>
> On Sat, Sep 22, 2018 at 2:53 PM, Alex Otenko <[hidden email]> wrote:
>> What use is the size() in a concurrent setting? It can only be an estimate
>
> Some library methods call size(), in the hope that it might optimize
> some other code.
>
> Even when size() is only an estimate, it may be useful.
>
> Surely we would want size() to never return a negative value (we
> probably have buglets where size overflows 32-bit).

--
Dr Heinz M. Kabutz (PhD CompSci)
Author of "The Java(tm) Specialists' Newsletter"
Sun/Oracle Java Champion
JavaOne Rockstar Speaker
http://www.javaspecialists.eu
Tel: +30 69 75 595 262
Skype: kabutz


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

Re: Concurrent Queue Sizes and Hot Fields

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
> LongAdder can use a lot of memory if there is contention, so I’d probably use two long fields with VarHandle access.

+100
Given that there isn't any indication on the CLQ doc to not use in an highly concurrent scenario I suspect that incrementAndGet (on jdk >= 8 and properly padded) woudn't be the bottleneck if compared to CLQ's cas:
a LongAdder instead will add stealthy effects without adding any real value.




Il dom 23 set 2018, 10:50 Dr Heinz M. Kabutz <[hidden email]> ha scritto:
I ran some basic tests to see under what circumstances a LongAdder or AtomicInteger would show up as a bottleneck and came up empty.   CLQ is a good general unbounded MPMC implementation, but there are faster approaches in JCTools when we can restrict the use case somewhat.  Or maybe my tests were just a bit too basic.

LongAdder can use a lot of memory if there is contention, so I’d probably use two long fields with VarHandle access.

Heinz

On Sun, 23 Sep 2018 at 09:57, Francesco Nigro <[hidden email]> wrote:
Hi guys!

To echo what Dr. Heinz suggested, on JCTools queues is being used a similar method https://github.com/JCTools/JCTools/blob/master/jctools-core/src/main/java/org/jctools/queues/IndexedQueueSizeUtil.java#L21
The only downside I see is that both producer/consumer sequences (given the multi producer/consumer nature) would fall into some perf penalty with both LongAdder (due to the many pointer chasing indirections) or incrementAndAdd-ish operations (due to the sequential consistent semantic). Only measuring would say the truth...

Cheers,
Francesco


Il 23 set 2018 05:37, "Dr Heinz M. Kabutz via Concurrency-interest" <[hidden email]> ha scritto:
We could increment before actually adding.  Both queues where this would apply are unbounded so we can assume it will add eventually. For remove we could decrement only if it was successfully removed. 

To avoid one hot field, Nathan suggested to me to use two AtomicLongs, one for adds and one for removes.  Size would return the difference. 

Heinz

On Sun, 23 Sep 2018 at 01:48, Alex Otenko <[hidden email]> wrote:
Right.

If the counter update is not atomic with the adding/removing of the elements, then you may get to add an element, then remove the element, then reduce the count as part of removing, then read a negative size(), and only then increment the count as part of the adding.


Alex

> On 22 Sep 2018, at 23:12, Martin Buchholz <[hidden email]> wrote:
>
> On Sat, Sep 22, 2018 at 2:53 PM, Alex Otenko <[hidden email]> wrote:
>> What use is the size() in a concurrent setting? It can only be an estimate
>
> Some library methods call size(), in the hope that it might optimize
> some other code.
>
> Even when size() is only an estimate, it may be useful.
>
> Surely we would want size() to never return a negative value (we
> probably have buglets where size overflows 32-bit).

--
Dr Heinz M. Kabutz (PhD CompSci)
Author of "The Java(tm) Specialists' Newsletter"
Sun/Oracle Java Champion
JavaOne Rockstar Speaker
http://www.javaspecialists.eu

Tel: +30 69 75 595 262
Skype: kabutz
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

--
Dr Heinz M. Kabutz (PhD CompSci)
Author of "The Java(tm) Specialists' Newsletter"
Sun/Oracle Java Champion
JavaOne Rockstar Speaker
http://www.javaspecialists.eu
Tel: +30 69 75 595 262
Skype: kabutz

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

Re: Concurrent Queue Sizes and Hot Fields

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
On 09/20/2018 11:32 AM, Dr Heinz M. Kabutz via Concurrency-interest wrote:

> Most likely too basic for this audience ... :-)
>
> Abstract: ConcurrentLinkedQueue's size() method is not very useful in a
> multi-threaded environment, because it counts the number of elements in
> the queue, rather than relying on a "hot field" to store the size. The
> result might be completely incorrect, or in strange situations, never
> return.
>
> Full article: https://www.javaspecialists.eu/archive/Issue261.html
>

This was one of the very first API design issues in j.u.c (some of the
discussions are probably in old concurrency-interest
archives): Should concurrent queues be forced to implement Collection?
Because supporting both the size() and remove(x) methods are
problematic, the initial versions included unrelated interface
"Channel". But people successfully argued for integrating with
Collections via Queue interface, even though it forces choice among bad
implementation options. For size(), the simplest is to add a sequence
field to each node, ensuring that it is one greater than predecessor
when CASing in. This leads to fast and accurate size(), at the expense
of a 25% increase in space. Another is to add an atomic counter, which
adds contention and still presents before-vs-after increment
inaccuracies. The third, which we adopted, is to traverse, with all the
disadvantages mentioned in the article. As others have mentioned, the
main rationale is that people should not be calling size for any kind of
synchronization control anyway; for occasional uses in monitoring etc,
the slow and inaccurate version is normally OK. We now have a few more
options available (LongAdder or variants), but the same arguments for
the status quo still seem to apply.


-Doug


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

Re: Concurrent Queue Sizes and Hot Fields

JSR166 Concurrency mailing list


On Sun, 23 Sep 2018 at 14:05, Doug Lea via Concurrency-interest <[hidden email]> wrote:
On 09/20/2018 11:32 AM, Dr Heinz M. Kabutz via Concurrency-interest wrote:
> Most likely too basic for this audience ... :-)
>
> Abstract: ConcurrentLinkedQueue's size() method is not very useful in a
> multi-threaded environment, because it counts the number of elements in
> the queue, rather than relying on a "hot field" to store the size. The
> result might be completely incorrect, or in strange situations, never
> return.
>
> Full article: https://www.javaspecialists.eu/archive/Issue261.html
>

This was one of the very first API design issues in j.u.c (some of the
discussions are probably in old concurrency-interest
archives): Should concurrent queues be forced to implement Collection?
Because supporting both the size() and remove(x) methods are
problematic, the initial versions included unrelated interface
"Channel". But people successfully argued for integrating with
Collections via Queue interface, even though it forces choice among bad
implementation options. For size(), the simplest is to add a sequence
field to each node, ensuring that it is one greater than predecessor
when CASing in. This leads to fast and accurate size(), at the expense
of a 25% increase in space.

On 64-bit with compressed oops, each node is 12+4+4 bytes, which is rounded up to 24 bytes.  Thus in terms of memory usage the extra int would be free on that architecture.

That said, I think the case of removal in the middle would then also give us wrong results.   

Another is to add an atomic counter, which
adds contention and still presents before-vs-after increment
inaccuracies. The third, which we adopted, is to traverse, with all the
disadvantages mentioned in the article. As others have mentioned, the
main rationale is that people should not be calling size for any kind of
synchronization control anyway; for occasional uses in monitoring etc,
the slow and inaccurate version is normally OK. We now have a few more
options available (LongAdder or variants), but the same arguments for
the status quo still seem to apply.

In my newsletter i was mainly pointing out the behavior, rather than suggesting ways to fix it, because I’ve seen a lot of puzzled faces from experienced Java programmers over the years. 





-Doug


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
--
Dr Heinz M. Kabutz (PhD CompSci)
Author of "The Java(tm) Specialists' Newsletter"
Sun/Oracle Java Champion
JavaOne Rockstar Speaker
http://www.javaspecialists.eu
Tel: +30 69 75 595 262
Skype: kabutz

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

Re: Concurrent Queue Sizes and Hot Fields

JSR166 Concurrency mailing list
On 09/23/2018 08:28 AM, Dr Heinz M. Kabutz wrote:

>     Collections via Queue interface, even though it forces choice among bad
>     implementation options. For size(), the simplest is to add a sequence
>     field to each node, ensuring that it is one greater than predecessor
>     when CASing in. This leads to fast and accurate size(), at the expense
>     of a 25% increase in space.
>
>
> On 64-bit with compressed oops, each node is 12+4+4 bytes, which is
> rounded up to 24 bytes.  Thus in terms of memory usage the extra int
> would be free on that architecture.
>
> That said, I think the case of removal in the middle would then also
> give us wrong results.  

Now "wrong", but internal remove(x) would be even slower: the method
would need to retraverse and atomically increment each sequence number
of each predecessor.

-Doug




>
>     Another is to add an atomic counter, which
>     adds contention and still presents before-vs-after increment
>     inaccuracies. The third, which we adopted, is to traverse, with all the
>     disadvantages mentioned in the article. As others have mentioned, the
>     main rationale is that people should not be calling size for any kind of
>     synchronization control anyway; for occasional uses in monitoring etc,
>     the slow and inaccurate version is normally OK. We now have a few more
>     options available (LongAdder or variants), but the same arguments for
>     the status quo still seem to apply.
>
>
> In my newsletter i was mainly pointing out the behavior, rather than
> suggesting ways to fix it, because I’ve seen a lot of puzzled faces from
> experienced Java programmers over the years. 
>
>
>
>
>
>     -Doug
>
>
>     _______________________________________________
>     Concurrency-interest mailing list
>     [hidden email]
>     <mailto:[hidden email]>
>     http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
> --
> Dr Heinz M. Kabutz (PhD CompSci)
> Author of "The Java(tm) Specialists' Newsletter"
> Sun/Oracle Java Champion
> JavaOne Rockstar Speaker
> http://www.javaspecialists.eu
> Tel: +30 69 75 595 262
> Skype: kabutz


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

Re: Concurrent Queue Sizes and Hot Fields

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
I think you need to start with what a “correct result” means.

First the queue is forced to be a Collection, then we find that the methods cannot be implemented “correctly” :-) Maybe it isn’t a Collection?


Alex

On 23 Sep 2018, at 13:28, Dr Heinz M. Kabutz via Concurrency-interest <[hidden email]> wrote:



On Sun, 23 Sep 2018 at 14:05, Doug Lea via Concurrency-interest <[hidden email]> wrote:
On 09/20/2018 11:32 AM, Dr Heinz M. Kabutz via Concurrency-interest wrote:

> Most likely too basic for this audience ... :-)
> 
> Abstract: ConcurrentLinkedQueue's size() method is not very useful in a
> multi-threaded environment, because it counts the number of elements in
> the queue, rather than relying on a "hot field" to store the size. The
> result might be completely incorrect, or in strange situations, never
> return.
> 
> Full article: https://www.javaspecialists.eu/archive/Issue261.html
> 

This was one of the very first API design issues in j.u.c (some of the
discussions are probably in old concurrency-interest
archives): Should concurrent queues be forced to implement Collection?
Because supporting both the size() and remove(x) methods are
problematic, the initial versions included unrelated interface
"Channel". But people successfully argued for integrating with
Collections via Queue interface, even though it forces choice among bad
implementation options. For size(), the simplest is to add a sequence
field to each node, ensuring that it is one greater than predecessor
when CASing in. This leads to fast and accurate size(), at the expense
of a 25% increase in space. 

On 64-bit with compressed oops, each node is 12+4+4 bytes, which is rounded up to 24 bytes.  Thus in terms of memory usage the extra int would be free on that architecture.

That said, I think the case of removal in the middle would then also give us wrong results.   

Another is to add an atomic counter, which
adds contention and still presents before-vs-after increment
inaccuracies. The third, which we adopted, is to traverse, with all the
disadvantages mentioned in the article. As others have mentioned, the
main rationale is that people should not be calling size for any kind of
synchronization control anyway; for occasional uses in monitoring etc,
the slow and inaccurate version is normally OK. We now have a few more
options available (LongAdder or variants), but the same arguments for
the status quo still seem to apply.

In my newsletter i was mainly pointing out the behavior, rather than suggesting ways to fix it, because I’ve seen a lot of puzzled faces from experienced Java programmers over the years. 





-Doug


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
-- 
Dr Heinz M. Kabutz (PhD CompSci)
Author of "The Java(tm) Specialists' Newsletter"
Sun/Oracle Java Champion
JavaOne Rockstar Speaker
http://www.javaspecialists.eu
Tel: +30 69 75 595 262
Skype: kabutz
_______________________________________________
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: Concurrent Queue Sizes and Hot Fields

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
I don’t think you can do that reliably. In the end, who’s faster: a consumer removing elements, or remove(x) incrementing the sequence numbers? There will be subtle races showing up as weird values for size().

Alex

On 23 Sep 2018, at 13:38, Doug Lea via Concurrency-interest <[hidden email]> wrote:

On 09/23/2018 08:28 AM, Dr Heinz M. Kabutz wrote:

   Collections via Queue interface, even though it forces choice among bad
   implementation options. For size(), the simplest is to add a sequence
   field to each node, ensuring that it is one greater than predecessor
   when CASing in. This leads to fast and accurate size(), at the expense
   of a 25% increase in space. 


On 64-bit with compressed oops, each node is 12+4+4 bytes, which is
rounded up to 24 bytes.  Thus in terms of memory usage the extra int
would be free on that architecture.

That said, I think the case of removal in the middle would then also
give us wrong results.   

Now "wrong", but internal remove(x) would be even slower: the method
would need to retraverse and atomically increment each sequence number
of each predecessor.

-Doug





   Another is to add an atomic counter, which
   adds contention and still presents before-vs-after increment
   inaccuracies. The third, which we adopted, is to traverse, with all the
   disadvantages mentioned in the article. As others have mentioned, the
   main rationale is that people should not be calling size for any kind of
   synchronization control anyway; for occasional uses in monitoring etc,
   the slow and inaccurate version is normally OK. We now have a few more
   options available (LongAdder or variants), but the same arguments for
   the status quo still seem to apply.


In my newsletter i was mainly pointing out the behavior, rather than
suggesting ways to fix it, because I’ve seen a lot of puzzled faces from
experienced Java programmers over the years. 





   -Doug


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

-- 
Dr Heinz M. Kabutz (PhD CompSci)
Author of "The Java(tm) Specialists' Newsletter"
Sun/Oracle Java Champion
JavaOne Rockstar Speaker
http://www.javaspecialists.eu
Tel: +30 69 75 595 262
Skype: kabutz


_______________________________________________
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: Concurrent Queue Sizes and Hot Fields

JSR166 Concurrency mailing list
On 09/23/2018 09:18 AM, Alex Otenko wrote:
> I don’t think you can do that reliably. In the end, who’s faster: a
> consumer removing elements, or remove(x) incrementing the sequence
> numbers? There will be subtle races showing up as weird values for
> size().

To first answer:

> I think you need to start with what a “correct result” means.
>
> First the queue is forced to be a Collection, then we find that the
> methods cannot be implemented “correctly” :-) Maybe it isn’t a
> Collection?
>

I initially resisted integrating with Collection on these grounds. But
one argument in favor is that implementations can at least preserve
quiescent consistency: results for one thread meet specs if no other
threads execute. This is the notion underlying all j.u.c methods that
contain "not for use in synchronization control" disclaimers.  Also, all
j.u.c queues, being Collections, are iterable, so already have defined
weak consistency properties on these grounds. So any solution based on
traversal is no worse than what people could do themselves; and some
surely would do so if we did not supply the method.

Given all this, using sequence numbers could provide stronger guarantees
(but with an unattractive time/space tradeoff) in the absence of
internal remove, but no better than now in their presence.

-Doug


>
> Alex
>
>> On 23 Sep 2018, at 13:38, Doug Lea via Concurrency-interest
>> <[hidden email]
>> <mailto:[hidden email]>> wrote:
>>
>> On 09/23/2018 08:28 AM, Dr Heinz M. Kabutz wrote:
>>
>>> Collections via Queue interface, even though it forces choice
>>> among bad implementation options. For size(), the simplest is to
>>> add a sequence field to each node, ensuring that it is one
>>> greater than predecessor when CASing in. This leads to fast and
>>> accurate size(), at the expense of a 25% increase in space.
>>>
>>>
>>> On 64-bit with compressed oops, each node is 12+4+4 bytes, which
>>> is rounded up to 24 bytes.  Thus in terms of memory usage the
>>> extra int would be free on that architecture.
>>>
>>> That said, I think the case of removal in the middle would then
>>> also give us wrong results.
>>
>> Now "wrong", but internal remove(x) would be even slower: the
>> method would need to retraverse and atomically increment each
>> sequence number of each predecessor.
>>
>> -Doug
>>
>>
>>
>>
>>>
>>> Another is to add an atomic counter, which adds contention and
>>> still presents before-vs-after increment inaccuracies. The third,
>>> which we adopted, is to traverse, with all the disadvantages
>>> mentioned in the article. As others have mentioned, the main
>>> rationale is that people should not be calling size for any kind
>>> of synchronization control anyway; for occasional uses in
>>> monitoring etc, the slow and inaccurate version is normally OK.
>>> We now have a few more options available (LongAdder or variants),
>>> but the same arguments for the status quo still seem to apply.
>>>
>>>
>>> In my newsletter i was mainly pointing out the behavior, rather
>>> than suggesting ways to fix it, because I’ve seen a lot of
>>> puzzled faces from experienced Java programmers over the years.
>>>
>>>
>>>
>>>
>>>
>>> -Doug
>>>
>>>
>>> _______________________________________________
>>> Concurrency-interest mailing list
>>> [hidden email]
>>> <mailto:[hidden email]>
>>> <mailto:[hidden email]>
>>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>>
>>> -- Dr Heinz M. Kabutz (PhD CompSci) Author of "The Java(tm)
>>> Specialists' Newsletter" Sun/Oracle Java Champion JavaOne
>>> Rockstar Speaker http://www.javaspecialists.eu Tel: +30 69 75 595
>>> 262 Skype: kabutz
>>
>>
>> _______________________________________________
>> Concurrency-interest mailing list
>> [hidden email]
>> <mailto:[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: Concurrent Queue Sizes and Hot Fields

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
If it is used as a Collection then it will give expected results ;)

On Sun, 23 Sep 2018 at 15:42, Alex Otenko via Concurrency-interest <[hidden email]> wrote:
I think you need to start with what a “correct result” means.

First the queue is forced to be a Collection, then we find that the methods cannot be implemented “correctly” :-) Maybe it isn’t a Collection?


Alex

On 23 Sep 2018, at 13:28, Dr Heinz M. Kabutz via Concurrency-interest <[hidden email]> wrote:



On Sun, 23 Sep 2018 at 14:05, Doug Lea via Concurrency-interest <[hidden email]> wrote:
On 09/20/2018 11:32 AM, Dr Heinz M. Kabutz via Concurrency-interest wrote:

> Most likely too basic for this audience ... :-)
> 
> Abstract: ConcurrentLinkedQueue's size() method is not very useful in a
> multi-threaded environment, because it counts the number of elements in
> the queue, rather than relying on a "hot field" to store the size. The
> result might be completely incorrect, or in strange situations, never
> return.
> 
> Full article: https://www.javaspecialists.eu/archive/Issue261.html
> 

This was one of the very first API design issues in j.u.c (some of the
discussions are probably in old concurrency-interest
archives): Should concurrent queues be forced to implement Collection?
Because supporting both the size() and remove(x) methods are
problematic, the initial versions included unrelated interface
"Channel". But people successfully argued for integrating with
Collections via Queue interface, even though it forces choice among bad
implementation options. For size(), the simplest is to add a sequence
field to each node, ensuring that it is one greater than predecessor
when CASing in. This leads to fast and accurate size(), at the expense
of a 25% increase in space. 

On 64-bit with compressed oops, each node is 12+4+4 bytes, which is rounded up to 24 bytes.  Thus in terms of memory usage the extra int would be free on that architecture.

That said, I think the case of removal in the middle would then also give us wrong results.   

Another is to add an atomic counter, which
adds contention and still presents before-vs-after increment
inaccuracies. The third, which we adopted, is to traverse, with all the
disadvantages mentioned in the article. As others have mentioned, the
main rationale is that people should not be calling size for any kind of
synchronization control anyway; for occasional uses in monitoring etc,
the slow and inaccurate version is normally OK. We now have a few more
options available (LongAdder or variants), but the same arguments for
the status quo still seem to apply.

In my newsletter i was mainly pointing out the behavior, rather than suggesting ways to fix it, because I’ve seen a lot of puzzled faces from experienced Java programmers over the years. 





-Doug


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
-- 
Dr Heinz M. Kabutz (PhD CompSci)
Author of "The Java(tm) Specialists' Newsletter"
Sun/Oracle Java Champion
JavaOne Rockstar Speaker
http://www.javaspecialists.eu
Tel: +30 69 75 595 262
Skype: kabutz
_______________________________________________
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
--
Cheers,

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

Re: Concurrent Queue Sizes and Hot Fields

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
Sorry to be OT but now I'm curious about the original Channel API proposal :)

Il dom 23 set 2018, 14:01 Doug Lea via Concurrency-interest <[hidden email]> ha scritto:
On 09/20/2018 11:32 AM, Dr Heinz M. Kabutz via Concurrency-interest wrote:
> Most likely too basic for this audience ... :-)
>
> Abstract: ConcurrentLinkedQueue's size() method is not very useful in a
> multi-threaded environment, because it counts the number of elements in
> the queue, rather than relying on a "hot field" to store the size. The
> result might be completely incorrect, or in strange situations, never
> return.
>
> Full article: https://www.javaspecialists.eu/archive/Issue261.html
>

This was one of the very first API design issues in j.u.c (some of the
discussions are probably in old concurrency-interest
archives): Should concurrent queues be forced to implement Collection?
Because supporting both the size() and remove(x) methods are
problematic, the initial versions included unrelated interface
"Channel". But people successfully argued for integrating with
Collections via Queue interface, even though it forces choice among bad
implementation options. For size(), the simplest is to add a sequence
field to each node, ensuring that it is one greater than predecessor
when CASing in. This leads to fast and accurate size(), at the expense
of a 25% increase in space. Another is to add an atomic counter, which
adds contention and still presents before-vs-after increment
inaccuracies. The third, which we adopted, is to traverse, with all the
disadvantages mentioned in the article. As others have mentioned, the
main rationale is that people should not be calling size for any kind of
synchronization control anyway; for occasional uses in monitoring etc,
the slow and inaccurate version is normally OK. We now have a few more
options available (LongAdder or variants), but the same arguments for
the status quo still seem to apply.


-Doug


_______________________________________________
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
12