Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!gegeweb.org!de-l.enfer-du-nord.net!feeder1.enfer-du-nord.net!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail From: Robert Klemme Newsgroups: comp.lang.java.programmer Subject: Re: multithreaded cache? Date: Thu, 17 May 2012 20:48:52 +0200 Lines: 90 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Trace: individual.net RS2u9OOV1nJkPMxfxguBcw3vNj7rVAcxLwhtVbqbqVMH4k6uSJZN90D+PRQchGUQY= Cancel-Lock: sha1:Iwyl64LlioZDz393FA78/kfXqpc= User-Agent: Mozilla/5.0 (Windows NT 6.0; WOW64; rv:12.0) Gecko/20120428 Thunderbird/12.0.1 In-Reply-To: Xref: csiph.com comp.lang.java.programmer:14590 On 17.05.2012 18:51, Daniel Pitts wrote: > On 5/17/12 3:06 AM, Robert Klemme wrote: >> On 05/17/2012 11:54 AM, Robert Klemme wrote: >>> 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 >> >> There was one important detail missing. This is the corrected code (gist >> is updated as well): > [snip] >> if (!here) { >> val = calc.get(key); >> here = true; >> // next time lock free access: >> Reference x = map.put(key, new Ref(val)); >> assert x == this; >> } > This assert (while true) is unnecessary and potentially harmful. Nothing > becomes inconsistent if the value you replace is not the calculating > reference. The algorithm works under the assumption that the first element placed into the map is the one doing the calculation and only after that the constant reference is inserted. If that is not the case (e.g. because another calculator is put into the map) then obviously something must be wrong and we might even have more than one lengthy calculation of the cached value. This assumption is checked with the assert which also serves as documentation. > However, your assert may break at runtime if something else > changes about this code. Assert should be used to validate consistency. Well, if the logic is changed then of course asserts need to change, too. There is nothing strange or harmful about that. With your argument no asserts would make sense because they would need to be changed if a class is changed. Note that internal class invariants can change without changing the observable invariant. So even though a class "looks" the same and behaves the same from the outside asserts might have to be changed if internal logic of the class changes. > I like this class, though I have a couple of style comments. Thank you! > I personally would name "Ref" as "ConstantReference", Well, I was lazy typing and the class isn't public anyway. This is not production code but an illustrating example for cljp. > and your anonymous > Reference implementation I would make a private static class > CalculatingReference. Why? You would need to either pass in a reference to LazyCache or pass map and calc - plus declaring a constructor and type parameters. In this case I don't really see the benefit. > In my own personal library of utilities, I actually have two interfaces > "Factory" with a "T create()" method and "ParameterizedFactory" > with a "T create(P parameter)". Including a few interesting > implementations of those. In my case, I would probably implement this > cache as a ParameterizedFactory impl that takes another > ParameterizedFactory as the "calc" field. That could be done. But then method naming could be considered misleading because the create() of the cache isn't really a create in all cases. Kind regards robert -- remember.guy do |as, often| as.you_can - without end http://blog.rubybestpractices.com/