[concurrency-interest] Concurrent tries as a cache

Rémi Forax forax at univ-mlv.fr
Sun Dec 11 13:54:15 EST 2011


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
>

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


More information about the Concurrency-interest mailing list