parallelization of nbody.go

[Sebastian Koch]

Hi!

I tried to parallelize nbody.go from go/test/bench/ 

I succeeded in producing compiling code that computes the same values as the non parallel version by adapting http://golang.org/doc/effective_go.html#chan_of_chan

However my "parallel" version is much slower than the sequential version. 

I suspect the overhead of using channels and starting goroutines is bigger than the speedup from the parallelization.

I attached the whole code to this email but the interesting parts are the following:

func (body Body) computeForce(body2 Body, dt float64, c chan Result, i,j int){

    res := new(Result);

    

    res.i = i;

    res.j = j;

    dx := body.x - body2.x;

dy := body.y - body2.y;

dz := body.z - body2.z;

dSquared := dx*dx + dy*dy + dz*dz;

distance := math.Sqrt(dSquared);

mag := dt / (dSquared * distance);

res.vx = dx * body2.mass * mag;

res.vy = dy * body2.mass * mag;

res.vz = dz * body2.mass * mag;

    res.vx2 = dx * body.mass * mag;

res.vy2 = dy * body.mass * mag;

res.vz2 = dz * body.mass * mag;

  c <- *res;

}

func (sys System) advance(dt float64) {

  N := ((len(sys)*(len(sys)-1))/2);

  c := make(chan Result, N);  // Buffering optional but sensible.

  for i, body := range sys {

for j := i+1; j < len(sys); j++ {

go body.computeForce(*sys[j], dt, c, i, j);

}

}

  // Drain the channel.

  for i := 0; i < N; i++ {

      res := <-c;

      sys[res.i].vx -= res.vx; 

      sys[res.i].vy -= res.vy; 

      sys[res.i].vz -= res.vz; 

      sys[res.j].vx += res.vx2; 

      sys[res.j].vy += res.vy2; 

      sys[res.j].vz += res.vz2; 

  }

  // All done.

for _, body := range sys {

body.x += dt * body.vx;

body.y += dt * body.vy;

body.z += dt * body.vz;

}

}

Is my assumption right or am I doing something wrong in my code that slows it down?

greets

Sebastian

[David]

I *think* what's slowing it down is the blocking nature of channels.
The goroutines have little effect on run time as far as I can tell.
I'm still getting used to Go, but I think what could be slowing it
down is draining the channels (specifically res := <-c; )

real 0m0.029s -- with goroutines
real 0m0.024s -- without goroutines

[Ian Lance Taylor]

Sebastian Koch <sebi...@gmail.com> writes:

> I tried to parallelize nbody.go from go/test/bench/
> I succeeded in producing compiling code that computes the same values as the non parallel version by adapting http://golang.org/doc/effective_go.html#chan_of_chan
> However my "parallel" version is much slower than the sequential version.
>
> I suspect the overhead of using channels and starting goroutines is bigger than the speedup from the parallelization.

Your goroutine doesn't seem to have any loops--it's just straight line
code--so it certainly seems plausible that the overhead of creating a
new goroutine is dominating the speedup of parallelization.
Goroutines are cheap but they aren't free. They are more expensive
than a function call.

Ian

[Jon Harrop]

On Friday 13 November 2009 23:30:55 Ian Lance Taylor wrote:
> Goroutines are cheap but they aren't free. They are more expensive
> than a function call.

Can you quantify this?

--
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

[Maradatscha]

My intention with this little test was to find out how fine grained
the parallization can be in go.

The work that is being done in each goroutine is very small in this
case, my guess is that if the work is bigger the goroutines make more
sense.

I'll try to do some tests on the weekend to get a feeling of how much
overhead a goroutine produces.

Sebastian

[Ian Lance Taylor]

Jon Harrop <j...@ffconsultancy.com> writes:

> On Friday 13 November 2009 23:30:55 Ian Lance Taylor wrote:
>> Goroutines are cheap but they aren't free. They are more expensive
>> than a function call.
>
> Can you quantify this?

I don't have good measurements, no.

I think it would not be too hard for somebody to produce these
measurements, but of course we are still improving and tuning the
runtime.

Ian