Could you explain test results, please

[Andrew Kondratovich]

Hello.

I just made tests on my computer and got following: https://gist.github.com/2107797.

Could you explain so huge defference in results between chm/nbhm and
clhm ?

Cache Benchmark shows the following: https://dl.dropbox.com/u/6802923/gyazo/cachebench-GetChart.png
and https://dl.dropbox.com/u/6802923/gyazo/cachebench-PutChart.png.

Thanks.

[Ben Manes]

Hi Andrew,

Sorry for the delayed response. I've been swamped lately and forget to reply.

The first reason is that, of course, both MapMaker and CLHM perform more work than CHM and NBHM. Both caches are built on top of CHM so its our performance baseline, with the goal of minimizing the extra penalty. In both caches, we prefer to penalize writers with maintenance work of keeping track of the LRU. If the absence writes, though, a reader may be penalized.

The write performance of CLHM has decreased since the v1.0 release as the LRU implementation was strengthened to strict LRU ordering. A weak ordering maintains that correct grouping of less frequently accessed entries, but the history is scrambled so it may not evict the least frequent entry. A stricter ordering requires additional shared state and a smarter maintenance process, which reduces concurrency and is more expensive. In practice a weaker LRU is acceptable, but this raised concerns for early adopters who were migrating from LinkedHashMap. Their unit tests failed sporadically, causing them to be less confident in using the library. I tried to add strict LRU as cheaply as possible, so the overhead hasn't been raised as a concern by heavy adopters like Cassandra. My intent was that a weaker ordering would be provided in a LIRS implementation, but my attempts stalled due to technical issues and higher priorities.

The reason why MapMaker (now CacheBuilder) has a similarly high write penalty is different. The implementation does not provide strict LRU, which did cause pain for adopters but their was higher confidence in a Google branded library. In CLHM, a global LRU is maintained while in CacheBuilder an LRU is per segment. This means that CacheBuilder may evict prematurely and cannot provide an ordered iteration, but maintaining each LRU is cheap. However, the per-segment LRU requires that the segment lock is held to update the LRU ordering, which blocks writes that need the lock to proceed. In comparison, CLHM manages the LRU using a dedicated lock held in a non-blocking fashion, so writes can operate concurrently and no segment locks are required.

In technical terms, its more feasible to see CLHM return back to its original performance characteristics of being only slightly slower than ConcurrentHashMap than having CacheBuilder improve performance to be comparable. However, there are a lot of features in CacheBuilder that make it attractive, making a rewrite a low priority for the Guava team (we integrated as much of CLHM we could into the basic structure we inherited from MapMaker). The hope is that when Doug Lea writes a JDK8 implementation, he'll start from a clean slate and borrow the best ideas from the two implementations.

Cheers,

Ben