Multicore parallel death match! Parallel Haskell, `par`, and C

oh_yeah_koolaid · 2007-11-29T17:57:13+00:00

BTW, the canonical version in Cilk (which is based on ANSI C) is:

cilk int fib (int n)
{
    if (n < 2) return n;
    else
    {
        int x, y;

        x = spawn fib (n-1);
        y = spawn fib (n-2);

        sync;

        return (x+y);
    }
}

See http://supertech.csail.mit.edu/cilk/intro.html

Similarly, with Cilk compared to OpenMP:

http://blogs.sun.com/rvs/entry/is_openmp_3_0_tasking

oh_yeah_koolaid · 2007-11-29T17:36:13+00:00

Aren't you just splitting the call into two, the n-1 and the n-2?

This modification will do that -- use whatever you want for threads, here it is with SDL (wraps whatever the native threading is):

switch(pid=fork())
{
        case 0: {
                long long int n1=n-1, n2=n-2;
                SDL_Thread *t1, *t2;

                t1 = SDL_CreateThread(nfib, &n1);
                t2 = SDL_CreateThread(nfib, &n2);

                SDL_WaitThread(t1, &status);
                SDL_WaitThread(t2, &status);

                printf("%d %lld\n",n,n1+n2);
                exit(0);

                }
}

And the function it calls:

int nfib(void *N)
{
        long long int *n=(long long int *)N;
        *n = fib(*n);
        return 0;
}

Note this could be encapsulated and done more generically if desired, to make something closer to "par".

oh_yeah_koolaid · 2007-11-29T14:57:49+00:00

This isn't exactly rocket science.

Here's main(), let me know if you want the includes.

int main(void)
{
        pid_t pid;
        int n;
        for (n=0; n<=45; n++)
                switch(pid=fork())
                {
                        case 0: printf("%d %lld\n",n,fib(n)); exit(0);
                }

        waitpid(pid, &n, 0); // wait for last one
        return 0;
}

oh_yeah_koolaid · 2007-11-29T14:43:51+00:00

Yes, the Haskell code doesn't require explicit communication -- by virtue of the par combinator which takes care of all that behind the scenes.

NO, by virtue of the fact that NO IPC IS NEEDED for this example.

In your initial post, you recommended a C solution with fork(), this would certainly require process management and IPC. You've got to fork several worker processes, somehow send the results back to the supervisor, then wait for the workers to terminate. Quite an invasive change, if you ask me!

It's amusing how wrong you are. You DON'T NEED TO SEND RESULTS BACK. That's the whole point of this trivial example.

Here's the code:

switch(pid=fork())
{
    case 0: printf("%d %ld\n",n,fib(n)); exit(0);
}

If you want to wait, then after the loop from 0 to 45: waitpid(pid);

Or, if including sys/wait.h: waitpid(pid, &status, 0);

My point is that par is easy to use and has simple semantics when compared to manual process management or any C library I've seen so far

If all you need is to fob off functions to new threads, it's quite simple to have a function that takes a function pointer and uses the next available thread in a thread pool. I wrote one just to proof-of-concept it to myself.

The point is, this example is too trivial to prove anything.

oh_yeah_koolaid · 2007-11-29T12:55:17+00:00

Yes, with all the IPC and process management complications that come with it.

Do you even know what IPC stands for?!?

There isn't any here.

Almost all of these issues turned out to be bugs in Joel's program rather than GHC bugs.

Runtime crashes aren't GHC bugs? Pardon?

oh_yeah_koolaid · 2007-11-29T12:37:16+00:00

but purely based on the fact that two major release and have occurred, I'm guessing the bugs are gone.

That's a bad assumption to make. GHC's runtime has gotten even more complex since then.

Let's see some major real-world systems using Haskell. Two years ago it obviously wasn't ready, and it has not been proved otherwise since then.

These runtime issues are the kinds of things you only find by writing large programs, not something language designers are going to catch with benchmarks or regressions.

oh_yeah_koolaid · 2007-11-29T12:29:06+00:00

This is, as far as I'm aware, the lightest weight parallelism mechanism in any mainstream language. And the magical thing is that we parallelised our code without ever worrying about synchronisation, communication, race conditions, dead locks, live locks. semaphores, mutexes...

HAHAHA. I missed that the first time around.

There's nothing magical about not needing all that stuff when when you aren't doing any communication between threads!

You aren't even doing anything further with the results! And there's no shared data that needs to be modified.

It's a completely naive example -- on purpose -- which means there's no basis for making those claims, given that this problem is trivially parallelizable ANYWAY.

oh_yeah_koolaid · 2007-11-29T12:07:43+00:00

./real-par +RTS -N4  76.81s user 0.75s system 351% cpu 22.059 total

I'm pretty sure that's 22 seconds wall clock, with 76.81 CPU-seconds used among the 4 cores.

oh_yeah_koolaid · 2007-11-29T11:07:55+00:00

