> vs. >= in bubble sort causes significant performance difference
I just stumbled upon something. At first I thought it might be a case of branch misprediction like it is in this case, but I cannot explain why branch misprediction should cause this behaviour.
I implemented two versions of Bubble Sort in Java and did some performance 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;
}
}
As we can see, the only difference between those two sorting methods is the > vs. >=. When running the program with java BubbleSortAnnomaly 50000 10 10, one would obviously expect that sortB is slower than sortA because it has to execute more swap(...)s. But I got the following (or similar) output on three different machines:
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.
When I set the parameter for LIMIT to, e.g., 50000 (java BubbleSortAnnomaly 50000 50000 10), I get the expected results:
Sorting with sortA: 3.983 seconds. It used 625941897 swaps.
Sorting with sortB: 4.658 seconds. It used 789391382 swaps.
I ported the program to C++ to determine whether this problem is Java-specific. Here is the C++ code.
#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; 0 < i; --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; 0 < i; --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; ARRAY_SIZE > idx; ++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);
}
This program shows the same behaviour. Can someone explain what exactly is going on here?
Executing sortB first and then sortA does not change the results.
最佳答案