Быстро компилировать эффективный алгоритм сортировки (для компиляции JIT)

Question

Я создаю компилятор, который создает код C++ в массив символов, который переводится JIT-компилятором Clang в LLVM-IR, а затем далее JIT-перевод на исполняемый код (который чем выполняется).

Я обрабатываю большие объемы данных, и в какой-то момент мне нужно отсортировать массив пользовательских типов данных. Тип данных динамически создается моим компилятором и отличается для каждой компиляции JIT. Обычно элементы лексикографически сравниваются с некоторыми числами в нем, однако сравнение может быть более сложным в редких случаях (следуя некоторым указателям и причудливым строкам).

Теперь мой вопрос: Что такое эффективный алгоритм сортировки, который может с помощью JIT, составленный LLVM очень быстро и на то же время очень быстро при исполнении? Существуют ли где-то алгоритмы, по которым можно быстро компилировать и быстро запускать?

Моя первая идея состояла в том, чтобы просто выполнить функцию сравнения и передать ее qsort() в качестве указателя (я могу ссылаться на внешние скомпилированные функции в LLVM). Тем не менее, qsort потрясающе неэффективен во время выполнения. Альтернатива, используя std :: sort, является потрясающе неэффективной во время компиляции из-за ее шаблонов и stl-blubbla-sugar.

Я сделал некоторые тест производительности для исполнения на следующий структуры:

struct MyStruct { 
int x; 
long z; 
bool operator<(const struct MyStruct& other) const { return (x < other.x) || (x==other.x&&z<other.z); } 
} 

1MB среды выполнения данных:

• станд :: сортировать: 5 мс
• QSort: 14 мс
• самописью: 6 мс

1 ГБ автономной работы данных:

• станд :: сортировать: 8,9 s
• QSort: 24 s
• самоуправления написано: 10,1 с

К сожалению, я не JIT компиляции раз прямо сейчас, но опубликует их в будущем.

В настоящее время кажется, что мой собственный письменный вид лучше, чем qsort или std :: sort, но я бы предпочел использовать некоторую реализацию библиотеки.

Есть ли у вас предложения по существующим реализациям сортировки, которые бы быстро выполнялись и для компиляции? Возможно ли какие-либо другие возможности ускорить компиляцию при быстрой сортировке (только компилировать функцию сравнения или что-то в этом роде)?

Кстати, вот мой самостоятельно написал (украдено из http://alienryderflex.com/quicksort/) своего рода рутина (для JITing, я бы не стал использовать тип шаблона, но заменяя его непосредственно с пользовательского типа, в том числе «< =»):

template< typename Type > 
void self_written_sort(Type *arr, int elements) { 
    #define MAX_LEVELS 64 
    Type piv; 
    int beg[MAX_LEVELS], end[MAX_LEVELS], i=0, L, R, swap ; 
    beg[0]=0; end[0]=elements; 
    while (i>=0) { 
    L=beg[i]; R=end[i]-1; 
    if (L<R) { 
     piv=arr[L]; 
     while (L<R) { 
     while (arr[R]>=piv && L<R) R--; if (L<R) arr[L++]=arr[R]; 
     while (piv<=arr[L] && L<R) L++; if (L<R) arr[R--]=arr[L]; } 
     arr[L]=piv; beg[i+1]=L+1; end[i+1]=end[i]; end[i++]=L; 
     if (end[i]-beg[i]>end[i-1]-beg[i-1]) { 
     swap=beg[i]; beg[i]=beg[i-1]; beg[i-1]=swap; 
     swap=end[i]; end[i]=end[i-1]; end[i-1]=swap; }} 
    else { 
     i--; 
}}} 

Answer 1

Я бы сначала попытаться передать указатель на функцию std::sort, и, таким образом, использовать его в qsort образом:

• сам алгоритм предкомпилированного
• функция сравнения JITed и передается динамически

Я думаю, что он все равно будет выше qsort, потому что алгоритм будет манипулировать память осмысленно и только сравнение можно было бы назвать (на самом деле).