[concurrency-interest] computeIfAbsent optimized for missing entries

Benjamin Manes ben.manes at gmail.com
Tue Feb 14 14:09:41 EST 2017


In that thread, Doug explains why:

However, the exact benefit depends on access patterns. For example, I reran
> your benchmark cases (urls below) on a 32way x86, and got throughputs
> (ops/sec) that are dramatically better with pre-screen for the case of a
> single key, but worse with your Zipf-distributed keys.



One might think (I did until running similar experiments) that the "1cif"
> version would be the best compromise. But currently it isn't. This is in
> part due to interactions with biased locking, that in some cases basically
> provide "free" prescreens, but in other cases add safepoint/GC pressure in
> addition to lock contention. This is all up for re-consideration though.


At the time, I spun up a 32-core machine and reproduced his findings. The
JDK9 partial pre-screening seems to be a compromise that hopefully avoids
lock contention in the common case, but I have not benchmarked it myself to
advise. Caffeine always performs its own pre-screening since a cache has a
high likelihood of the entry being present.

I believe ComputingTest became AsMapTest. This has the recursive
computation test cases discussed and fixed in that thread.

On Tue, Feb 14, 2017 at 5:46 AM, Amir Hadadi <amirhadadi at hotmail.com> wrote:

> I went over the discussions, and found the following:
> http://cs.oswego.edu/pipermail/concurrency-interest/2014-December/013360.
> html
>
> And these are the current benchmarks from caffeine (the links in the post
> above are dead):
> https://github.com/ben-manes/caffeine/wiki/Benchmarks
>
>
> > As an intermediate
> > test, I measured the impact of adding a single-node prescreen
> > ("1cif") before locking inside CHM.computeIfAbsent, that is similar
> > to what was done in some pre-release versions:
> >
> > Same key
> >
> > cif:        1402559
> > get+cif: 3775886700
> > 1cif:    1760916148
> >
> > Zipf-distributed keys
> >
> > cif:     1414945003
> > get+cif:  882477874
> > 1cif:     618668961
>
>
> You refer to 2 benchmarks in this post, ComputingTest and
> ComputeBenchmark. I couldn't find ComputingTest, but I found
> ComputeBenchmark here:
> https://github.com/ben-manes/caffeine/blob/master/caffeine/
> src/jmh/java/com/github/benmanes/caffeine/cache/ComputeBenchmark.java
>
> I tested only the Zipf-distributed keys, running the cif vs get + cif
> versions using 8 threads, OSX 10.11.6, 2.8 GHz Intel Quad Core i7.
> My results were:
>
> cif:
> Result "org.sample.ComputeBenchmark.compute_spread":
>   83559118.933 ±(99.9%) 18403807.660 ops/s [Average]
>   (min, avg, max) = (80998142.816, 83559118.933, 86575174.221), stdev =
> 2848009.607
>   CI (99.9%): [65155311.273, 101962926.593] (assumes normal distribution)
>
>
> get + cif:
>   208177607.279 ±(99.9%) 12987916.190 ops/s [Average]
>   (min, avg, max) = (206351511.981, 208177607.279, 210850461.612), stdev =
> 2009894.407
>   CI (99.9%): [195189691.090, 221165523.469] (assumes normal distribution)
>
> So the get + cif version is faster by a factor of 2.5.
> I would be very surprised to find that get + cif is slower than cif when
> there are no absent entries.
>
> Do these results seem reasonable? Did you run other benchmarks that
> convinced you that cif is better than the alternatives?
>
> ------------------------------
> *From:* Concurrency-interest <concurrency-interest-bounces at cs.oswego.edu>
> on behalf of Doug Lea <dl at cs.oswego.edu>
> *Sent:* Thursday, February 9, 2017 1:51:01 PM
> *To:* Benjamin Manes
> *Cc:* Concurrency-interest at cs.oswego.edu
> *Subject:* Re: [concurrency-interest] computeIfAbsent optimized for
> missing entries
>
> On 02/08/2017 12:22 PM, Benjamin Manes wrote:
> > In JDK9, it looks like you added a small prescreening
> > <http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/
> main/java/util/concurrent/ConcurrentHashMap.java?r1=1.295&r2=1.296>
> > to check at the first node in the bin and eagerly return. That seems
> > like a smart compromise, given the performance analysis you shared on
> > this forum previously that dissuaded you from adopting a full
> > pre-screening.
>
> Thanks! I forgot that this made it into jdk9 (vs jdk8).
> Amir: for more details see the discussions on this in the
> archives: http://cs.oswego.edu/pipermail/concurrency-interest/
>
> -Doug
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20170214/1978502c/attachment.html>


More information about the Concurrency-interest mailing list