[PRL] Interesting multi-core results...

[Bryan Chadwick]

I though maybe some of you would be interested in hearing about a simple test 
comparing functional Lists to Arrays on a multi-core system.

Attached is a quick implementation of functional lists in Java, and a little 
test/timing framework for merge sort.  I sort the functional lists both 
sequentially, and with two threads.  The Array is sorted using 
java.util.Arrays.sort(...), which "offers guaranteed n*log(n) performance" 
(quote from Sun's JavaDoc).

Here's a typical run on my machine (Laptop, Intel Pentium-4/M)

   % java -Xss3M MergeSort 30000
    Length = 30000
     Sort:  MSec: 186
    PSort:  MSec: 263
    ASort:  MSec: 31

Notice how fast the Array sort is!  Obviously the parallel version is slower 
since I only have one processor... but the functional sort is reasonable, at 
least on my older machine.

Here's a typical run on the CCIS machine "pacman" (Intel Core2 Duo):

   % java -Xss3M MergeSort 30000
    Length = 30000
     Sort:  MSec: 76
    PSort:  MSec: 23
    ASort:  MSec: 113

Ok... so what just happened!?  Well, alas, my machine is much slower than 
pacman, but other than that, the parallel version does *very* well, probably too 
well in fact.  Because one of the sorts has to go first, the second one seems to 
get a nicely filled cache.  This can be minimized by sorting the list once ("off 
the record") before running the tests.

More importantly, the Array sort is atrocious, running (consistently) almost 
four times slower than on my machine.  I'm assuming this has to do with cache 
invalidations (at various levels) and implicit synchronization between cores, 
but someone else might have a better idea.

Thanks,
Bryan.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: MergeSort.java
Type: text/x-java
Size: 6845 bytes
Desc: not available
Url : https://lists.ccs.neu.edu/pipermail/prl/attachments/20080922/3c164224/attachment.bin