[concurrency-interest] Strange behaviour when sorting an uniform array

Doug Lea dl at cs.oswego.edu
Tue May 25 16:38:18 EDT 2010


On 05/25/10 03:07, Lukas Krecan wrote:
> Hi,
>     I have been playing with extra166y library and found that when I try
> to sort an uniform array (full of ones) it takes ages.

Thanks for reporting this! As correctly guessed by Kasper, this
was due to a degenerate O(n^2) case in the sequential leaf sort.
Sorry for the problems. I changed a few things to allow
replacement for long and double versions with calls to  Arrays.sort
which as of jdk7 includes much faster base sorts that also
avoid this degeneracy. So if you run these with openjdk7
snapshots, the parallel sorts will also be faster. Also,
the other variants of sort (with comparators and for objects)
are changed to also screen for runs of identical values.

Get replacements at the usual places:

# API specs:  http://gee.cs.oswego.edu/dl/jsr166/dist/extra166ydocs/
# jar file: http://gee.cs.oswego.edu/dl/jsr166/dist/extra166y.jar (compiled 
using Java6 javac).
# Browsable CVS sources: 
http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/extra166y/









More information about the Concurrency-interest mailing list