multicore wish [Was: Re: [Caml-list] Re: OCaml is broken]

[Goswin von Brederlow <goswin-v-b@web.de>]

Jon Harrop <jon@ffconsultancy.com> writes:

> We've discussed the problems with that before. Writing a parallel generic 
> quicksort seems to be a good test of a decent multicore capable language 
> implementation. Currently, F# is a *long* way ahead of everything open 
> source.

How do you implement it?

1) divide at the top and then let each core sort its smaller array

Say you have 2^n cores then the first n splits in merge sort would
first sort the values into the 2 regions and then start a thread for
each region (start a new one, do the other part in this thread). After
n splits you would switch to a uni-core quicksort.

For this you need to split well so each core ends up with a roughly
equal sized chunk.

2) factory/worker approach

Each core runs a factory/worker thread waiting on a job queue. You
start by dumping the full array into the job queue. Some random core
picks it up, splits it into 2 regions and dumps one into the job
queue. If the job gets too small (PAGE_SIZE? cache line size? total
size / cores^2?) the factory/worker switches to normal uni-core
quicksort and sorts the whole chunk.

The job queue should probably be priority based so larger chunks are
sorted before smaller.

Here the quality of each split is not so important. If a chunk is
smaller, and therefore faster, the core just picks up the next job in
the queue. But you need more syncronization between the cores for the
job queue. On the other hand you aren't limited to 2^n cores. Any
number will do.

MfG
        Goswin