[concurrency-interest] Concurrent tries as a cache

√iktor Ҡlang viktor.klang at gmail.com
Sun Dec 11 12:18:05 EST 2011


Have you've seen Aleksander Prokopec and Phil Bagwells work on Ctries?

https://github.com/axel22/Ctries/tree/master/src

Cheers,
√

On Sun, Dec 11, 2011 at 4:20 PM, Michael Barker <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> 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
> > [2] http://webdocs.cs.ualberta.ca/~paullu/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
> > 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
>



-- 
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/5a4cf056/attachment.html>


More information about the Concurrency-interest mailing list