sort segfaults

[HarlanH]

All commits from master applied to my fork (which doesn't touch sort.jl), make clean, make test passes, I get the following. Other arrays work; this one doesn't:

julia> zz =   [0.2,0.2,0.2,0.2,0.2,0.4,0.3,0.2,0.2,0.1,0.2,0.2,0.1,0.1,0.2,0.4,0.4,0.3,0.3,0.3,0.2,0.4,0.2,0.5,0.2,0.2,0.4,0.2,0.2,0.2,0.2,0.4,0.1,0.2,0.2,0.2,0.2,0.1,0.2,0.2,0.3,0.3,0.2,0.6,0.4,0.3,0.2,0.2,0.2,0.2,1.4,1.5,1.5,1.3,1.5,1.3,1.6,1.0,1.3,1.4,1.0,1.5,1.0,1.4,1.3,1.4,1.5,1.0,1.5,1.1,1.8,1.3,1.5,1.2,1.3,1.4,1.4,1.7,1.5,1.0,1.1,1.0,1.2,1.6,1.5,1.6,1.5,1.3,1.3,1.3,1.2,1.4,1.2,1.0,1.3,1.2,1.3,1.3,1.1,1.3,2.5,1.9,2.1,1.8,2.2,2.1,1.7,1.8,1.8,2.5,2.0,1.9,2.1,2.0,2.4,2.3,1.8,2.2,2.3,1.5,2.3,2.0,2.0,1.8,2.1,1.8,1.8,1.8,2.1,1.6,1.9,2.0,2.2,1.5,1.4,2.3,2.4,1.8,1.8,2.1,2.4,2.3,1.9,2.3,2.5,2.3,1.9,2.0,2.3,1.8]
[0.2, 0.2, 0.2, 0.2, 0.2, 0.4, 0.3  ...  2.3, 2.5, 2.3, 1.9, 2.0, 2.3, 1.8]

julia> sort(zz)
Segmentation fault

[6e441f9c]

Linux, 64-bit, libc 2.13.

recent trunk build

Segfault happens, backtrace useless

#0 0x00007fffee3533ef in ?? ()
#1 0x0000000000000000 in ?? ()

[vtjnash]

It appears to be an infinite recursion. quicksort appears to recurse infinitely (or break in one of several other ways) if given a sufficiently large chunk of identical values at any point during the computation (over the threshold for using an insertionsort).

ie, try zz=[.1,.1,.1,.1,.1,.1,.1,.1,.1,.1,.1,.1,.1,.1,.1,.1,.1,.1,.1,.1,.1,.1]

[StefanKarpinski]

@ViralBShah: can you take a look at this? The quicksort code was originally yours. I will also take a look.

[6e441f9c]

Bisecting on Linux / 64-bit / glibc-2.13:

julia> sort([0.1 | x = 1:21])
21-element Float64 Array:
 0.1
 0.1
 0.1
 0.1
 0.1
 0.1
 0.1
 0.1
 0.1
 0.1
 0.1
 0.1
 0.1
 0.1
 0.1
 0.1
 0.1
 0.1
 0.1
 0.1
 0.1

julia> sort([0.1 | x = 1:22])
in _jl_quicksort_fp_pos: arrayref: index out of range
 in _jl_quicksort_fp_pos at sort.jl:77
 in sort! at sort.jl:252
 in anonymous at no file

[6e441f9c]

I think that the root cause are the line

          pivot = (a[lo]+a[hi]+a[(lo+hi)>>>1])/3                    # 1.16x

(sort.jl : 77)

and the fact

julia> (0.1+0.1+0.1)/3>0.1
true

So, while quicksort code relies on the fact that some element of array is no less than pivot, this assumption can be false.

I can understand a few ways to fix it in a straightforward way (for example, taking 4 sample points could help, because there is no rounding off in division by 4) that doesn't hurt basic asimptotical beaviour, but I am not sure what is the best fix to keep constants in complexity small.

[StefanKarpinski]

Interesting. That's an excellent find. I didn't get around to investigating this yet, so that's very much appreciated. We can change the pivot selection for now and convert a segfault into correct behavior with a potential performance problem on some array orderings.

[6e441f9c]

This increases possibility of quadratic-time exploit, I guess

[StefanKarpinski]

Yeah — as noted in my commit message. But I'd rather have a potential performance regression than a segfault.