Re: atoms, memoize, future-s and CAS
Hi, Thanks for all suggestions. It all encouraged me to deep dive into atom-s code which turns out to be a simple wrapper over Java java.util.concurrent.atomic.AtomicReference which essentially is a spinlock. Knowing how it works under the hood makes so easier to use it ... Below piece (hopefully correct) let me update map atomically: (defn cond-assoc! [atomic-map key val] (loop [] (let [candidate (if (contains? @atomic-map key) @atomic-map (assoc @atomic-map key val))] (if (compare-and-set! atomic-map @atomic-map candidate) candidate (recur) I also learned that using future (or essentially Java threads) is so poor approach to scalability. derefing memoized delay of my function wrapped with future worked well to some point. After pushing it a bit with more concurrent tasks, my JVM started freezing under pressure of to many threads. I ended up with my custom hybrid of a queued future-s. I have also a version done in core.async - I will try to write it up in a separate piece at some point .. Best regards, Andy -- 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 --- 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 clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: atoms, memoize, future-s and CAS
Most of the cache implementations in core.cache have no side-effects. They simply return a new cache rather than overwriting the old one. The memoize library places the cache in an atom, so it's guaranteed to change atomically. I tried to read the cache code (btw an excellent exercise) , and I think I understand how persistent data structure/atom is employed here in case we deal with side effects free functions. You could write this as a function. There's nothing in there that requires a macro. (defn when-map-future-swap! [a k f] (locking a (when-not (contains? @a k) (swap! a assoc k nil) (future (swap! a assoc k (f k)) I realized that later too ... But I'd personally just use a delay rather than locking for this purpose. It is not that I like locking at all. However I still fail to see, how in a multithreaded context memoize/cache prevents executing a given function more than once (which I want to avoid at any cost here) since cache lookup and swap! does not seem to be atomic : https://github.com/clojure/core.cache/blob/master/src/main/clojure/clojure/core/cache.clj#L52 . Best regards, Andy -- 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 --- 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 clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: atoms, memoize, future-s and CAS
On 8 December 2014 at 17:54, Andy L core.as...@gmail.com wrote: But I'd personally just use a delay rather than locking for this purpose. It is not that I like locking at all. However I still fail to see, how in a multithreaded context memoize/cache prevents executing a given function more than once (which I want to avoid at any cost here) since cache lookup and swap! does not seem to be atomic : https://github.com/clojure/core.cache/blob/master/src/main/clojure/clojure/core/cache.clj#L52 When you say (delay (foo)), foo will be called at most once, regardless of how many times you deref (@) / force the delay. (If you never force the delay, it will not be called at all.) The way this is enforced is through making deref a synchronized method on delays. Cheers, Michał -- 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 --- 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 clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: atoms, memoize, future-s and CAS
On Monday, December 8, 2014 3:34:05 PM UTC-5, Michał Marczyk wrote: On 8 December 2014 at 17:54, Andy L core@gmail.com javascript: wrote: But I'd personally just use a delay rather than locking for this purpose. It is not that I like locking at all. However I still fail to see, how in a multithreaded context memoize/cache prevents executing a given function more than once (which I want to avoid at any cost here) since cache lookup and swap! does not seem to be atomic : https://github.com/clojure/core.cache/blob/master/src/main/clojure/clojure/core/cache.clj#L52 When you say (delay (foo)), foo will be called at most once, regardless of how many times you deref (@) / force the delay. (If you never force the delay, it will not be called at all.) The way this is enforced is through making deref a synchronized method on delays. Which means it's locking or bust. You just get to either do the locking yourself or delegate :) -- 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 --- 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 clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: atoms, memoize, future-s and CAS
Oh, and as for how to use it here, you could for example say (.putIfAbsent concurrent-hash-map :foo (delay (foo))) Then the first thread to @(get concurrent-hash-map :foo (delay :not-found)) (or similar) would actually compute the value. With a map in an atom, you could swap! using a function like (fn [old-state] (if (contains? old-state :foo) (assoc old-state :foo (delay (foo))) old-state)) I'd probably prefer a CHM for this purpose, though. Michał On 8 December 2014 at 21:33, Michał Marczyk michal.marc...@gmail.com wrote: On 8 December 2014 at 17:54, Andy L core.as...@gmail.com wrote: But I'd personally just use a delay rather than locking for this purpose. It is not that I like locking at all. However I still fail to see, how in a multithreaded context memoize/cache prevents executing a given function more than once (which I want to avoid at any cost here) since cache lookup and swap! does not seem to be atomic : https://github.com/clojure/core.cache/blob/master/src/main/clojure/clojure/core/cache.clj#L52 When you say (delay (foo)), foo will be called at most once, regardless of how many times you deref (@) / force the delay. (If you never force the delay, it will not be called at all.) The way this is enforced is through making deref a synchronized method on delays. Cheers, Michał -- 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 --- 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 clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: atoms, memoize, future-s and CAS
On 8 December 2014 at 21:46, Fluid Dynamics a2093...@trbvm.com wrote: [...] Which means it's locking or bust. You just get to either do the locking yourself or delegate :) Sure, but isn't it nice when somebody else does your locking for you? :-) Incidentally, there is a trade-off here between lockless reads and cache-locking writes in the version with (locking …) and synchronized reads (of delays) and somewhat concurrency-friendly writes in the version with CHM.putIfAbsent and delays. So actually explicit (locking …) might be preferable for certain workloads. Benchmarking required. Michał -- 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 --- 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 clojure+unsubscr...@googlegroups.com. 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 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 --- 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 clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: atoms, memoize, future-s and CAS
On 7 December 2014 at 05:13, Andy L core.as...@gmail.com wrote: The SoftCache uses a ConcurrentHashMap, but that caching option isn't used in core.memoize. Are you building a custom memoizer? WRT ConcurrentHashMap, it was an incorrect conclusion on my part. In any case, I fail to see thread safety in the cache implementation, but again I could be wrong. Or it might not be needed for 99.99% cache use cases. Also, at that point I would like to avoid to defcache my own version. Most of the cache implementations in core.cache have no side-effects. They simply return a new cache rather than overwriting the old one. The memoize library places the cache in an atom, so it's guaranteed to change atomically. So I ended up with this (this is my first LISP macro ever, so please be gentle :-) : (defmacro when-map-future-swap! [a k f] `(locking ~a (when (not (contains? @~a ~k)) (swap! ~a assoc ~k nil) (future (swap! ~a assoc ~k (~f ~k))) ) ) ) You could write this as a function. There's nothing in there that requires a macro. (defn when-map-future-swap! [a k f] (locking a (when-not (contains? @a k) (swap! a assoc k nil) (future (swap! a assoc k (f k)) But I'd personally just use a delay rather than locking for this purpose. - James -- 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 --- 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 clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
atoms, memoize, future-s and CAS
Hi,
Here is the situation. There is a function f retrieving some data from
various sources (including reading files, a lot of io, e.g. map-reduce)
expected by design to return the same result for given input. Results of
f invocation from parallely running futures are stored in an atom wrapped
map and everything works just fine.
With a small exception when f invocations with the same arguments
overlap - the same expensive io is kicked off 2 or more time s. Not a
tragedy, but still very unpleasant and wasteful. The expectation would be
that a subsequent f call would just bail without doing anything while
initial invocation assoc new data into an atom,
The first intuition was to use memoize, however I do not think its
semantics fit well into this case, since the result is a side-effect on
an atom as opposed to return value.
The easiest solution, is to create another atom with a map of the arguments
into a state. If some other future is already there working hard on the
problem, we simply bail. However, that leads to another problem.
compare-and-set! just operates on atoms as wholes, which is fine for
unstructured data, but falls short for things somewhat more complex,
like here.
While updating an atom in this context is trivial:
user= (def a (atom {}))
user= (swap! a assoc [arg1 arg2] :PENDING)
{[arg1 arg2] resultA}
I would like to link the condition and future together somehow like that:
user= (when ((complement contains?) @a [arg1 arg3]) (swap! a assoc
[arg1 arg3] :PENDING ))
That obviously will not work, unless I wrap it with locking, which is not
necessarily a nice thing to do. I also tried to use refs here, however they
do not fit well here either and the solution is not as nice as it could be.
After that long introduction, I would like ask for some insight Thanks
in advance ...
Best,
Andy
--
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
---
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 clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
Re: atoms, memoize, future-s and CAS
It sounds like you want a delay. Delays are guaranteed to execute their
body only once, so we can combine a delay with an atom:
(defn memoized [f]
(comp deref (memoize (fn [ args] (delay (apply f args)
In theory that should produce a memoize that executes the function only
once for each set of arguments.
- James
On 6 December 2014 at 21:32, Andy L core.as...@gmail.com wrote:
Hi,
Here is the situation. There is a function f retrieving some data from
various sources (including reading files, a lot of io, e.g. map-reduce)
expected by design to return the same result for given input. Results of
f invocation from parallely running futures are stored in an atom wrapped
map and everything works just fine.
With a small exception when f invocations with the same arguments
overlap - the same expensive io is kicked off 2 or more time s. Not a
tragedy, but still very unpleasant and wasteful. The expectation would be
that a subsequent f call would just bail without doing anything while
initial invocation assoc new data into an atom,
The first intuition was to use memoize, however I do not think its
semantics fit well into this case, since the result is a side-effect on
an atom as opposed to return value.
The easiest solution, is to create another atom with a map of the
arguments into a state. If some other future is already there working
hard on the problem, we simply bail. However, that leads to another problem.
compare-and-set! just operates on atoms as wholes, which is fine for
unstructured data, but falls short for things somewhat more complex,
like here.
While updating an atom in this context is trivial:
user= (def a (atom {}))
user= (swap! a assoc [arg1 arg2] :PENDING)
{[arg1 arg2] resultA}
I would like to link the condition and future together somehow like that:
user= (when ((complement contains?) @a [arg1 arg3]) (swap! a assoc
[arg1 arg3] :PENDING ))
That obviously will not work, unless I wrap it with locking, which is
not necessarily a nice thing to do. I also tried to use refs here, however
they do not fit well here either and the solution is not as nice as it
could be.
After that long introduction, I would like ask for some insight
Thanks in advance ...
Best,
Andy
--
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
---
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 clojure+unsubscr...@googlegroups.com.
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 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
---
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 clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
Re: atoms, memoize, future-s and CAS
(defn memoized [f] (comp deref (memoize (fn [ args] (delay (apply f args) Thanks for looking into that. This indeed would solve a semantics problem of memoize, as it returns a value now. However, it seems that clojure.core.memoize, or rather clojure.core.cache memoize is based of, is not thread safe. It uses ConcurrentHashMap's put under the hood, instead of atomic putIfAbsent. I might be completely wrong here though. Cheers, Andy -- 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 --- 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 clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: atoms, memoize, future-s and CAS
On 7 December 2014 at 01:13, Andy L core.as...@gmail.com wrote: Thanks for looking into that. This indeed would solve a semantics problem of memoize, as it returns a value now. However, it seems that clojure.core.memoize, or rather clojure.core.cache memoize is based of, is not thread safe. It uses ConcurrentHashMap's put under the hood, instead of atomic putIfAbsent. I might be completely wrong here though. The SoftCache uses a ConcurrentHashMap, but that caching option isn't used in core.memoize. Are you building a custom memoizer? - James -- 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 --- 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 clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: atoms, memoize, future-s and CAS
The SoftCache uses a ConcurrentHashMap, but that caching option isn't used
in core.memoize. Are you building a custom memoizer?
WRT ConcurrentHashMap, it was an incorrect conclusion on my part. In any
case, I fail to see thread safety in the cache implementation, but again
I could be wrong. Or it might not be needed for 99.99% cache use cases.
Also, at that point I would like to avoid to defcache my own version.
So I ended up with this (this is my first LISP macro ever, so please be
gentle :-) :
(defmacro when-map-future-swap! [a k f]
`(locking ~a
(when (not (contains? @~a ~k))
(swap! ~a assoc ~k nil)
(future (swap! ~a assoc ~k (~f ~k)))
)
)
)
Which seems to do what I need:
user= (defn f[k] (Thread/sleep 3000) k)
#'user/f
user= (when-map-future-swap! a arg f)
#core$future_call$reify__6320@a7f0cb9: :pending
user= a
#Atom@71d68915: {arg nil}
user= (Thread/sleep 4000)
nil
user= a
#Atom@71d68915: {arg arg}
Andy
--
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
---
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 clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
Re: atoms, memoize, future-s and CAS
or even better (using future themselves as a marker in the atom): (defmacro map-future-swap! [a k f] `(locking ~a (when (not (contains? @~a ~k)) (swap! ~a assoc ~k (future (swap! ~a assoc ~k (~f ~k ) ) ) -- 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 --- 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 clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
