Hi Eugen, On Sat, Mar 13, 2010 at 3:28 AM, Eugen Dück <eu...@dueck.org> wrote:
> 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? > My variations on memoize use a single atom: your bounded-memoize id roughly equivalent to my memoize2 + fifo-strategy, see http://gist.github.com/330644#LID19. 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))))) > Two quick notes: * a PersistentQueue is a better fit there (conj at one end, pop/peek at the other) than a vector, * by padding it to the desired length (capacity) with dummy items, you are sure that the queue (or the vector) is always full, so you always have to remove an item: no more need for the (> (count v) capacity) test. > And if this works, it should be applicable to the strategy-ed > memoizers, too. > You implementation suffers from the same problems that my memoize2 (and they become worst in memoize3) which are caused by using the atom twice (once when reading, once when swapping). Say you have: (def g (bounded-memoize identity 3)) (g 0) (g 1) (g 2) so at this point the value in mem is [{(0) 0, (1) 1, (2) 2} [0 1 2]]. Now, concurrently, two threads call (g 3), each one see that 3 isn't memoized yet and swap! the new entry in. After the first swap! mem holds [{(1) 1, (2) 2 (3) 3} [1 2 3]], which is expected. However after the second swap! mem holds [{(2) 2 (3) 3} [2 3 3]]. That's why Meikel tests twice if the value is already in the cache (the first time outside of a transactio, the second time inside) and why I introduce hit-or-assoc in memoize4/memoize5. Have a nice week-end! 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
