Here's a (primitive) quicksort implementation I just wrote from
scratch; on my machine every run was below 30s for a 1GB array:
https://gist.github.com/Sh4rK/ebd5b7a39be70185500e
The elemtype parameter needs to be a ctype of the element type; and
key needs to be a one param function that maps an array element to
what you want to sort by (in this case the linear combination of the
fields). The INSERTION_THRESHOLD constant is kind of arbitrary, so you
can try different values and see whether it changes anything.
2015-07-21 7:56 GMT+02:00 demetri <demetri.spanos@xxxxxxxxx>:
I tried porting the relatively simple qsort from the Apple/Darwin
standard C library source so that I could avoid qsorting with a
Lua callback on every comparison.
I'm not sure if I'm doing something wrong but it's about a factor
of 100 slower. Based on -jv output it seems that the problem is
an explosion of traces (several hundred) depending on how the
various comparisons within the tight loop evaluate. I'm not
getting any NYIs or other obviously fixable problems -- as far as
I can tell it's pure compiled code and just ends up being way
slower due to the trace compiler emitting a new trace every
second or so. But I'm out of my depth on what might be causing
the JIT to be slow so perhaps I'm mistaken; advice here would
be appreciated :)
So I was wondering if anyone might have a good implementation
they would be willing to share? For my purposes I just care about
sorting an array of structs of the form
struct {int32_t a,b,c,d,e,f,g,h;}
I need to be able to sort by linear combinations of the member fields,
and have decent performance even on large (say 1GB) arrays. Doing
so with the qsort from Apple/Darwin I get about 30s for a 1GB array
on a 2013 i7, and over 100x that using my brain-dead port to LuaJIT/FFI
code.
I have a workaround solution by manually implementing a comparator
for every linear combination I care about in C and compiling that into my
analysis binary. But I'd really prefer to be able to use a pure Lua
function.
I'd also be willing to accept a mergesort or other non-in-place sort
in a pinch :)
Any help would be appreciated! Or if it seems like my 100x factor is
due to my own stupidity somehow, I'm open to that possibility as well.
In fact, I would greatly prefer to discover I've been stupid :)
Thanks,
Demetri
