> vs. >= вызывает значительную разницу в производительности
Я только что наткнулся на что-то. Сначала я подумал, что это может быть случай неправильного предсказания ветки, как будто это в этом случае, но я не могу объяснить, почему неправильное предсказание отрасли должно вызвать это явление. Я реализовал две версии Bubble Sort в Java и выполнил некоторые тесты производительности:
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;
}
}
Как вы можете видеть, единственная разница между этими двумя методами сортировки - это > 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: 3.983 seconds. It used 625941897 swaps.
Sorting with sortB: 4.658 seconds. It used 789391382 swaps.
Я портировал программу на С++, чтобы определить, является ли эта проблема специфичной для Java. Вот код С++.
#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 не изменит результаты.
Ответы
Ответ 1
Я думаю, что это может быть связано с предсказанием ветвей. Если вы подсчитаете количество свопов по сравнению с количеством итераций внутренней сортировки, которые вы найдете:
Предел = 10
- A = 560M свопов /1250M циклов
- B = 1250M свопов /1250M циклов (на 0,02% меньше свопов, чем циклов)
Предел = 50000
- A = 627M свопов /1250M циклов
- B = 850M свопов /1250M циклов
Таким образом, в случае Limit == 10 обмен выполняется 99,98% времени в B-типе, что, очевидно, выгодно для предсказателя ветвления. В случае Limit == 50000 обмен производится только случайным образом на 68%, поэтому предсказатель ветвления менее выгоден.
Ответ 2
Я думаю, что это действительно может быть объяснено неверным предсказанием отрасли.
Рассмотрим, например, 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, условие ложно и никаких свопов не выполняется. Следовательно, это условие истинно в 10 раз из 11 (значения a[next] от 0 до 9) и false в 1 случае из 11. Ничего странного, что предсказание ветвления терпит неудачу.
Ответ 3
Используя предоставленный код С++ (отсчет времени удален) с помощью команды perf stat, я получил результаты, подтверждающие теорию brach-miss.
С Limit = 10 BubbleSortB очень выигрывает от предсказания ветвления (0,01% промахов), но с прогнозом отклонения Limit = 50000 не удается еще больше (с пропущенными 15.65%), чем в BubbleSortA (соответственно 12.69% и 12.76%).
BubbleSortA Limit = 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 Limit = 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 Limit = 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 Limit = 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
Ответ 4
Изменить 2: Этот ответ, вероятно, неверен в большинстве случаев, ниже, когда я говорю, что все вышеописанное верно, по-прежнему верно, но нижняя часть неверна для большинства архитектур процессоров, см. комментарии. Однако я скажу, что теоретически возможно наличие какой-то JVM для некоторых OS/Architecture, которые делают это, но JVM, вероятно, плохо реализована или это странная архитектура. Кроме того, это теоретически возможно в том смысле, что большинство мыслимых вещей теоретически возможны, поэтому я бы взял последнюю порцию с солью.
Во-первых, я не уверен в С++, но я могу поговорить о 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 справляются с этим. Я предполагаю, что С++ также сводится к аналогичной операции.
Изменить: документация на if_i<cond> здесь
То, как компьютеры сравнивают числа, вычитает один из другого и проверяет, является ли это число 0 или нет, поэтому при выполнении a < b, если вычитает b из a и видит, если результат меньше 0, знак значения (b - a < 0). Сделать a <= b, хотя он должен сделать дополнительный шаг и вычесть 1 (b - a - 1 < 0).
Обычно это очень незначительная разница, но это не какой-то код, это путаница! O (n ^ 2) - среднее число раз, когда мы делаем это конкретное сравнение, потому что оно во внутреннем большинстве циклов.
Да, это может иметь какое-то отношение к предсказанию ветки. Я не уверен, я не эксперт в этом, но я думаю, что это также может сыграть несущественную роль.
