c++ - 快速编译高效排序算法(用于JIT编译)

Question

我正在构建一个编译器，它将 C++ 代码生成一个字符数组，该数组由 JIT 编译器 Clang 翻译成 LLVM-IR，然后进一步 JIT 翻译成可执行代码(然后执行)。

我正在处理大量数据，有一次我需要对一个自定义 数据类型的数组进行排序。数据类型由我的编译器动态构建，并且每个 JIT 编译都不同。通常，元素按字典顺序与其中的一些数字进行比较，但是，在极少数情况下，比较可能会更加复杂(遵循一些指针和奇特的字符串比较)。

现在我的问题是:什么是高效的排序算法，它可以通过 llvm 非常快 的 JIT 编译，同时在执行时非常快？是否存在可以快速编译并同时快速运行的算法？

我的第一个想法是 JIT 比较函数并将其作为指针提供给 qsort()(我可以链接到 LLVM 中的外部编译函数)。然而，qsort 在执行时的效率低得惊人。由于其模板和 STL-blubbla-sugar，使用 std::sort 的替代方案在编译期间效率低得惊人。

我为执行以下结构做了一些性能测试:

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

1MB 数据运行时间:

• std::sort:5 毫秒
• qsort:14 毫秒
• 自写:6 毫秒

1GB 数据运行时间:

• std::sort: 8.9 秒
• qsort: 24 秒
• 自写: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 方式使用它:

• 算法本身是预编译的
• 比较函数是 JIT 并动态传递的

我认为它仍然优于 qsort，因为该算法会有意义地操纵内存并且只会调用比较(真的)。