C性能和编译选项

Question

我有两个类似的实现(java和c ++)用于像选择排序这样的简单算法.

public interface SortingAlgorithm {

    public void sort(int[] a);
}

public class SelectionSort implements SortingAlgorithm {

    @Override
    public void sort(int[] a) {
        for (int i = 0; i < a.length; i++) {
            int lowerElementIndex = i;
            for (int j = i + 1; j < a.length; j++) {
                if (a[j] < a[lowerElementIndex]) {
                    lowerElementIndex = j;
                }
            }
            swap(a, lowerElementIndex, i);
        }
    }

    private void swap(int[] a, int i, int j) {
        if (i == j) {
            return;
        }
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

和c一:

inline void swap(int* a, int i, int j);

void s_sort(int* a, int size) {
  int i;
  for (i = 0; i < size; i++) {
    int lowerElementIndex = i, j;
    for (j = i + 1; j < size; j++) {
      if (a[j] < a[lowerElementIndex]) {
    lowerElementIndex = j;
      }
    }
    swap(a, lowerElementIndex, i);
  }
}

inline void swap(int* a, int i, int j) {
  if (i == j) {
    return;
  }
  int temp = a[i];
  a[i] = a[j];
  a[j] = temp;
}

现在,我尝试在大型阵列上测试它们(100000随机int).结果首先是java:~17秒(用oracle jdk/jvm编译和执行)c:~22秒(用gcc v4.8编译,没有任何优化)

当然,我然后尝试通过cflags优化我的c版本.结果是(我只报告cflags): - O1:~18.4

-O2:~18.4

-O {3-9}:~20.9

现在,我的第一个问题是我应该使用哪些cflacs进行编译？

所以我阅读了关于优化的gnu手册.添加-march = native没有帮助.经过一段时间尝试其他选项后,我进入了-fprofile-arcs选项.将它添加到我的标志使我的代码在大约11秒内完成测试!但是有些文件出现在我的文件夹中:分析的结果.据我所知,我应该将它们与-fbranch-probability一起使用并重新编译代码.在~18.5秒内再次重新编译结果.这就是我真正想问的问题.

如果我的程序必须编写文件并收集分析信息,那么我的程序如何运行得如此之快呢？如果它不运行,它的运行速度会慢1.5倍？

我忘了提到我在安装了Intel Celeron @ 2.8GHz处理器和linux(带有xfce的fedora 20)的旧PC上.如果您需要有关硬件的其他信息,请询问!;)

编辑:我用于测试的代码是:

Java的:

public class Test {

    public static void main(String[] args) {
        int[] a = new int[100000];
        int[] a2 = new int[100000];
        for (int i = 0; i < a.length; i++) {
            a[i] = (int)(Math.random()*100000);
            a2[i] = a[i];
        }
        SelectionSort s = new SelectionSort();
        InsertionSort s1 = new InsertionSort();
        double start = System.nanoTime();
        s.sort(a);
        double end = System.nanoTime();
        double time = (end-start)/1000000000.0; 
        System.out.println("Selection: "+time);
        start = System.nanoTime();
        s1.sort(a2);
        end = System.nanoTime();
        time = (end-start)/1000000000.0;
        System.out.println("Insertion: "+time);
    }
}

而c:

#include "insertion_sort.h"
#include "selection_sort.h"
#include <time.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int main() {
  int max = 100000, i;
  srand(time(NULL));

  int array[100000], array2[100000];
  for(i=0; i<100000; i+=1) {
    array[i] = rand()%100000;
  }

  memcpy(array2, &array[0], 100000 * sizeof(int));

  clock_t inizio = clock();
  s_sort(array, max);
  clock_t fine = clock();
  float tempoEsecuzione = (float)(fine - inizio) / CLOCKS_PER_SEC;
  printf("Selection: %2.3f\n", tempoEsecuzione);

  inizio = clock();
  i_sort(array2, max);
  fine = clock();
  tempoEsecuzione = (float)(fine - inizio) / CLOCKS_PER_SEC;
  printf("Insertion: %2.3f\n", tempoEsecuzione);
  return 0;
}

代码包含对插入排序函数的引用,我没有将其包含在问题的其余部分中,因为(正如预期的那样)java运行速度慢于c.

Answer 1

这才是我真正想问的。

如果我的程序必须写入文件并收集分析信息，那么它怎么可能运行得这么快，而在不需要写入文件和收集分析信息时，它的运行速度会慢 1.5 倍？

是的，这才是真正的问题。提及所有 Java 比较的内容只会增加噪音。

我可以使用 gcc 4.7.2 在我的机器上重现奇怪的行为。毫不奇怪，代码的热路径是内部 for 循环：

for (j = i + 1; j < size; j++) {
  if (a[j] < a[lowerElementIndex]) {
    lowerElementIndex = j;
}

相应生成的汇编代码中唯一相关的区别是：

快速案例：

    cmpl    %esi, %ecx
    jge .L3
    movl    %ecx, %esi
    movslq  %edx, %rdi
.L3:

慢的情况：

cmpl    %ecx, %esi
cmovl   %edx, %edi
cmovl   %esi, %ecx

第一种情况（快速）可以从分支预测中受益匪浅，但另一种情况（慢速情况）显然不能。排序或随机打乱的数组不会导致太多的分支错误预测。在这种情况下，第一个代码片段是最佳的。

事实证明，创建一个在选择排序中导致大量分支预测错误的数据集实际上很困难。（ Yakk指出了这一点；另请参阅我创建邪恶数据集的尝试；到目前为止，我未能创建一个。）

这-fprofile-arcs恰好禁用了树向量化，这似乎是生成缓慢案例代码的原因。禁用树向量化的更好方法是传递标志-fno-tree-vectorize。

clang 3.4 还生成快速案例代码，没有任何特殊标志。没有预热的Java 代码的运行速度比 C 代码慢 2.4 倍。（因为这不是问题，所以我没有考虑提高 Java 代码性能。）