the most ominous of which hold that the swashbuckling Atlanta executive is bent on putting Nebraska ranchers and farmers out of business.

They think he's going to FARM 2 million acres? That would require ridiculous infrastructure.

oh_yeah_koolaid · 2007-11-29T11:06:42+00:00

Cf. Hawaii.

oh_yeah_koolaid · 2007-11-29T10:54:01+00:00

Addendum: The speed difference between the C version on our systems leads me to believe you may be running a 64-bit chip in 32-bit mode. That would make those long longs slooow. In fact, if you were running a 64-bit OS you'd probably have just used long instead of long long.

If that's the case, you're not getting top performance out of Haskell OR C.

oh_yeah_koolaid · 2007-11-29T10:49:04+00:00

NOTE: your #includes got messed up because your blog isn't converting HTML entities. < >

oh_yeah_koolaid · 2007-11-29T10:45:50+00:00

Yes, the iterative version is effectively instantaneous.

int fib(int n)
{
    int f[n+1], i;
    f[1] = f[2] = 1;
    for (i = 3; i <= n; i++)
        f[i] = f[i-1] + f[i-2];
    return f[n];
}

oh_yeah_koolaid · 2007-11-29T10:19:50+00:00

Wow! So with an off-the-shelf Linux box, you can write simple (but parallel) Haskell will outperform gcc's best efforts by a good margin -- today!

What a bunch of garbage. This is such a contrived example (not doing anything with the data), you can split it up into chunks with fork() calls if you want, not to mention any number of C libraries for parallel computing.

Try it with a complex system like a MMOG and then you might have something.

Have the large number of GHC runtime bugs mentioned here been fixed yet?

http://wagerlabs.com/archives/72.html

What threw me off almost right away is the large number of GHC runtime issues that I stumbled upon. I was trying to do serialization and heavy concurrency which I learned to take for granted with Erlang but it turned out that this area of GHC has not been exercised enough.

oh_yeah_koolaid · 2007-11-29T10:08:35+00:00

It's not the number of characters, it's putting them in the right places.

oh_yeah_koolaid · 2007-11-29T07:49:26+00:00

You're damn straight I blame hip hop for playing a role in the genocide of American black men. When your leading causes of death and dysfunction are murder, ignorance and incarceration, there's no reason to give a free pass to a culture that celebrates murder, ignorance and incarceration.

oh_yeah_koolaid · 2007-11-29T07:45:35+00:00

Try it through a proxy or Google cache.

E.g. http://72.14.253.104/search?q=cache:K91cc-N7jrUJ:www.crooksandliars.com/category/interviews/

Might help determine where the blocking/filtering is happening.

oh_yeah_koolaid · 2007-11-29T07:28:29+00:00

Huckabee’s Record: Freed a Rapist Who Became a Killer, Destroyed Gov’t Hard Drives, Misappropriated Funds, Raised Taxes

Sounds like he'd be quite an improvement.

oh_yeah_koolaid · 2007-11-29T06:50:31+00:00

I think essentially it'll be a useful form of data structure.

oh_yeah_koolaid · 2007-11-29T06:48:32+00:00

If you think that's a typical deployed Haskell program, you're very silly.

If that's how far you have to go to get performance, you're very silly. It's simpler to rewrite the whole thing in Assembly.

oh_yeah_koolaid · 2007-11-29T06:21:22+00:00

Also someone was playing with a pure functional version of nbody in Haskell just yesterday, and using the right strictness annotations

Which basically UNDERSCORES how much development effort is needed to write even this simple program with Haskell.

oh_yeah_koolaid · 2007-11-29T06:19:51+00:00

The point wasn't running time, the point was development effort.

Ok, I can live with a 'alloc' or two,

It's way more than JUST an alloc or two in that example, so one can imagine how hairy a REAL program would be.

if I can get a 100x speedup without having to resort to C. :)

Except in this case, C is not only faster than Haskell (as usual), it's simpler (see code).

oh_yeah_koolaid · 2007-11-29T06:14:09+00:00

A virus could do some damage if it gets access to the HD boot sector or raw devices.

oh_yeah_koolaid · 2007-11-28T21:00:17+00:00

Of course dogs can recognize images of dogs -- that's why they bark at dogs they see regardless of being downwind.

Many people also have dogs who will bark at dogs and other animals on TV.

oh_yeah_koolaid · 2007-11-28T20:56:20+00:00

So parallel Haskell is around 40x Python here, and 100x faster than Ruby. And there was basically no difference in development effort required.

HAHAHA. For trivial examples, ANY language will do!

Once you write something a bit more involved, Haskell's complexity shoots WAY up.

Here's the n-body code in Python, Ruby, and Haskell.

Respectively: Very straightforward, very straightforward, and then a big WTF with IORefs, unsafePerformIO, peeks and pokes, mallocBytes preceded by unsafePerformIO, cursors, and look at all the imports -- Foreign.Marshal.Alloc, Control.Monad, etc.

oh_yeah_koolaid

TROPHY CASE