[concurrency-interest] Concurrent tries as a cache

Rémi Forax forax at univ-mlv.fr
Mon Dec 12 05:55:50 EST 2011


On 12/11/2011 10:53 PM, Christian Vest Hansen wrote:
> This is just an idea, and I don't know enough to tell whether it's any 
> good, but here goes...
> If the cache is a pointer to some persistent map, where persistent 
> implies immutable as in all fields are final (so it cannot be unsafely 
> published) /and/ you can always compensate for a miss (an implied 
> property of a cache) /and/ you never delete or overwrite entries; then 
> perhaps the pointer field need not be volatile at all? You might miss 
> a lot of updates until the cache is warm, but these misses can always 
> be compensated for, as far as I understand it.

Hi Christian.
That's a good question, I think it's ok but I'm not a concurrency guru.

In fact, I don't even miss a lot of updates in this case, at least with 
Hotspot.
Hotspot compiles the method lookup but generate a call to the interpreter
in case an update is needed because the update method is not called often
(and is too big).
So the generated code, always read the head of the tries from the RAM
and always write it into the RAM even if the variable is not tagged as 
volatile.
So I only miss updates that are truly concurrent (that happen at the 
same time
on different cores).
It's very Hotspot specific but it's fun to know that.

Rémi

>
> 2011/12/11 Rémi Forax <forax at univ-mlv.fr <mailto:forax at univ-mlv.fr>>
>
>     On 12/11/2011 06:18 PM, √iktor Ҡlang wrote:
>>     Have you've seen Aleksander Prokopec and Phil Bagwells work on
>>     Ctries?
>>
>>     https://github.com/axel22/Ctries/tree/master/src
>>
>>     Cheers,
>>>
>     I've read the wikipedia entry.
>     Compared to the implementation of Michael they insert a mutable node
>     in front of all bitmap node in order to avoid to propagate mutations
>     to more than one level.
>
>     I don't understand why it's a new kind of Node and not
>     the implementation of the bitmap node which is changed to used
>     a side object that will store the bitmap and the array and
>     be stored in a volatile variable used with a CAS.
>     It should avoid at least one virtual call.
>
>     Anyway, this data-structure will do one volatile read by level of
>     the tries
>     so in my opinion, it like get is slow down to make the mutation
>     more effective.
>     So it's not interesting for my cache.
>
>     Rémi
>
>
>>
>>     On Sun, Dec 11, 2011 at 4:20 PM, Michael Barker
>>     <mikeb01 at gmail.com <mailto:mikeb01 at gmail.com>> wrote:
>>
>>         Hi Remi,
>>
>>         It would be worthwhile benchmarking your implementation against
>>         ConcurrentHashMap.  I did something similar a while back,
>>         creating a
>>         ConcurrentMap using a Bagwell-style tree.  The quantity of my
>>         implementation notwithstanding, I was unable to bring the
>>         performance
>>         up above ConcurrentHashMap.  Profiling was inconclusive, but
>>         suggested
>>         that a combination of memory throughput demands and garbage
>>         generated
>>         by the array creation and copying when nodes were added was
>>         the main
>>         performance cost.  It outweighed the costs of the volatile/CAS
>>         operations.
>>
>>         Details are here:
>>         http://mikes-tech.blogspot.com/2011/02/non-blocking-concurrenthashmaptrie.html
>>
>>         Michael Barker.
>>
>>         On Sun, Dec 11, 2011 at 2:13 PM, Rémi Forax
>>         <forax at univ-mlv.fr <mailto:forax at univ-mlv.fr>> wrote:
>>         > Hi guys,
>>         > I'm trying to implement a fast multi-dispatch on top of
>>         invokedynamic.
>>         >
>>         > If the callsite is megamorphic, I would like to implement a
>>         table based
>>         > solutions
>>         > like MRD [1], SRP [2] or TABA [3]. All these algorithms
>>         rely on the fact
>>         > that it's possible
>>         > to associate an object or an int to a Class.
>>         >
>>         > So I need to implement a kind concurrent map (Class -> int) but
>>         > I know that an entry will be never modified nor removed
>>         after being added
>>         > and I know that there will be a lot of get and very few
>>         updates.
>>         > In fact, the data structure acts more like a cache, i.e if
>>         I can't find
>>         > the value for a specific class, I have a way to find it
>>         based on the other
>>         > entries that are already in the map.
>>         >
>>         > I've first written a class that use a lock for that, it
>>         works but as you can
>>         > guess,
>>         > it's slow.
>>         >
>>         http://code.google.com/p/jsr292-cookbook/source/browse/trunk/multi-dispatch/src/jsr292/cookbook/mdispatch/SmallClassBitMap.java
>>         >
>>         > After, I've tried to remove the lock and use an array of
>>         array. The main
>>         > array is an AtomicReferenceArray,
>>         > and the secondary arrays are the ones that store collisions
>>         and that use
>>         > copy-on-write semantics
>>         > when they need to store a new key/value entry.
>>         > But because the main array also need to grow, the reference
>>         to the main
>>         > array is also
>>         > a volatile field. So accessing to a value requires two
>>         volatiles reads.
>>         > This implementation is faster than the data structure that
>>         uses a lock
>>         > but still slow.
>>         >
>>         > So I try to use a tries instead of a hashmap.
>>         > The idea is to have a persistent trie, like the one used in
>>         Clojure [4] so
>>         > all mutations
>>         > re-create a new trie that share parts with the ole one and
>>         to use a volatile
>>         > field
>>         > (and a CAS) to store the root of the tries.
>>         >
>>         http://code.google.com/p/jsr292-cookbook/source/browse/trunk/multi-dispatch/src/jsr292/cookbook/mdispatch/util/ConcurrentTries.java
>>         >
>>         > This code is faster, but I'm not sure it is correct and I
>>         wonder if
>>         > there is a way to remove the volatile field because the
>>         data structure acts
>>         > as a cache
>>         > so if another thread don't see the modification, it's not a
>>         big deal because
>>         > it can always
>>         > process the value by using the already existing entries.
>>         >
>>         > Rémi
>>         >
>>         > [1]
>>         http://www.ifs.uni-linz.ac.at/~ecoop/cd/papers/1628/16280304.pdf
>>         <http://www.ifs.uni-linz.ac.at/%7Eecoop/cd/papers/1628/16280304.pdf>
>>         > [2]
>>         http://webdocs.cs.ualberta.ca/~paullu/Papers/COOTS2001-HTML/mdj.html
>>         <http://webdocs.cs.ualberta.ca/%7Epaullu/Papers/COOTS2001-HTML/mdj.html>
>>         > [3]
>>         http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.23.7337
>>         > [4] https://en.wikipedia.org/wiki/Hash_array_mapped_trie
>>         >
>>         > _______________________________________________
>>         > Concurrency-interest mailing list
>>         > Concurrency-interest at cs.oswego.edu
>>         <mailto:Concurrency-interest at cs.oswego.edu>
>>         > http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>
>>         _______________________________________________
>>         Concurrency-interest mailing list
>>         Concurrency-interest at cs.oswego.edu
>>         <mailto:Concurrency-interest at cs.oswego.edu>
>>         http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>
>>
>>
>>
>>     -- 
>>     Viktor Klang
>>
>>     Akka Tech Lead
>>     Typesafe <http://www.typesafe.com/>- Enterprise-Grade Scala from
>>     the Experts
>>
>>     Twitter: @viktorklang
>>
>
>
>     _______________________________________________
>     Concurrency-interest mailing list
>     Concurrency-interest at cs.oswego.edu
>     <mailto:Concurrency-interest at cs.oswego.edu>
>     http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
>
>
>
> -- 
> Venlig hilsen / Kind regards,
> Christian Vest Hansen.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20111212/458cb194/attachment-0001.html>


More information about the Concurrency-interest mailing list