> vs.> =导致显着的性能差异
我只是偶然发现了一些事情。 起初我以为这可能是一个分支预测错误的例子 ，但是我无法解释为什么分支错误预测会导致这种现象。 我实现了两个版本的Bubble Sort Java，并进行了一些性能testing：
import java.util.Random; public class BubbleSortAnnomaly { public static void main(String... args) { final int ARRAY_SIZE = Integer.parseInt(args[0]); final int LIMIT = Integer.parseInt(args[1]); final int RUNS = Integer.parseInt(args[2]); int[] a = new int[ARRAY_SIZE]; int[] b = new int[ARRAY_SIZE]; Random r = new Random(); for (int run = 0; RUNS > run; ++run) { for (int i = 0; i < ARRAY_SIZE; i++) { a[i] = r.nextInt(LIMIT); b[i] = a[i]; } System.out.print("Sorting with sortA: "); long start = System.nanoTime(); int swaps = bubbleSortA(a); System.out.println( (System.nanoTime() - start) + " ns. " + "It used " + swaps + " swaps."); System.out.print("Sorting with sortB: "); start = System.nanoTime(); swaps = bubbleSortB(b); System.out.println( (System.nanoTime() - start) + " ns. " + "It used " + swaps + " swaps."); } } public static int bubbleSortA(int[] a) { int counter = 0; for (int i = a.length - 1; i >= 0; --i) { for (int j = 0; j < i; ++j) { if (a[j] > a[j + 1]) { swap(a, j, j + 1); ++counter; } } } return (counter); } public static int bubbleSortB(int[] a) { int counter = 0; for (int i = a.length - 1; i >= 0; --i) { for (int j = 0; j < i; ++j) { if (a[j] >= a[j + 1]) { swap(a, j, j + 1); ++counter; } } } return (counter); } private static void swap(int[] a, int j, int i) { int h = a[i]; a[i] = a[j]; a[j] = h; } } 如您所见，这两种sorting方法之间的唯一区别是> vs. >= 。 当用java BubbleSortAnnomaly 50000 10 10运行程序时，你显然会期望sortB比sortA慢。 但是我在三台不同的机器上得到了以下（或类似的）输出：
Sorting with sortA: 4.214 seconds. It used 564960211 swaps. Sorting with sortB: 2.278 seconds. It used 1249750569 swaps. Sorting with sortA: 4.199 seconds. It used 563355818 swaps. Sorting with sortB: 2.254 seconds. It used 1249750348 swaps. Sorting with sortA: 4.189 seconds. It used 560825110 swaps. Sorting with sortB: 2.264 seconds. It used 1249749572 swaps. Sorting with sortA: 4.17 seconds. It used 561924561 swaps. Sorting with sortB: 2.256 seconds. It used 1249749766 swaps. Sorting with sortA: 4.198 seconds. It used 562613693 swaps. Sorting with sortB: 2.266 seconds. It used 1249749880 swaps. Sorting with sortA: 4.19 seconds. It used 561658723 swaps. Sorting with sortB: 2.281 seconds. It used 1249751070 swaps. Sorting with sortA: 4.193 seconds. It used 564986461 swaps. Sorting with sortB: 2.266 seconds. It used 1249749681 swaps. Sorting with sortA: 4.203 seconds. It used 562526980 swaps. Sorting with sortB: 2.27 seconds. It used 1249749609 swaps. Sorting with sortA: 4.176 seconds. It used 561070571 swaps. Sorting with sortB: 2.241 seconds. It used 1249749831 swaps. Sorting with sortA: 4.191 seconds. It used 559883210 swaps. Sorting with sortB: 2.257 seconds. It used 1249749371 swaps.
当您将LIMIT参数设置为例如50000 （ java BubbleSortAnnomaly 50000 50000 10 ）时，您会得到预期的结果：
Sorting with sortA: 3982697438 ns. It used 625941897 swaps. Sorting with sortB: 4657909823 ns. It used 789391382 swaps.
我把程序移植到C ++来确定这个问题是否是Java特有的。 这是C ++代码。
#include <cstdlib> #include <iostream> #include <omp.h> #ifndef ARRAY_SIZE #define ARRAY_SIZE 50000 #endif #ifndef LIMIT #define LIMIT 10 #endif #ifndef RUNS #define RUNS 10 #endif void swap(int * a, int i, int j) { int h = a[i]; a[i] = a[j]; a[j] = h; } int bubbleSortA(int * a) { const int LAST = ARRAY_SIZE - 1; int counter = 0; for (int i = LAST; i > 0; --i) { for (int j = 0; j < i; ++j) { int next = j + 1; if (a[j] > a[next]) { swap(a, j, next); ++counter; } } } return (counter); } int bubbleSortB(int * a) { const int LAST = ARRAY_SIZE - 1; int counter = 0; for (int i = LAST; i > 0; --i) { for (int j = 0; j < i; ++j) { int next = j + 1; if (a[j] >= a[next]) { swap(a, j, next); ++counter; } } } return (counter); } int main() { int * a = (int *) malloc(ARRAY_SIZE * sizeof(int)); int * b = (int *) malloc(ARRAY_SIZE * sizeof(int)); for (int run = 0; RUNS > run; ++run) { for (int idx = 0; idx < ARRAY_SIZE; ++idx) { a[idx] = std::rand() % LIMIT; b[idx] = a[idx]; } std::cout << "Sorting with sortA: "; double start = omp_get_wtime(); int swaps = bubbleSortA(a); std::cout << (omp_get_wtime() - start) << " seconds. It used " << swaps << " swaps." << std::endl; std::cout << "Sorting with sortB: "; start = omp_get_wtime(); swaps = bubbleSortB(b); std::cout << (omp_get_wtime() - start) << " seconds. It used " << swaps << " swaps." << std::endl; } free(a); free(b); return (0); }
这个程序显示了相同的行为。 有人能解释一下，究竟发生了什么？
先执行sortB然后sortA不会改变结果。
我想这可能确实是由于分支预测。 如果您计算交换的次数与内部sorting迭代次数的比较，您会发现：
限制= 10
- A = 560M掉期/ 1250M循环
- B = 1250M掉期/ 1250M循环（掉期比循环减less0.02％）
限制= 50000
- A = 627M掉期/ 1250M循环
- B = 850M掉期/ 1250M循环
所以在Limit == 10情况下，交换在Bsorting中执行99.98％的时间，这对于分支预测器是明显有利的。 在Limit == 50000情况下，交换只是随机命中68％，所以分支预测器不太有利。
我认为这可以通过分支机构的错误预测来解释。
例如，考虑LIMIT = 11和sortB 。 在外层循环的第一次迭代中，它很快就会碰到等于10的元素之一。所以它将有a[j]=10 ，因此肯定a[j]将是>=a[next] ，因为那里没有大于10的元素。因此，它将执行交换，然后在j只执行一步，再次发现a[j]=10 （相同的交换值）。 所以再一次，它将是a[j]>=a[next] ，所以一个。 每一个比较，除了几个开始将是真实的。 同样，它将在外循环的下一次迭代中运行。
sortA不一样。 它会以大致相同的方式开始，偶然发现a[j]=10 ，做一些类似的交换，但是也只是在发现a[next]=10 。 那么条件将是错误的，不会做交换。 如此等等：每当它在a[next]=10上绊倒，条件是错误的并且不交换。 因此，这个条件在11个（从0到9的a[next]值）中是10次，在11个中是1个是假的。没有什么奇怪的分支预测失败。
使用提供的C ++代码（删除了时间计数）和perf stat命令，我得到了确认brach-miss理论的结果。
当Limit = 10 ，BubbleSortB从分支预测（0.01％未命中）中受益很大，但Limit = 50000分支预测的失败甚至比BubbleSortA（失败率分别为12.69％和12.76％）还要多15.65％。
BubbleSortA限制= 10：
Performance counter stats for './bubbleA.out': 46670.947364 task-clock # 0.998 CPUs utilized 73 context-switches # 0.000 M/sec 28 CPU-migrations # 0.000 M/sec 379 page-faults # 0.000 M/sec 117,298,787,242 cycles # 2.513 GHz 117,471,719,598 instructions # 1.00 insns per cycle 25,104,504,912 branches # 537.904 M/sec 3,185,376,029 branch-misses # 12.69% of all branches 46.779031563 seconds time elapsed
BubbleSortA限制= 50000：
Performance counter stats for './bubbleA.out': 46023.785539 task-clock # 0.998 CPUs utilized 59 context-switches # 0.000 M/sec 8 CPU-migrations # 0.000 M/sec 379 page-faults # 0.000 M/sec 118,261,821,200 cycles # 2.570 GHz 119,230,362,230 instructions # 1.01 insns per cycle 25,089,204,844 branches # 545.136 M/sec 3,200,514,556 branch-misses # 12.76% of all branches 46.126274884 seconds time elapsed
BubbleSortB限制= 10：
Performance counter stats for './bubbleB.out': 26091.323705 task-clock # 0.998 CPUs utilized 28 context-switches # 0.000 M/sec 2 CPU-migrations # 0.000 M/sec 379 page-faults # 0.000 M/sec 64,822,368,062 cycles # 2.484 GHz 137,780,774,165 instructions # 2.13 insns per cycle 25,052,329,633 branches # 960.179 M/sec 3,019,138 branch-misses # 0.01% of all branches 26.149447493 seconds time elapsed
BubbleSortB限制= 50000：
Performance counter stats for './bubbleB.out': 51644.210268 task-clock # 0.983 CPUs utilized 2,138 context-switches # 0.000 M/sec 69 CPU-migrations # 0.000 M/sec 378 page-faults # 0.000 M/sec 144,600,738,759 cycles # 2.800 GHz 124,273,104,207 instructions # 0.86 insns per cycle 25,104,320,436 branches # 486.101 M/sec 3,929,572,460 branch-misses # 15.65% of all branches 52.511233236 seconds time elapsed
编辑2：这个答案在大多数情况下可能是错误的，当我说上面的所有内容都是正确的时候，这个答案仍然是正确的，但是对于大多数处理器体系结构来说，下面的部分是不正确的。 然而，我会说在某些OS / Architecture上有一些JVM在理论上可能会这样做，但是JVM可能执行的很差，或者是一个奇怪的架构。 而且，这在理论上是可能的，因为大多数可以想象的事情在理论上是可能的，所以我会拿最后一部分的盐。
首先，我不确定C ++，但是我可以谈论一些Java。
这里是一些代码，
public class Example { public static boolean less(final int a, final int b) { return a < b; } public static boolean lessOrEqual(final int a, final int b) { return a <= b; } }
运行javap -c我得到字节码
public class Example { public Example(); Code: 0: aload_0 1: invokespecial #8 // Method java/lang/Object."<init>":()V 4: return public static boolean less(int, int); Code: 0: iload_0 1: iload_1 2: if_icmpge 7 5: iconst_1 6: ireturn 7: iconst_0 8: ireturn public static boolean lessOrEqual(int, int); Code: 0: iload_0 1: iload_1 2: if_icmpgt 7 5: iconst_1 6: ireturn 7: iconst_0 8: ireturn }
你会注意到唯一的区别是if_icmpge （如果比较大/相等）与if_icmpgt （如果比较大）。
以上所有内容都是事实，剩下的就是我最好的猜测，就是if_icmpge和if_icmpgt是如何在大学课程的基础上处理的。 为了得到更好的答案，你应该看看你的JVM如何处理这些。 我的猜测是，C ++也编译到类似的操作。
编辑：关于
if_i<cond>文档在这里
计算机比较数字的方法是从另一个中减去一个，并检查数字是否为0，所以当执行a < b如果从b减去b ，并通过检查值的符号来查看结果是否小于0 b - a < 0 ）。 要做a <= b虽然它必须做一个额外的步骤，并减去1（ b - a - 1 < 0 ）。
通常这是一个非常小的差异，但这不是任何代码，这是吓人的泡沫sorting！ O（n ^ 2）是我们正在做这个特定比较的平均次数，因为它在最内圈。
是的，这可能与分支预测有关，我不确定，我不是这方面的专家，但我认为这也可能起到非微不足道的作用。
