In my previous post Why Go? Use Racket!, I pointed out that CSP facilities provided with the Go programming language also exist with Racket, a Scheme dialect. However, it seems that Racket programs run much slower than their Go counterparts.
Weeks earlier, Rob Pike gave a talk Go Concurrency Patterns in Google IO 2012, where he presented an interesting demo program named Chinese Whispers. This program creates a sequence of 10,001 channels interleaved with 10,000 threads (whispers). Each thread reads from the channel to its left and writes the processed input into the channel to its right.
Here follows the Go program:
package main import "fmt" func whisper(left, right chan int) { left <- 1 + <- right } func main() { const n = 100000 leftmost := make(chan int) right := leftmost left := leftmost for i := 0; i < n; i++ { right = make(chan int) go whisper(left, right) left = right } go func(c chan int) { c <- 1 }(right) fmt.Println(<- leftmost) }
And this is what I wrote using Racket:
(let ((leftmost (make-channel))) (define (setup-whispers left i n) (if (>= i n) left (let ((right (make-channel))) (thread (lambda () (channel-put left (+ 1 (channel-get right))))) (setup-whispers right (+ 1 i) n)))) (let ((rightmost (setup-whispers leftmost 0 100000))) (thread (lambda () (channel-put rightmost 1))) (channel-get leftmost)))
Both programs output the same result 100,001. However, the running time differs significantly:
wangyi@WangYiIMac$time go run daisy-chain.go 100001 real 0m1.045s user 0m0.367s sys 0m0.231s wangyi@WangYiIMac$raco exe daisy-chain.rkt && time ./daisy-chain 100001 real 0m42.905s user 0m29.579s sys 0m11.075s
Building and running in Go costs about 1 second, but that in Racket costs about 1 minute. Racket, how did you do this??
Thanks to monad, who provided a Haskell version of the program, which runs as fast as the Go version.
import Control.Monad import Control.Concurrent chans = sequence $ replicate 100001 newEmptyMVar whisper chans = do forM_ (zip chans (tail chans)) $ \(t,f) -> forkIO $ do a <- readMVar f putMVar t (a + 1) forkIO $ putMVar (last chans) 1 takeMVar $ head chans main = chans >>= whisper >>= print
Thanks to ligong, who provided the Common Lisp version of this program:
(defpackage :whisper (:use :cl :chanl)) (in-package :whisper) (defparameter N 10000) (defun whisper(left right) "create a whsiper thread" (pcall #'(lambda () (send left (1+ (recv right)))))) (defun main() "Simulate passing message from the right most whisper to the left most" (multiple-value-bind (left-most right-most) (loop with left-most = (make-instance 'channel) repeat N for left = left-most then right for right = (make-instance 'channel) do (whisper left right) finally (return (values left-most right))) (send right-most 1) (print (recv left-most))))
Thanks to jadudm, who provides the occam-pi version:
#INCLUDE "useful.module" VAL INT N IS 100000: PROC whisper (CHAN INT left?, right!) INT v: SEQ left ? v right ! (v + 1) : PROC main (CHAN BYTE kyb?, scr!, err!) SEQ [N+1]CHAN INT whispers: PAR -- The first whisperer whispers[0] ! 1 -- N whisperers PAR i = 0 FOR N whisper (whispers[i]?, whispers[i+1]!) -- The last whisperer INT end: SEQ whispers[N] ? end -- Print the end result. out.int(end, 0, scr!) out.string("*n", 0, scr!) :