Re: ConcurrentHashMap and equality

--===============3482534877330064450==
Content-Type: multipart/alternative; boundary="0000000000008ab45f05da24f28f"

--0000000000008ab45f05da24f28f
Content-Type: text/plain; charset="UTF-8"

Thanks Nathan, I had forgotten about those details in the Java 5-7
implementations. If I recall correctly, those were O(concurrencyLevel) as
the segment maintained a counter. However, some variants were more complex
with retries and locking, whereas others were just a best-effort summation.
The Java 8+ implementation embeds a variant of LongAdder which maintains
its own array of lock-free counter cells. As the number of cells is based
on the runtime cpu count, it is effectively O(1). This same approach was
applied to ConcurrentSkipListMap which previously was O(n) and might be
what you are recalling.

On Sun, Mar 13, 2022 at 7:47 PM Nathan Reynolds <[email protected]>
wrote:

> If I remember right, ConcurrentHashMap.size() is a O(n) operation.  This
> means it traverses the entries in the Map.  So, instead of making 2 passes
> at the entries (i.e., size() and then entries equals()), it is probably
> cheaper to simply to just do entries equals().
>
> I think size() is a O(n) operation because of too much contention from
> maintaining an atomic size.  Every put() and remove() will have to do an
> atomic operation on the size field.  This leads to cache contention and
> terrible performance.
>
> However, my knowledge may be stale.  Perhaps, size() is now O(1).  If so,
> a size() precheck in equals() probably would make sense.
>
> On Sun, Mar 13, 2022 at 4:54 PM Benjamin Manes via Concurrency-interest <
> [email protected]> wrote:
>
>> The equality contract for Map is defined as having the same mappings in
>> their entrySet views. The AbstractMap and AbstractSet implementations
>> include a size() prescreen, which is typically an immediate operation. The
>> concurrent maps don't, though, and I am wondering if this is a missed
>> opportunity. The consistency property already dictates that the comparison
>> is deterministic only if neither object or its parts are modified between
>> invocations. Therefore the method's documentation that equality may
>> be misleading in the face of concurrency is simply a reminder of that fact.
>> Since the size check might be performed regardless by an AbstractMap-based
>> implementation (e.g. HashMap), then by symmetry it would imply that adding
>> this prescreen would be an acceptable optimization. Does that seem
>> reasonable or is there an aspect that I am forgetting?
>> _______________________________________________
>> Concurrency-interest mailing list
>> [email protected]
>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>
>

--0000000000008ab45f05da24f28f
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Thanks Nathan, I had forgotten about those details in the =
Java 5-7 implementations. If I recall correctly, those were O(concurrencyLe=
vel) as the segment maintained a counter. However, some variants were more =
complex with retries and locking, whereas others were just a best-effort su=
mmation. The Java 8+ implementation embeds a variant of LongAdder which mai=
ntains its own array of lock-free counter cells. As the number of cells is =
based on the runtime cpu count, it is effectively O(1). This same approach =
was applied to ConcurrentSkipListMap which previously was O(n) and might be=
 what you are recalling.</div><br><div class=3D"gmail_quote"><div dir=3D"lt=
r" class=3D"gmail_attr">On Sun, Mar 13, 2022 at 7:47 PM Nathan Reynolds &lt=
;<a href=3D"mailto:[email protected]">[email protected]</a>&gt;=
 wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px =
0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=
=3D"ltr"><div>If I remember right, ConcurrentHashMap.size() is a O(n) opera=
tion.=C2=A0 This means it traverses the entries in the Map.=C2=A0 So, inste=
ad of making 2 passes at the entries (i.e., size() and then entries equals(=
)), it is probably cheaper to simply to just do entries equals().</div><div=
><br></div><div>I think size() is a O(n) operation because of too much cont=
ention from maintaining an atomic size.=C2=A0 Every put() and remove() will=
 have to do an atomic operation on the size field.=C2=A0 This leads to cach=
e contention and terrible performance.</div><div><br></div><div>However, my=
 knowledge may be stale.=C2=A0 Perhaps, size() is now O(1).=C2=A0 If so, a =
size() precheck in equals() probably would make sense.<br></div></div><br><=
div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">On Sun, Mar=
 13, 2022 at 4:54 PM Benjamin Manes via Concurrency-interest &lt;<a href=3D=
"mailto:[email protected]" target=3D"_blank">concurrency-i=
[email protected]</a>&gt; wrote:<br></div><blockquote class=3D"gmail_qu=
ote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,20=
4);padding-left:1ex"><div dir=3D"ltr"><div>The equality contract for Map is=
 defined as having the same mappings in their entrySet views. The AbstractM=
ap and AbstractSet implementations include a size() prescreen, which is typ=
ically an immediate operation. The concurrent maps don&#39;t, though, and I=
 am wondering if this is a missed opportunity. The consistency property alr=
eady dictates that the comparison is deterministic only if neither object o=
r its parts are modified between invocations. Therefore the method&#39;s do=
cumentation that equality may be=C2=A0misleading in=C2=A0the face of concur=
rency is simply=C2=A0a reminder of that fact. Since the size check might be=
 performed regardless by an AbstractMap-based implementation (e.g. HashMap)=
, then by symmetry it would imply that adding this prescreen would be an ac=
ceptable optimization. Does that seem reasonable or is there an aspect that=
 I am forgetting?<br></div></div>
_______________________________________________<br>
Concurrency-interest mailing list<br>
<a href=3D"mailto:[email protected]" target=3D"_blank">Con=
[email protected]</a><br>
<a href=3D"http://cs.oswego.edu/mailman/listinfo/concurrency-interest" rel=
=3D"noreferrer" target=3D"_blank">http://cs.oswego.edu/mailman/listinfo/con=
currency-interest</a><br>
</blockquote></div>
</blockquote></div>

--0000000000008ab45f05da24f28f--

--===============3482534877330064450==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

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

--===============3482534877330064450==--