Re: ConcurrentHashMap and equality

--===============6764653192903451497==
Content-Type: multipart/alternative; boundary="000000000000a2b88905da24b291"

--000000000000a2b88905da24b291
Content-Type: text/plain; charset="UTF-8"

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
>

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

<div dir=3D"ltr"><div>If I remember right, ConcurrentHashMap.size() is a O(=
n) operation.=C2=A0 This means it traverses the entries in the Map.=C2=A0 S=
o, 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().</=
div><div><br></div><div>I think size() is a O(n) operation because of too m=
uch contention from maintaining an atomic size.=C2=A0 Every put() and remov=
e() will have to do an atomic operation on the size field.=C2=A0 This leads=
 to cache contention and terrible performance.</div><div><br></div><div>How=
ever, my knowledge may be stale.=C2=A0 Perhaps, size() is now O(1).=C2=A0 I=
f so, a size() precheck in equals() probably would make sense.<br></div></d=
iv><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]">concurrency-interest@cs=
.oswego.edu</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>The equality contract for Map is defined a=
s having the same mappings in their entrySet views. The AbstractMap and Abs=
tractSet implementations include a size() prescreen, which is typically an =
immediate operation. The concurrent maps don&#39;t, though, and I am wonder=
ing if this is a missed opportunity. The consistency property already dicta=
tes that the comparison is deterministic only if neither object or its part=
s are modified between invocations. Therefore the method&#39;s documentatio=
n that equality may be=C2=A0misleading in=C2=A0the face of concurrency is s=
imply=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 acceptable o=
ptimization. Does that seem reasonable or is there an aspect that I am forg=
etting?<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>

--000000000000a2b88905da24b291--

--===============6764653192903451497==
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

--===============6764653192903451497==--