Huh, I gave it some more thought - of course, the reason why memoize won't
help us here is that there is no synchronization between simultaneous
invocations with the same set of arguments. This is typically not a problem
if the underlying function is fast, but in our case it would be neat with
an alternative. I got the idea of writing a channel-based version of
memoize, which will ensure that invoking the memoized function
simultaneously with the same arguments will only call the underlying
function once. Below is a quick implementation with one obvious drawback
(and probably tons of bugs and points of improvement!), namely that if the
underlying function is costly, and we invoke the memoized function with a
bunch of different non-cached set of arguments, then calculating the values
will be done one-by-one. This could be fixed for example by having
handle-ch delegate to another channel, where we have one channel per set of
arguments - I'll leave that for someone else, or for when I've had some
sleep and realized what a bad idea it was... :) Note that I haven't worked
much with core.async, and that there is probably a much more
straightforward solution (for example the one given by Thomas Heller), so
please let me know of any issues with this:
(defn synced-memoize [f]
(let [mem (atom {})
handle-ch (chan)]
(go-loop []
(let [[args ret-ch] (<! handle-ch)]
(>! ret-ch (if-let [e (find @mem args)]
(val e)
(let [ret (apply f args)]
(swap! mem assoc args ret)
ret)))
(recur)))
(fn [& args]
(if-let [e (find @mem args)]
(val e)
(let [ret (chan)]
(>!! handle-ch [args ret])
(<!! ret))))))
(def lookup
(let [calc-value* (synced-memoize calc-value)]
(fn [cache key]
(if (contains? @cache key)
(@cache key)
(swap! cache assoc key (calc-value* key))))))
Den måndagen den 1:e september 2014 kl. 22:35:56 UTC+2 skrev Marcus
Magnusson:
>
> I reckon if that worked, there would be no need for memoize anyway, but I
> don't think swap! will allow for it. I'm far from an expert on swap! or
> atoms, but several swap!s may be run simultaneously on a single atom (and
> swap! may re-run the swapping function if the atom has been changed since
> the swapping function was invoked). In other words, if two swap!s are
> invoked at about the same time for the same key (which is not currently in
> the cache), both invocations may be given the same value of the cache at
> that moment, which will lead to the value being re-calculated in both
> invocations - and even if calc-value is memoized, the same thing may occur
> in the memoized function.
>
> As I said, I'm far from an expert, so I wrote a small test that shows that
> calc-value may indeed be called more than once (core.async here is simply
> to ensure that each invocation of calc-value is printed on its own line):
>
>
> (def out-ch (chan 100))
>
> (go-loop []
> (println (<! out-ch))
> (recur))
>
> (defn calc-value [x]
> (put! out-ch x)
> (* x x))
>
> (def cache (atom {}))
>
> (def lookup
> (let [calc-value* (memoize calc-value)]
> (fn [cache key]
> ((swap! cache (fn [cache']
> (if (contains? cache' key)
> cache'
> (assoc cache' key (calc-value* key)))))
> key))))
>
>
> => (dotimes [_ 1000]
> (future (lookup cache (rand-int 20))))
> 11
> 12
> 16
> 1
> nil
> 6
> 15
> 17
> 18
> 14
> 2
> 5
> 19
> 10
> 0
> 7
> *9*
> *4*
> *4*
> *13*
> *9*
> *13*
>
>
> Den måndagen den 1:e september 2014 kl. 21:32:01 UTC+2 skrev Alex
> Baranosky:
>>
>> I believe you can replace:
>> (when-not (contains? @cache k)
>> (swap! cache assoc k (calc-value* k))))
>>
>> with:
>> (swap! cache (fn [cache']
>> (if (contains? cache' k)
>> cache'
>> (assoc cache' k (calc-value* k)))))
>>
>> Note: I haven't run this code
>>
>>
>> On Mon, Sep 1, 2014 at 2:20 AM, Colin Fleming <[email protected]>
>> wrote:
>>
>>> Hi Thomas,
>>>
>>> Normally I'd agree with you, but in my case it actually works quite well
>>> since I don't need to expire or worry about sizing. This is for caching
>>> objects on IntelliJ parse tree elements, and the element with its cached
>>> values is thrown away every time the document is parsed, so these are
>>> pretty transient caches. In this particular case the calculation isn't too
>>> heavyweight either so recalculating it in the unlikely event of contention
>>> isn't a big deal. In fact, this discussion and the related thinking has
>>> made me realise that my original solution was actually sufficient for my
>>> somewhat strange use case, which is nice :-). For more typical server side
>>> caching, I agree that Guava would be a great solution.
>>>
>>> Cheers,
>>> Colin
>>>
>>>
>>> On 1 September 2014 20:54, Thomas Heller <[email protected]> wrote:
>>>
>>>> As much as I like Clojure and atoms, I do not think they are a good fit
>>>> for caching. Not only is it impossible to address the concurrency issues
>>>> related to multiple threads loading the same object, but you also have to
>>>> do expiration and size management yourself. Immutability doesn't help much
>>>> for caching either. There is core.cache that does some bits but I probably
>>>> would recommend using something like CacheBuilder from the guava libs:
>>>>
>>>> See
>>>> https://code.google.com/p/guava-libraries/
>>>>
>>>> http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/cache/CacheBuilder.html
>>>>
>>>> Its Java but the Clojure<->Java interop is so good that it doesn't
>>>> matter much.
>>>>
>>>> On Saturday, August 30, 2014 7:27:05 AM UTC+2, Colin Fleming wrote:
>>>>>
>>>>> Hi all,
>>>>>
>>>>> I want to use a map to cache values based on a key. I'm planning to
>>>>> use an atom for this. My basic operation is "give me the value for this
>>>>> key" - if the value exists in the map then that value should be returned,
>>>>> otherwise a new value should be calculated, inserted in the map and then
>>>>> returned. My plan is to implement something like the following:
>>>>>
>>>>>
>>>>> (defn ensure [cache key] (if (contains? cache key) cache (assoc
>>>>> cache key (calc-value key))))(let [value (get (swap! cache ensure key)
>>>>> key)] ... do my thing with value ...)
>>>>>
>>>>>
>>>>> So 'ensure' ensures that the cache contains the value for key, the
>>>>> swap! operation returns the cache with the value and then I get it out.
>>>>> This works but feels a little clumsy, is there a better way to do this?
>>>>>
>>>>> Also, looking at the Atom source code, I see that this will cause a
>>>>> CAS operation even if the value returned from swap! is identical to the
>>>>> original value. It seems like a reasonable optimisation would be to check
>>>>> if the values are identical and not update if so - is there a reason this
>>>>> might not be a good idea?
>>>>>
>>>>> Thanks,
>>>>> Colin
>>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Clojure" group.
>>>> To post to this group, send email to [email protected]
>>>> Note that posts from new members are moderated - please be patient with
>>>> your first post.
>>>> To unsubscribe from this group, send email to
>>>> [email protected]
>>>> For more options, visit this group at
>>>> http://groups.google.com/group/clojure?hl=en
>>>> ---
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Clojure" group.
>>>> To unsubscribe from this group and stop receiving emails from it, send
>>>> an email to [email protected].
>>>> For more options, visit https://groups.google.com/d/optout.
>>>>
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Clojure" group.
>>> To post to this group, send email to [email protected]
>>> Note that posts from new members are moderated - please be patient with
>>> your first post.
>>> To unsubscribe from this group, send email to
>>> [email protected]
>>> For more options, visit this group at
>>> http://groups.google.com/group/clojure?hl=en
>>> ---
>>> You received this message because you are subscribed to the Google
>>> Groups "Clojure" group.
>>> To unsubscribe from this group and stop receiving emails from it, send
>>> an email to [email protected].
>>> For more options, visit https://groups.google.com/d/optout.
>>>
>>
>>
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
