The thread ring problem

[Alvaro Vilanova Vidal]

Hi everyone,
I am a newbie in clojure world, so I have some newbie's questions :) To learn about clojure, I am trying to do the thread ring problem of clgb in clojure. The rules of problem are here, and my attempt here. It seems that works well, but I can only test it with a small load (5 - 15 threads, 503 is the target) because it runs extremely slow. I tried to use atoms, hints, and change the implementation, but always is slower. What am I doing wrong? And, by the way, why can't I compile the class?

Thanks a lot.

[Christian Vest Hansen]

For kicks, I made an implementation* using agents:

http://gist.github.com/119946

I think that you may not want to use the STM so much and instead
figure out a different approach to sending the token around the ring.

*it may be a bit liberal in its interpretation of the rules... didn't
read them that carefully.

--
Venlig hilsen / Kind regards,
Christian Vest Hansen.

[graham]

Have you seen the example on the agents page of the main clojure site?

http://clojure.org/agents

[Laurent PETIT]

Hi,

didn't take time to analyse why, but your solution sends a

java.util.concurrent.RejectedExecutionException

when I try it with the 50,000,000 number of times the token is
exchanged (which is the number to be used for the benchmark)

2009/5/29 Christian Vest Hansen <karma...@gmail.com>:

[Laurent PETIT]

Sorry, I understood that the (shutdown-agents) call is certainly
responsible for this.

2009/5/29 Laurent PETIT <lauren...@gmail.com>:

[Michael Wood]

On Fri, May 29, 2009 at 3:29 PM, Christian Vest Hansen
<karma...@gmail.com> wrote:
>
> For kicks, I made an implementation* using agents:
>
> http://gist.github.com/119946

The call to time returns almost immediately and the actual result
takes much longer to appear (with large values of token). How would
one fix this?

> I think that you may not want to use the STM so much and instead
> figure out a different approach to sending the token around the ring.
>
> *it may be a bit liberal in its interpretation of the rules... didn't
> read them that carefully.

--
Michael Wood <esio...@gmail.com>

[Christian Vest Hansen]

On Fri, May 29, 2009 at 4:29 PM, Laurent PETIT <lauren...@gmail.com> wrote:
> when I try it with the 50,000,000 number of times the token is
> exchanged (which is the number to be used for the benchmark)

Oh, right. I only noticed the 1000 mentioned at the bottom. Also, the
(time ...) makes no sense.

> How would one fix this?

With a CountDownLatch? That's what I'm currently trying.

[Alvaro Vilanova Vidal]

Thanks, seems that I misunderstood Agents :)

The solution of Christian works well with full load, but maybe slow for the benchmark. In my core2duo, with full load, takes about 28mins to compute the result.

user=> (do (println (System/nanoTime)) (start 50000000))
22651751153117
#<Agent@27a897a9: 1>
user=> 292 ( 24319344452689 )
user=> (/ (- 24319344452689 22651751153117) 60000000000.0)      
27.793221659533334

--
Álvaro Vilanova,
http://alvivi.com

[Laurent PETIT]

Hi,

Here is my attempt, for the real benchmark test, it has an honorable
result of 62 sec. (if there is no flaw in my algorithm, of course).

;; file shootout/ring.clj
(ns shootout.ring
(:gen-class))

(def n-threads 503)
(def nb-pass 50000000)

(defn main
"main function calling the benchmark test."
[n-threads N print-result-fn]
(let [start-time (System/nanoTime)
agents (into [] (map #(agent {:name (inc %)}) (range n-threads)))
send-to (fn this [i token-val]
(send (nth agents (mod i n-threads))
(fn [state t-val]
(if (= t-val N)
(print-result-fn (:name state) start-time)
(this (inc i) (inc t-val)))
state)
token-val))]
(send-to 0 0)
nil))

(defn repl-print-result-fn [thread-id start-time]
(println "\n"
"thread number: " thread-id "\n"
"time (secs): " (/ (- (System/nanoTime) start-time) 1000000000.0)))

(defn benchmark-print-result-fn [thread-id _]
(println thread-id))

(defn -main []
(main n-threads nb-pass benchmark-print-result-fn))

(defn repl-test [nb-pass]
(main n-threads nb-pass repl-print-result-fn))

;; repl session
Clojure
1:1 user=> (use 'shootout.ring)
nil
1:2 user=> (do (repl-test 1000) (repl-test 50000000))
nil
1:3 user=>
thread number: 498
time (secs): 0.128037133

thread number: 292
time (secs): 62.724999733

on a recent machine

(and yes, I know something similar is on the clojure agents page, but
sometimes it's rewarding not to look at the solution too early :-)

Cheers,

--
Laurent

2009/5/29 Alvaro Vilanova Vidal <alv...@gmail.com>:

[Sean Devlin]

Would type hints help at all?

> > 2009/5/29 Christian Vest Hansen <karmazi...@gmail.com>
>
> >> On Fri, May 29, 2009 at 4:29 PM, Laurent PETIT <laurent.pe...@gmail.com>

> >> wrote:
> >> > when I try it with the 50,000,000 number of times the token is
> >> > exchanged (which is the number to be used for the benchmark)
>
> >> Oh, right. I only noticed the 1000 mentioned at the bottom. Also, the
> >> (time ...) makes no sense.
>
> >> > How would one fix this?
>
> >> With a CountDownLatch? That's what I'm currently trying.
>

> >> > 2009/5/29 Christian Vest Hansen <karmazi...@gmail.com>:

[Laurent PETIT]

Hi,

here is a second attempt, partly inspired by clojure's agents page,
that looks better (true direct ring of agents, not just indirect ring
via vector), and that performs similarly to my first attempt.

Still room for progress, though.

(ns shootout.ring2

(:gen-class))

(def n-threads 503)
(def nb-pass 50000000)

(defn agent-fn [state token-val stop-val print-result-fn start-time]
(if (= token-val stop-val)

(print-result-fn (:name state) start-time)

(send (:next state) agent-fn (inc token-val) stop-val
print-result-fn start-time))
state)

(defn main
"main function calling the benchmark test."
[n-threads N print-result-fn]

(let [agent-n (agent {:name n-threads :next nil})
agent-1 (reduce (fn [a n] (agent {:name n :next a})) agent-n
(range (dec n-threads) 0 -1))]
(send agent-n assoc :next agent-1)
(send agent-1 agent-fn 0 N print-result-fn (System/nanoTime))

nil))

(defn repl-print-result-fn [thread-id start-time]
(println "\n"
"thread number: " thread-id "\n"
"time (secs): " (/ (- (System/nanoTime) start-time) 1000000000.0)))

(defn benchmark-print-result-fn [thread-id _]
(println thread-id))

(defn -main []
(main n-threads nb-pass benchmark-print-result-fn))

(defn repl-test [nb-pass]
(main n-threads nb-pass repl-print-result-fn))

2009/5/29 Sean Devlin <francoi...@gmail.com>:

[Kevin Downey]

http://gist.github.com/120289 using queues and Threads instead of agents

--
And what is good, Phaedrus,
And what is not good—
Need we ask anyone to tell us these things?