Laurent, Meikel, Christophe, I guess I must be missing something obvious, but can't we just put more than one thing into an atom in order to get atomic behavior? Using, say, a vector. Using the simple bounded memoizer as an example, this looks to me like it works:
(defn bounded-memoize [f capacity] (let [mem (atom [{} []])] (fn [& args] (if-let [e (find (first @mem) args)] (val e) (let [ret (apply f args)] (swap! mem #(let [cache (assoc (first %) args ret) v (conj (second %) args)] (if (> (count v) capacity) [(dissoc cache (first v)) (subvec v 1)] [cache v]))) ret))))) And if this works, it should be applicable to the strategy-ed memoizers, too. Eugen On Mar 13, 4:27 am, Christophe Grand <christo...@cgrand.net> wrote: > Hi Meikel, > > Since Laurent dragged me into the discussion: > > > > On Thu, Mar 11, 2010 at 8:42 AM, Meikel Brandmeyer <m...@kotka.de> wrote: > > Hello Laurent, > > > On Mar 10, 11:45 am, Laurent PETIT <laurent.pe...@gmail.com> wrote: > > > > * usage of refs : I had a bad feeling, and cgrand confirmed this to > > > me by pointing an even more interesting counter-argument. Me: using > > > refs is not mandatory since you do not need to synchronize this change > > > with anything else. > > > I don't think, that this is entirely true! You have to syncronise the > > cache with the state in the strategy. This can be done with atoms only > > if the cache and the strategy state are contained in the same atom and > > all updates happen in a single call to swap! (or reset!). As soon as > > you > > have multiple calls, you need transactions again, because the atom > > might > > change between the two calls. And you can't swap! and return a result > > at > > the same time. > > > Say you have the LRU strategy. You deref the cache, find the result > > cached. Now you swap! in the new access time into your state. But > > between the deref and the swap! another call might trigger the removal > > of the entry. So you always have to guard against the atom suddenly > > changing underneath - even if it's only one atom. > > I agree. > > > Something what annoys me more is that the computation may be fired of > > several times. Since the f is supposedly expensive, I'd rather avoid > > that. > > See my memoize5: the call isn't computed inside the swap!s > > > > > I gave it another run and came up with another solution. Even more > > hairy. :P > > > * a warm cache is fast > > * a cache miss is potentially slow, but the missing value is computed > > only > > once, multiple requests for the same item wait for the initially > > triggered > > computation > > * the cache can be updated (almost) in parallel for different items > > > (defn memoize > > ([f] (memoize f naive-strategy)) > > ([f [cache-lookup cache-update]] > > (let [cache-state (atom {})] > > (fn [& args] > > (if-let [e (cache-lookup cache-state args)] > > @(val e) > > @(locking cache-state > > (if-let [e (cache-lookup cache-state args)] > > (val e) > > (let [result (promise)] > > (.start (Thread. #(deliver result (apply f args)))) > > (swap! cache-state assoc-in [:cache args] result) > > (cache-update cache-state args) > > result)))))))) > > > But with this you can't reliably implement strategies like LRU and the > > like. > > Since you use a lock I think some clever combination of memoized functions > can create a deadlock. > > > But this is really an interesting problem. I'll mull a little more > > about it. :) > > I agree, it's interesting and here is my entry:http://gist.github.com/330644 > > Christophe -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en