Chinese Whispers in Go, Racket and Other Languages

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!)
:

About these ads