1

我正在构建一个编译器，它将 c++ 代码生成为一个字符数组，该数组由 JIT 编译器 Clang 转换为 LLVM-IR，然后进一步 JIT 转换为可执行代码（然后执行）。

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

现在我的问题是：什么是一种有效的排序算法，它可以由 llvm非常快地编译，同时在执行时非常快？是否有可以快速编译并同时快速运行的算法？

我的第一个想法是对比较函数进行 JIT 处理并将其作为指针提供给 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毫秒

1GB 数据运行时间：

  • 标准：：排序：8.9 秒
  • qsort：24 秒
  • 自写：10.1 s

不幸的是，我现在没有 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--;
}}}
4

1 回答 1

2

我会首先尝试将函数指针传递给std::sort，然后以下列qsort方式使用它：

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

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

于 2012-05-14T18:46:19.760 回答