Re: [Gc] parallel speedup

On Tue, Jun 24, 2014 at 07:46:01PM -0400, Daniel R. Grayson wrote:
> In our application that uses libgc (see http://macaulay2.com/) I observe no
> speedup when running tasks in parallel, if the tasks allocate memory using
> libgc.  Perhaps I'm doing something wrong.  Are there any commonly observed
> situations where no speedup occurs?
> 
> A glance at the source code shows that mutex locks lock down the world on
> almost every occasion, so it's hard to see why there would ever be any
> speedup
> when using threads.

I've found that when a collector (like Boehm GC) is involved then you're
fighting Amdahl's law.  This means that you often get less speedup than you
would expect.

Lets say you spend 50% of your time in the mutator (your program) and 50% of
time in the collector (When the collector runs).  If you parallelise the
mutator using four processors, and the collector is not parallelised then
your best case speedup isn't 4x, it's:

    Sequential time = 0.5 + 0.5
    Parallel time = 0.5 / 4 + 0.5
                  = 0.625

    Speedup = 1 / 0.625
            = 1.6

So the program runs 1.6 times faster than the sequential one.  When naively
you might have expected it to run 4 times faster.

The marking phase of Boehm GC is parallelised, so the situation is a bit
better, but AIUI parallelising a marking phase is difficult, so it's likely
to be far from a perfect theoretical speedup.

I did some testing for my thesis including calculating how much of the
program's time is spent in the mutator and collector.  See section 3.1
http://www.mercurylang.org/documentation/papers.html#pbone_phd_thesis

I found that on a program that was theoretically trivial to parallelisable,
but which allocated a lot of memory for intermediate data (a raytracker).  I
got a speedup of 1.58 from using four application threads, and 1.29 when
using four marker threads, and when I used 4 threads for the application and
four threads for the merker the speedup was 2.73.  When running sequentially
the same program spends 55% of it's time in the mutator and 45% of it's time
in the collector.  This program allocates memory at 26.9MB/s (without thread
safety).  One of the easiest ways to tune for better performance was to
increase the initial heap size.

I hope this is helpful.


-- 
Paul Bone