[concurrency-interest] Concurrent tries as a cache

Christian Vest Hansen karmazilla at gmail.com
Sun Dec 11 16:53:50 EST 2011


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.

2011/12/11 Rémi Forax <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>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
>
>
>
> _______________________________________________
> Concurrency-interest mailing list
> 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/20111211/3b38a019/attachment.html>


More information about the Concurrency-interest mailing list