Ken Wesson <kwess...@gmail.com> writes:
> Retries? We were discussing an atom here, not a ref. A dosync
> transaction may be retried. The obvious implementation for swap! would
> be (locking inner_value (set! inner_value.contents (apply fun
> inner_value.contents))) (warning: pseudocode, I assume this stuff
> would actually be implemented in Atom.java or someplace like that in
> Java rather than in Clojure).
Sorry, I didn't explain very well. I basically said that it's not
implemented with locks, rather than how it *is* implemented. I should
have pointed at the Clojure documentation:
"Internally, swap! reads the current value, applies the function to
it, and attempts to compare-and-set it in. Since another thread may
have changed the value in the intervening time, it may have to
retry, and does so in a spin loop. The net effect is that the value
will always be the result of the application of the supplied
function to a current value, atomically. However, because the
function might be called multiple times, it must be free of side
effects."
-- http://clojure.org/atoms
The actual implementation from clojure/lang/Atom.java is quite concise
too:
public Object swap(IFn f) throws Exception{
for(; ;) {
Object v = deref();
Object newv = f.invoke(v);
validate(newv);
if(state.compareAndSet(v, newv)) {
notifyWatches(v, newv);
return newv;
}
}
}
> (let [owned (Object.)]
> (swap! the-atom #(if (= % sentinel) owned %))
> (if (= @the-atom owned)
> (reset! the-atom (do-once-fn))
> (loop []
> (if (= (.getClass @the-atom) Object)
> (do
> (Thread/sleep 10)
> (recur))
> (@the-atom)))))
>
> The interesting bit here deals with the case that the atom holds
> someone else's "owned" object instead of an actual result. The loop
> sleeps 10ms and checks repeatedly until the do-once-fn (running in
> some other thread) has completed and the atom's final value been
> assigned. It does assume that the result of do-once-fn will not be an
> unspecialized java.lang.Object.
>
> The locking version is probably cleaner than the above, but when no
> return value is needed, the code further above is short and especially
> concise; both are lock-free (given that swap! and reset! are
> lock-free, which, if they perform retries, is presumably the case).
You've actually implemented a polling sleeplock in terms of an atom.
Using the language's own lock has the benefit that long sleeping threads
do not have to keep polling and using CPU time, the OS scheduler will
wake them up when the lock is released.
Locking is semantically correct for this situation. Imagine the webapp
case, you start up the webapp and want to initialize something on
the first request. What happens if 3 requests come in simultaneously
and all hit your initialize? You want two of the threads to block and
wait while one of them does the initialization. That's locking (mutual
exclusion).
>> Atoms do not lock. If multiple threads enter swap! simultaneously, they
>> *will* each execute f. One will win and the others will retry.
>
> Eh. Why this implementation? To optimize for the common case that
> there isn't any contention?
CAS is a lower-level primitive, locks and semaphores can be
implemented using a CAS as you demonstrated. ;-)
But yes, there are potential performance benefits, depending on
contention. For example, if f does some calculation and ends up often
returning the value unchanged then multiple threads can do that
simultaneously without blocking.
Also context switching (due to blocking on a lock) is quite expensive.
However, if there's really high contention and a lot of retrying,
locking may be better from a performance perspective as it allows the
blocked thread to sleep and other tasks to run.
Finally, the atom is a safer concurrency primitive, it's impossible to
deadlock (unless you implement a lock with one, of course).
Further reading about CAS:
http://en.wikipedia.org/wiki/Compare-and-swap
http://en.wikipedia.org/wiki/Non-blocking_algorithm
--
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
