Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.java.programmer > #14571
| From | Robert Klemme <shortcutter@googlemail.com> |
|---|---|
| Newsgroups | comp.lang.java.programmer |
| Subject | Re: multithreaded cache? |
| Date | 2012-05-17 11:54 +0200 |
| Message-ID | <a1k06fFtdtU1@mid.individual.net> (permalink) |
| References | <zsWdnVufD87Egy_SnZ2dnUVZ7oednZ2d@brightview.co.uk> |
On 05/15/2012 11:14 AM, bugbear wrote:
> However, if the underlying function is slow
> and/or resource hungry (consider cacheing
> a ray traced image!) many threads can
> end up calling the real function (second
> and subsequent threads to the first get a miss
> during the first threads call to the underlying function).
>
> "obviously..." what I want is for only
> the thread that FIRST has a cache miss
> calls the underlying function, whilst other
> threads (for the same key) wait.
I provide a variant of Silvio's, Eric's and Daniel's solution which
should yield higher throughput because it works without read write
locking. You can find it as gist in case the code is garbled in the
newsgroup posting:
https://gist.github.com/2717818
Kind regards
robert
The code (untested):
package clj;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
/**
* The cache works with as few locking as possible. Lookup is done in
two steps
* on cache miss:
* <ol>
* <li>On a cache miss a retriever is inserted into the cache which
will obtain
* the value synchronized from a {@link Calculator}.</li>
* <li>Once calculation has finished a simple lock free reference to
the value
* replaces the retriever in the cache and the value is returned.</li>
* </ol>
*
* @author robert klemme
*
* @param <K>
* key type
* @param <V>
* value type
*/
public final class LazyCache<K, V> {
/**
* Calculate values from given keys.
*
* @param <K>
* key type
* @param <V>
* value type
*/
public interface Calculator<K, V> {
V get(K key);
}
/**
* Obtain a value.
*
* @param <V>
* value type.
*/
private interface Reference<V> {
V get();
}
/**
* Stupid simple reference which only hands out a fixed value all
the time
* without synchronization.
*
* @param <V>
* value type.
*/
private static final class Ref<V> implements Reference<V> {
private final V val;
public Ref(V val) {
this.val = val;
}
@Override
public V get() {
return val;
}
}
/** Mapping from keys to objects which yield values. */
private final ConcurrentMap<K, Reference<V>> map = new
ConcurrentHashMap<K, Reference<V>>();
/** User provided. */
private final Calculator<K, V> calc;
/**
* Create a cache.
*
* @param calc
* user must provide a reasonable implementation, not
* <code>null</code>.
*/
public LazyCache(final Calculator<K, V> calc) {
if (calc == null)
throw new NullPointerException();
this.calc = calc;
}
/**
* Get a value from the cache. The value might have to be calculated.
*
* @param key
* lookup key.
* @return value, might even be <code>null</code> depending on
algorithm.
*/
public V get(final K key) {
Reference<V> ref = map.get(key);
if (ref == null) {
// miss
ref = new Reference<V>() {
@Override
public synchronized V get() {
final V val = calc.get(key);
// next time lock free access:
Reference<V> x = map.put(key, new Ref<V>(val));
assert x == this;
return val;
}
};
final Reference<V> old = map.putIfAbsent(key, ref);
if (old != null)
ref = old; // someone else was faster
}
return ref.get();
}
}
Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll 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