[concurrency-interest] A concurrent, linked HashMap impl

Shaffer, Darron Darron_Shaffer at stercomm.com
Fri May 29 12:17:14 EDT 2009

That's just a cache size vs. lookup tradeoff.  If you want to match normal hardware caches, you just make the rule that each bucket may only contain one item.

-- Darron

-----Original Message-----
From: Roman Elizarov [mailto:elizarov at devexperts.com] 
Sent: Thursday, May 28, 2009 10:43 AM
To: Shaffer, Darron
Cc: Doug Lea; Bhasin, Vishal; concurrency-interest at cs.oswego.edu
Subject: Re[2]: [concurrency-interest] A concurrent, linked HashMap impl

Hello Darron!

That means you have a somehow filled hash bucket in the first place,
which makes your hash slow on get operations. We try to keep our
hashes at a very low fill factor (average 50%), so that our gets
operations stumble on the right element at the first attempt most of
the time.

Roman Elizarov

On Thursday, May 28, 2009 6:43:31 PM you wrote:

SD> One eviction strategy that mirrors hardware caches is to use the
SD> concept of a "cache line".  Make each hash bucket a LRU list and evict if the bucket
SD> size grows over a threshold.

SD> -----Original Message-----
SD> From: concurrency-interest-bounces at cs.oswego.edu
SD> [mailto:concurrency-interest-bounces at cs.oswego.edu] On Behalf Of Doug Lea
SD> Sent: Thursday, May 28, 2009 8:04 AM
SD> To: Bhasin, Vishal
SD> Cc: concurrency-interest at cs.oswego.edu
SD> Subject: Re: [concurrency-interest] A concurrent, linked HashMap impl

SD> Bhasin, Vishal wrote:
>> There is a high need for LRU in CHM - folks end up either creating their
>> own or using a caching product (like JCS or EHcache) for this
>> functionality.

SD> First, we cannot hope to supply something that automates all
SD> possible caching needs, especially those with persistent
SD> (disk-based) components or integrated with J2EE services.

SD> But we can supply some eviction policies in custom maps.
SD> Basically, a cache is a map with an eviction policy.
SD> An eviction policy in turn has two main parts:
SD>    * (approximately) when to evict
SD>    * (approximately) what to evict

SD> For concurrent maps we only want to consider policies
SD> compatible with our concurrency properties.
SD> So strict LIFO-based LRU is out. However, this is not
SD> a big loss. People usually pick LRU because it is
SD> cheap (which it is in non-concurrent maps) and usually
SD> performs OK. However, there are many other related
SD> policies that usually perform at least as well, especially
SD> for those that are ultimately tied to web-based requests
SD> For a slightly dated survey see
SD> http://portal.acm.org/citation.cfm?id=954341
SD> (you might need ACM membership to access this)
SD> A survey of Web cache replacement strategies
SD> Stefan Podlipnig, Laszlo Böszörmenyi, ACM Computing Surveys 2003.
SD> Most of these policies choose eviction victims based on
SD> some combination of recency, frequency, and size.

SD> We can provide generalized support for a number of
SD> these by allowing users to tell us, for each
SD> cached value:
SD>    * The item's "utility" as an eviction preference score.
SD>      for example for LRU-ish behavior, the score is access timestamp
SD>    * The item's "weight" as its contribution to the decision of
SD>      whether any item should be evicted. For example, for
SD>      a bounded cache of equal-sized items, each weight is just 1.

SD> Given these (definable in subclassable ValueRecords), we plan to
SD> support methods that will evict low-utility items when a given
SD> total-weight threshold is exceeded. The method can have only
SD> probabilistic specs, both in terms when eviction triggers and
SD> which items are removed.

SD> Aside: It is really too bad that there is no way to
SD> automate size calculations. Just bounding by total number
SD> of items can lead to unbounded footprint growth. The only
SD> recourse is to also declare the values as "Soft" references
SD> to allow the GC to delete, which we will also support, even though
SD> this can also seriously slow down GC.

SD> -Doug

SD> _______________________________________________
SD> Concurrency-interest mailing list
SD> Concurrency-interest at cs.oswego.edu
SD> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

SD> _______________________________________________
SD> Concurrency-interest mailing list
SD> Concurrency-interest at cs.oswego.edu
SD> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

More information about the Concurrency-interest mailing list