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
