Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #15010

Re: multithreaded cache?

Show key headers only | View raw

On 02.06.2012 21:27, Kevin McMurtrie wrote:
> In article<a29n7cFr61U1@mid.individual.net>,
>   Robert Klemme<shortcutter@googlemail.com>  wrote:
>
>> On 25.05.2012 08:22, Kevin McMurtrie wrote:
>>> Ha, this is an interview question that I use.
>>>
>>> What you need is row level locking for the cache load.
>>
>> But not all the time.  See https://gist.github.com/2717818
>
> The original post stated that duplicate element creation was too
> expensive.  That code may create duplicate elements for a key and
> discard the extras.

No, it does not create duplicate elements and hence does not discard 
them.  The only thing which might be duplicated is the proxy instance 
which calls the factory method (created in line 98).  But that is cheap. 
  The design ensures that a value is only calculated once per key and 
neither CPU is wasted nor duplicate value objects.  Please see Lew's 
excellent explanation of what happens or look at the code again.

>>> Step 1)
>>> Use synchronized operations to map your key to a value; creating an
>>> uninitialized value in the map if needed.  Use whatever tech you want.
>>> A synchronized block on a HashMap is simplest and performs the fastest
>>> on 1 or 2 core systems.  A ConcurrentHashMap sometimes performs better
>>> with 4+ core systems.
>>
>> In my experience a CHM performs better even on a 1 or 2 core system.
>
> This depends on usage patterns.  The Java 1.5 Concurrency locks used in
> some parts of CHM are very slow compared to synchronization.  The
> Concurrency locks only have a chance of performing better when there are
> a lot of concurrent shared read locks.

Even if they are slower than synchronization they perform better than a 
single lock on the whole Map (what you suggested above) with multiple 
threads even on a few core machine just because there are more of them 
and the whole Map is partitioned.  I haven't strictly measured the 
synchronization mechanisms used inside CHM but I did also not notice bad 
timing (and frankly, I cannot believe Doug Lea would have used 
inefficient mechanisms).  Bottom line: when in doubt measure.

>>> Step 2)
>>> Synchronize on the value.  Initialize it if needed.
>>>
>>>
>>> Step 1 blocks all cache access for only for a very short moment to make
>>> sure that a key always has a value.  Step 2 blocks access independently
>>> for each cache value to make sure that it is loaded.  It will perform
>>> well for continuous use by several CPU cores.  Google has some high
>>> concurrency Maps that aren't too bad either.
>>
>> Actually once the value is in the cache you do not need any step 2
>> synchronization any more.
>
> Step 2 is initializing the value.  It's critical to synchronize there or
> the second thread to request the same key may see an element that is not
> yet fully initialized.  (Again, the original post stated that elements
> were expensive to create.)

Maybe my wording was not clear enough.  Once the value is in the Map 
synchronization is needed no more for this key and only the Map level 
locking remains.  Again, please look at the code.

>>> In the 16 core range you'll find that any kind of exclusive lock causes
>>> stalls where threads suspend while holding locks, causing a backlog that
>>> reinforces itself. A concurrency expert can fix that using complex
>>> Compare-And-Swap designs.
>>
>> Basically this is what CHM does with putIfAbsent() internally.
>
> Yes, but you don't have access to its internal container class so CHM is
> not much use for caching elements that are very expensive to create.

I beg to differ (see code).

> The Googlely version does provide a way to initialize the container with
> a factory callback; combining steps 1 and 2 here.

Which version?  Please share a reference.  Thank you!

Kind regards

	robert

-- 
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

