Any help to see what needs to be done?

Hello,

I try to learn clojure and my first steps is that I try to follow the “Clojure from the ground up” book before IM going try the brave book.

But I have totally no idea what I should do here and what the 2 closures must do

Instead of using a lazy list, imagine two threads are removing tasks from a pile of work. Our work pile will be the list of all integers from 0 to 10000:
user=> (def work (ref (apply list (range 1e5))))
user=> (take 10 @work)
(0 1 2 3 4 5 6 7 8 9)And the sum will be a ref as well:
user=> (def sum (ref 0))Write a function which, in a dosync transaction, removes the first number in work and adds it to sum.
Then, in two futures, call that function over and over again until there's no work left. Verify that @sum is 4999950000. Experiment with different combinations of alter and commute–if both are correct, is one faster? Does using deref instead of ensure change the result?
` ``

can anyone help me figure this out ? 
So what schould the closures do and why I need 2 

Regards, 

Roelof

I haven’t read ”Clojure from the ground up”, so might not be getting this right. But it seems like you are supposed to learn about refs, transactions and futures here. So checking out these links might give you some clues:

With docync and alter you are able to do the first part of the exercise.

The reason you are asked to make the work happen from two futures is probably so that you can examine how transactions ensure that things are being done in order, even though the refs are manipulated from different threads.

oke, so both futures do the same ?

here is the page : https://aphyr.com/posts/306-clojure-from-the-ground-up-state

That’s an awesome page. Thanks!

Yes, I think both futures can do the same at first. But you are also encouraged to use alter in one and commute in the other, if I am understanding it right.

oke

I hope im here then on the right track.
:

(defn add-dosync []
  (dosync
  (alter sum4 + (first @work))
  (alter work rest)))


(defn future1 [] 
  (future @work add-dosync))

(defn future2[] 
  (future @work add-dosync))

(deref sum4)

but the answer keeps zero

You need to take from this list, meaning it should remove the taken number from the list (that’s the first mutable change you need), and then you need to add the number to the sum (the second mutable change you need).

This means you need two mutable things. Well in Clojure everything is immutable by default, but you can create mutable things, and ref is one way to do it. It creates a mutable reference.

So now you have a mutable reference to the list of work, and a mutable reference to the sum. To change a ref, there’s a few functions you can use such as: ref-set, alter and commute.

To get and remove from the list you can do:

(first @work) ;; reads first
(ref-set work (next @work)) ;; removes first from ref

To add to sum you can do:

(alter sum + (first @work))

ref-set will just set the value to the new value, where as alter will take the old value and the new value and compute a new value from them. That’s why for sum we use alter, but for removing from work we use ref-set.

So putting it all together you have:

(defn dowork
  [work-ref sum-ref]
  (dosync
    (when-let [n (first @work-ref)] ; avoid null exception so we don't try to add nil to sum
      (alter sum-ref + n)
      (ref-set work-ref (next @work-ref)))))

Okay, but why are we even using dosync here? Well, only because the problem then tells you that you should have multiple workers doing work concurrently. That means you need a way to coordinate them, so that they don’t do the same work more than once, or overwrite each other’s work.

For example, you don’t want two of them adding the same number to sum, that will skew the result. Similarly, you don’t want one of them to change the sum back to a prior state while the other has already removed the number, again that will skew your result.

This is where dosync comes in. It basically defines the atomic unit of work that each worker can do, and a means for them to check with others if they are about to overlap or overwrite each other so that they don’t.

This is done pretty simply. The worker who enters a dosync will get the next number from work, and the current value of sum, it’ll remove the item and update the sum on its own workstation, but before commiting the changes back to the ref, it’ll check if anyone else changed the ref while they were working. If so, the worker will realize that they can’t commit, and need to rebase their changes against the new ref value, and then they’ll try to commit again, until they manage to get in.

So how do you create two workers and have them work concurrently? Well future is one way to do so.

(future (dowork work sum))

Will spawn one worker and have them do work. If you want to spawn two workers you just do:

(future (dowork work sum))
(future (dowork work sum))

Ok, but we don’t want them to add only once and stop working. We want them to work until there is no more work. So we need a loop:

(future (while @work (dowork work sum)))

This will have them work until there is no more work. Note how in dowork I use next and not rest, that’s really important here, because next will return nil when empty, and nil is falsy, which will make the condition in our loop false and thus have them stop.

Alright, but how do you know when they are done? And how do we wait for them to be done before doing something else? Like printing the result of the work being done? Well you can block on the future by derefing on them.

; Spawn two concurrent workers working until there is no more work
(let [work (ref (apply list (range 1e5)))
      sum (ref 0)
      worker1 (future (while @work (dowork work sum)))
      worker2 (future (while @work (dowork work sum)))]
  @worker1 ;wait for worker1
  @worker2 ;wait for worker2
  @sum) ;return the result of their work

There you go.

Now the question has you experiment further with using commute instead of ref-set and alter. That’s an optimization, you can see how summing is a commutative operation, so when your modification is commutative, you can use commute instead of alter, and it’ll be faster. That’s because the workers won’t check that they are doing things in-order, which lets them go faster, but only works if you can do things in any order, like for sum.

Finally the question has you experiment between deref and ensure. That part I’m also a bit confused here, I guess the answer is no, normally you use ensure when you only read from a ref and care that the ref value changes while you were working. Which isn’t the case here, so I guess the answer is no, it won’t make a difference here. That said, I wonder if it could affect the profiling, I don’t know enough to say, but it’s possible ensure would be more strict about having the worker redo work.

1 Like

I haven’t played with refs and transactions in years. Most of my concurrency stuff these days is done via core.async. Take that as a disclaimer. The following code works, but took some finagling to ensure appropriate dosync blocks in certain places. I’m also not seeing expected speedups as more workers are added, although there is some thread contention. It’s possible I choked down concurrency too much with too many transactional blocks…although the answer is computed correctly.

(def work (ref (seq (range 1e5))))
(def sum  (ref 0))


(defn work-by-set! []
  (dosync
   (when-let [n (first @work)]
     (ref-set work (rest @work))
     (ref-set sum (+ n @sum)))))

(defn work-by-alter! []
  (dosync
   (when-let [n (first @work)]
     (alter work rest)
     (alter sum + n))))

(defn work-by-commute! []
  (dosync
   (when-let [n (first @work)]
     (alter work rest)
     (commute sum + n))))

(defn go-work! [work-fn]
  (future (loop []
            (dosync
             (if-let [new-sum (work-fn)]
               (recur)
               @sum)))))

(defn first-to-complete [n work-fn]
  (let [result (promise)]
    (doseq [n (range n)]
      (future (deliver result @(go-work! work-fn))))
    @result))

(defn simple-test [n work-fn]
  (dosync
   (ref-set work (seq (range 1e5)))
   (ref-set sum 0))
  (first-to-complete n work-fn))

(defn alter-test [n]
  (simple-test n work-by-alter!))

(defn commute-test [n]
  (simple-test n work-by-commute!))

(defn refset-test [n]
  (simple-test n work-by-commute!))

There’s something happening where more parallelization actually slows things down. Here’s an example, I made each unit of work more computer intensive by summing naïve Fibonacci to reduce the ref book-keeping overhead, but it still shows that more parallelization makes things slower:

(defn fib
  [n]
  (case n
    0 0
    1 1
    (+ (fib (- n 1))
       (fib (- n 2)))))

(defn dowork
  [work-ref sum-ref]
  (dosync
    (when-let [n (first @work-ref)] ; avoid null exception so we don't try to add nil to sum
      (alter sum-ref + (fib n))
      (ref-set work-ref (next @work-ref)))))

(time
  (reduce #(+ %1 (fib %2)) 0 [30 31 32 33 34 35]))
"Elapsed time: 5966.5828 msecs"
22811548

(time
  (let [work (ref [30 31 32 33 34 35])
        sum (ref 0)
        num-of-workers 1
        workers (mapv (fn[_] (future (while @work (dowork work sum)))) (range num-of-workers))]
    (run! deref workers)
    @sum))
"Elapsed time: 5944.0034 msecs"
22811548

(time
  (let [work (ref [30 31 32 33 34 35])
        sum (ref 0)
        num-of-workers 4
        workers (mapv (fn[_] (future (while @work (dowork work sum)))) (range num-of-workers))]
    (run! deref workers)
    @sum))
"Elapsed time: 7281.6213 msecs"
22811548

(time
  (let [work (ref [30 31 32 33 34 35])
        sum (ref 0)
        num-of-workers 6
        workers (mapv (fn[_] (future (while @work (dowork work sum)))) (range num-of-workers))]
    (run! deref workers)
    @sum))
"Elapsed time: 11090.3298 msecs"
22811548

Deep Dive

One thing I noticed is there seems to be a really high amount of contention which forces the transactions to rollback and retry often.

(defn dowork
  [work-ref sum-ref attempts]
  (dosync
    (when-let [n (first @work-ref)] ; avoid null exception so we don't try to add nil to sum
      (swap! attempts inc)
      (alter sum-ref + (fib n))
      (ref-set work-ref (next @work-ref)))))

(time
  (let [work (ref [30 31 32 33 34 35])
        sum (ref 0)
        num-of-workers 6
        workers (mapv
                  (fn[_]
                    (let [attempts (atom 0)]
                      (future (while @work (dowork work sum attempts))
                        @attempts)))
                  (range num-of-workers))]
    [(mapv deref workers) @sum]))
"Elapsed time: 10679.0423 msecs"
[[6 6 6 6 6 6] 22811548]

You can see that 36 attempts were made, each worker picks up each of the 6 work items and tries to compute them. That means there will be 30 rollbacks.

And if you think about it, this makes sense. All workers pick up the first item, compute fib, try to sum it over sum-ref, one of them will succeed, others will fail, so they will retry the whole transaction, thus all workers will now be reading from work-ref again, getting the second item, compute the fib, try to add it to sum-ref, only one will succeed, others will fail and retry the whole transaction, etc.

So really, we are computing fib 36 times, because of all the retries due to contention on the refs.

(defn fib
  ([n fib-count]
   (swap! fib-count inc)
   (fib n))
  ([n]
   (case n
         0 0
         1 1
         (+ (fib (- n 1))
            (fib (- n 2))))))

(defn dowork
  [work-ref sum-ref fib-count]
  (dosync
    (when-let [n (first @work-ref)] ; avoid null exception so we don't try to add nil to sum
      (alter sum-ref + (fib n fib-count))
      (ref-set work-ref (next @work-ref)))))

(time
  (let [work (ref [30 31 32 33 34 35])
        sum (ref 0)
        fib-count (atom 0)
        num-of-workers 6
        workers (mapv (fn[_] (future (while @work (dowork work sum fib-count)))) (range num-of-workers))]
    (run! deref workers)
    [@sum @fib-count]))
"Elapsed time: 10585.9375 msecs"
[22811548 36]

It’s actually quite impressive that even though it computes each fib 6 times, it only takes about twice as much time as the single threaded version to complete.

Commute also doesn’t help us here, because we can only make (alter sum-ref + (fib n fib-count)) into (commute sum-ref + (fib n fib-count)), but the removing the work item from the list is not commutative, doing so gives us the wrong result, and so changing only the summing to commute still will have all workers retry once they try to remove the item, and it doesn’t help them not all compute all fibs. But if we did:

(defn dowork
  [work-ref sum-ref fib-count]
  (dosync
    (when-let [n (first @work-ref)] ; avoid null exception so we don't try to add nil to sum
      (commute sum-ref + (fib n fib-count))
      (commute work-ref next))))

(time
  (let [work (ref [30 31 32 33 34 35])
        sum (ref 0)
        fib-count (atom 0)
        num-of-workers 6
        workers (mapv (fn[_] (future (while @work (dowork work sum fib-count)))) (range num-of-workers))]
    (run! deref workers)
    [@sum @fib-count]))
"Elapsed time: 3154.6583 msecs"
[26971748 11]

Things are considerably faster, at only 3154ms, which is twice as fast as the single-threaded version, but it gives us a sum of 26971748 which is wrong, the correct sum is 22811548. That’s because, as we see from the example, fib was called 11 times, because we didn’t synchronize the removing of items, some workers picked up duplicate items and committed their work even though it was a duplicate.

Conclusion

Well, I’m not really sure what to conclude here. I guess when you use ref, you have to be careful with how much contention you’ll have, because retrying a transaction can be pretty costly, either because the work done in the transaction is expensive (like in my example with fib), or because each retry adds a lot of overhead (why it was also slower when only summing over range).

Using locking as an alternative wouldn’t help either, since locking will basically simulate single threaded, it’ll cancel all parallelization as even though there’s multiple workers, only one will do the work at a time while the others wait on the lock. That said, in this case, locking would be faster, since it will only compute fib 6 times, but it also won’t be faster than the single threaded approach.

So, I don’t really know when you’d want to use ref to be honest. I can’t really think of a scenario where it would speed things up? Any ideas?

Edit: My only thought right now is STM (and refs) are not for performance, but really they are for if you’re already in a multi-threaded application, and have some shared variables that need to be synchronized for correctness, using STM and ref will let you do that in a way that can’t deadlock, where as using locking is at risk of deadlock. So I think ref is for correctness in concurrent scenarios, not for performance.

Edit2: Okay, I think in a scenario where you have single writer, multiple readers, than STMs can make things more performant and correct. With locking, you also need to lock the readers until the writer is done, not so with ref. That would probably be a case where they are faster than locking (as well as being safer). Similarly, commuters are also not blocked, so if some writers are only doing commutative transactions those scenarios will also be faster than locking.

1 Like

Thanks for the long explanation but there is a syntax error somewhere in the future.

and now I get a classcastexception

(def work (ref (apply list (range 1e5))))


; And the sum will be a ref as well:
(def sum4 (ref 0))

; Write a function which, in a dosync transaction, removes the first number in 
; work and adds it to sum. Then, in two futures, call that function over and 
; over again until there’s no work left. Verify that @sum is 4999950000. 
; Experiment with different combinations of alter and commute–if both are 
; correct, is one faster? Does using deref instead of ensure change the result?

(defn add-dosync [work sum4]
  (dosync
  (alter (ensure sum4) + (first @work))
  (ref-set work (next @work))))


(let [worker1 (future (while @work (add-dosync work @sum4)))
      worker2 (future (while @work (add-dosync work @sum4)))]
@worker1 ;wait for worker1
@worker2 ;wait for worker2
@sum4) ;return the result of their work

(deref sum4)

Like I said on reddit:

Per the documentation ensure “Returns the in-transaction-value of
ref” not the ref. So you are invoking alter on a thing that’s not a ref, when you have

(alter (ensure sum4) + (first @work))

That’s at least one class cast exception, which is what the error would say

java.lang.Long cannot be cast to clojure.lang.Ref

Yeah, the general rule of thumb is that refs are for coordinated state and concurrency semantics, not necessarily speed. They ease the burden on modelling a bit, at the possible expense of throughput. It’s possible to get there with refs in some cases, but you have to be very wary of thread contention and retries. Given the granularity of the work, having a bunch of threads pulling and coordinating via refs probably isn’t enough to overcome contention. I remember the original ants demo (with refs) was a big deal not because of how performant it was (performance wasn’t really an issue, it ran fast enough to render at like 60fps), but because the ease of which complex coordinated state changes could be modeled.

I actually looked for opportunities to use refs over the years, and honestly haven’t found a consistent use. I also tend to migrate toward core.async these days. I remember stuff like megaref being a thing, but they didn’t seem to catch on much either. I don’t know if that’s a comment on the general utility of refs or the community’s capacity to use them effectively.

I’m not at a computer, but I think on top of what @joinr said, it also seems you’re passing the value of sum4 to add-dosync, you want to pass the ref instead:

(future (while @work (add-dosync work sum4)))

Also, (deref sum4) at the end is redundant, you are already calling @sum4 at the end of the let. If you didn’t know: @ref and (deref ref) are the same thing, just two different syntax.

Thanks,

Solved it like this
I hope it good clojure

(def work (ref (apply list (range 1e5))))


; And the sum will be a ref as well:
(def sum4 (ref 0))

; Write a function which, in a dosync transaction, removes the first number in 
; work and adds it to sum. Then, in two futures, call that function over and 
; over again until there’s no work left. Verify that @sum is 4999950000. 
; Experiment with different combinations of alter and commute–if both are 
; correct, is one faster? Does using deref instead of ensure change the result?

(defn add-dosync [work-ref sum-ref]
  (dosync
    (when-let [work (seq (deref work-ref))]
      (alter sum-ref + (first work))
      (ref-set work-ref (next work)))))


(let [worker1 (future (while @work (println "1:" (first @work))(add-dosync work sum4)))
      worker2 (future (while @work (add-dosync work sum4)))]
@worker1 ;wait for worker1
@worker2 ;wait for worker2
@sum4) ;return the result of their work

Glad you got it to work.