ConcurrentHashMap's clear() may make size() always incorrent

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

ConcurrentHashMap's clear() may make size() always incorrent

JSR166 Concurrency mailing list
hi concurrency-interest:
    In JDK8's ConcurrentHashMap, we would use size() or mappingCount() to get size of map.

    public int size() {
        long n = sumCount();
        return ((n < 0L) ? 0 :
                (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
                (int)n);
    }

    But sometimes, the sumCount() may return a negative number, and size() or mappingCount() function must ignore the negative number and return zero.

    The reason why sumCount() may return a negative number, is that when sumCount() invoked by clear() just traverse a CounterCell object to get its count, a later delete operation comes and decrease this CounterCell's value. Then addCount(delta, -1) invoked by clear() will add a smaller negative number which is incorrent.

    I know sumCount() return a negative number is acceptable, because sumCount() not need return a very accurate number. But this incorrectness will always maintain in baseCount and counterCells, if above case happens.

    BUT I am wonder why not to corrent this incorrectness, when sumCount() return a negative number? 

    When this incorrectness happen, sumCount() always return a number that less than the correct count number. For example, in a time, ConcurrentHashMap has three node currently, but size() could return zero.

    Perhaps correct way is to make baseCount and counterCells all zero.

--------------------------------------------------------------------------------
Regards
Liu | someone who are very interested in concurrency

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

Re: ConcurrentHashMap's clear() may make size() always incorrent

JSR166 Concurrency mailing list


On 7/18/20 6:01 AM, Liu via Concurrency-interest wrote:

    The reason why sumCount() may return a negative number, is that when sumCount() invoked by clear() just traverse a CounterCell object to get its count, a later delete operation comes and decrease this CounterCell's value. Then addCount(delta, -1) invoked by clear() will add a smaller negative number which is incorrent.

Yes, when clears race with removes, some reported counts may be inaccurate. They would be less inaccurate if decrements were performed one-by-one, but at noticeable cost. Still, thanks for the reminder that this might be improved.



    Perhaps correct way is to make baseCount and counterCells all zero.

There is no quiescent point to do this, so this would also race and sometimes be inaccurate.



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

Re: ConcurrentHashMap's clear() may make size() always incorrent

JSR166 Concurrency mailing list
Well, consider of the possibility of races, maybe 
there is no way to imporve it.

Result of any operations can be obsolete, because of races.

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

Re: ConcurrentHashMap's clear() may make size() always incorrent

JSR166 Concurrency mailing list
The principle is that:
- global operations like size() must be correct in a quiescent map.
- When non-quiescent, we cannot succeed but we try to return a good estimate.

On Sun, Jul 19, 2020 at 6:32 AM Liu via Concurrency-interest
<[hidden email]> wrote:
>
> Well, consider of the possibility of races, maybe
> there is no way to imporve it.
>
> Result of any operations can be obsolete, because of races.
> _______________________________________________
> 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