我有两个类似的实现(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 个随机整数)上测试它们。 起初的结果是 java: ~17 sec (使用 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-probabilities 一起使用并重新编译代码。 在 ~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 慢。

最佳答案

And this is what I really want to ask.

How is it possible for my program to run so fast if it has to write files and collect profiling information and instead it runs 1.5 times slower when it hasn't?

是的，这才是真正的问题。提及所有 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

第一种情况(快速)可以从branch prediction中受益匪浅但另一个(缓慢的情况)显然不能。排序或随机排列的数组不会导致太多 branch mispredictions .在这种情况下，第一个代码片段是最佳的。

事实证明，实际上很难创建一个在选择排序中导致大量分支预测错误的数据集。 (由 Yakk 指出；另见 my attempts 创建一个邪恶的数据集；到目前为止，我没有创建一个。)

-fprofile-arcs 碰巧禁用了树向量化，这似乎负责生成慢速案例代码。禁用树向量化的更好方法是传递 -fno-tree-vectorize 标志。

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

关于java - C 性能和编译选项，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21050130/