On Wed, Dec 1, 2010 at 4:50 AM, Alex Osborne <a...@meshy.org> wrote:
> 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
Interesting.
> 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.
It looks an awful lot like swap! itself is implemented with a polling
sleeplock instead of using the language's own lock. :)
> 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).
Most of the various proposals here would have that effect. I expect
they may differ as to their efficiency, though, and perhaps different
ones would be more efficient under a) high contention and b) low
contention. I expect that there's been research done on such matters
by theorists, but I'm not sure to what extent that's informed the
design of either Java or Clojure...
>>> 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.
I expect the compare it does uses .equals rather than ==?
> Finally, the atom is a safer concurrency primitive, it's impossible to
> deadlock (unless you implement a lock with one, of course).
It seems to me that it is still possible to "livelock" with this sort
of thing (and with dosync as well) if the system ends up spending a
very large percentage of time in retries. On the other hand, with a
deadlock it would just plain hang and avoiding deadlocks can be very
complicated; whereas every time several transactions try to go through
at the same time at least *one* of them should succeed, so the system
will always be making progress and won't completely hang, and
adjusting things like the granularity of your refs can reduce
contention while at the same time you don't have to worry about
locking order and deterministic symmetry-breaking and all that stuff
to try to keep deadlocks from happening.
--
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