multithreaded cache? bugbear <bugbear@trim_papermule.co.uk_trim> - 2012-05-15 10:14 +0100
  Re: multithreaded cache? Silvio Bierman <silvio@moc.com> - 2012-05-15 11:41 +0200
    Re: multithreaded cache? Roedy Green <see_website@mindprod.com.invalid> - 2012-05-15 15:57 -0700
      Re: multithreaded cache? Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-05-15 16:13 -0700
        Re: multithreaded cache? Silvio Bierman <silvio@moc.com> - 2012-05-16 01:22 +0200
      Re: multithreaded cache? Silvio Bierman <silvio@moc.com> - 2012-05-16 01:19 +0200
        Re: multithreaded cache? Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-05-15 20:26 -0400
          Re: multithreaded cache? Arved Sandstrom <asandstrom3minus1@eastlink.ca> - 2012-05-15 21:41 -0300
          Re: multithreaded cache? Silvio Bierman <silvio@moc.com> - 2012-05-16 09:26 +0200
            Re: multithreaded cache? "Mike Schilling" <mscottschilling@hotmail.com> - 2012-05-26 14:54 -0700
        Re: multithreaded cache? Roedy Green <see_website@mindprod.com.invalid> - 2012-05-16 22:03 -0700
          Re: multithreaded cache? Silvio Bierman <silvio@moc.com> - 2012-05-21 15:25 +0200
  Re: multithreaded cache? Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-05-15 08:22 -0400
  Re: multithreaded cache? Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-05-15 09:56 -0700
  Re: multithreaded cache? bugbear <bugbear@trim_papermule.co.uk_trim> - 2012-05-16 14:33 +0100
  Re: multithreaded cache? Robert Klemme <shortcutter@googlemail.com> - 2012-05-17 11:54 +0200
    Re: multithreaded cache? Robert Klemme <shortcutter@googlemail.com> - 2012-05-17 12:06 +0200
      Re: multithreaded cache? Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-05-17 09:51 -0700
        Re: multithreaded cache? Robert Klemme <shortcutter@googlemail.com> - 2012-05-17 20:48 +0200
      Re: multithreaded cache? Sebastian <sebastian@undisclosed.invalid> - 2012-05-20 01:35 +0200
        Re: multithreaded cache? Sebastian <sebastian@undisclosed.invalid> - 2012-05-20 01:48 +0200
          Re: multithreaded cache? Lew <noone@lewscanon.com> - 2012-05-19 18:11 -0700
    Re: multithreaded cache? Silvio Bierman <silvio@moc.com> - 2012-05-18 20:42 +0200
      Re: multithreaded cache? Robert Klemme <shortcutter@googlemail.com> - 2012-05-18 23:45 +0200
        Re: multithreaded cache? Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-05-18 18:31 -0400
          Re: multithreaded cache? Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-05-18 22:15 -0700
            Re: multithreaded cache? Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-05-19 07:09 -0400
          Re: multithreaded cache? Robert Klemme <shortcutter@googlemail.com> - 2012-05-19 12:33 +0200
            Re: multithreaded cache? Lew <noone@lewscanon.com> - 2012-05-19 14:24 -0700
              Re: multithreaded cache? Robert Klemme <shortcutter@googlemail.com> - 2012-05-21 21:15 +0200
                Re: multithreaded cache? Lew <noone@lewscanon.com> - 2012-05-23 23:11 -0700
                Re: multithreaded cache? Robert Klemme <shortcutter@googlemail.com> - 2012-05-24 23:05 +0200
                Re: multithreaded cache? Gene Wirchenko <genew@ocis.net> - 2012-05-24 20:11 -0700
                Re: multithreaded cache? Robert Klemme <shortcutter@googlemail.com> - 2012-05-25 17:42 +0200
                Re: multithreaded cache? Arved Sandstrom <asandstrom3minus1@eastlink.ca> - 2012-05-25 07:09 -0300
        Re: multithreaded cache? Silvio Bierman <silvio@moc.com> - 2012-05-21 15:21 +0200
  Re: multithreaded cache? Kevin McMurtrie <mcmurtrie@pixelmemory.us> - 2012-05-24 23:22 -0700
    Re: multithreaded cache? Robert Klemme <shortcutter@googlemail.com> - 2012-05-25 17:36 +0200
      Re: multithreaded cache? Kevin McMurtrie <mcmurtrie@pixelmemory.us> - 2012-06-02 12:27 -0700
        Re: multithreaded cache? Robert Klemme <shortcutter@googlemail.com> - 2012-06-02 21:54 +0200

csiph-web