> 대> = 버블 정렬로 인해 상당한 성능 차이 발생
방금 뭔가 우연히 발견했습니다. 처음에는 이 경우 처럼 분기 오 예측일지도 모른다고 생각 했지만 분기 오 예측이 왜 이런 현상을 일으키는 지 설명 할 수 없습니다.
Java에서 두 가지 버전의 Bubble Sort를 구현하고 몇 가지 성능 테스트를 수행했습니다.
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;
}
}
보시다시피이 두 정렬 방법의 유일한 차이점은 >대 >=. 를 사용하여 프로그램 을 실행할 때 더 많은 s 를 실행해야하기 때문에 속도가 느리다고 java BubbleSortAnnomaly 50000 10 10예상 할 수 있습니다 . 그러나 세 개의 다른 컴퓨터에서 다음과 같은 (또는 유사한) 출력을 얻었습니다.sortBsortAswap(...)
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와 관련된 것인지 확인하기 위해 프로그램을 C ++로 이식했습니다. 다음은 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; 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);
}
이 프로그램은 동일한 동작을 보여줍니다. 누군가 여기서 정확히 무슨 일이 일어나고 있는지 설명 할 수 있습니까?
sortB먼저 실행 한 다음 sortA결과를 변경하지 않습니다.
실제로 분기 예측 때문이라고 생각합니다. 내부 정렬 반복 수와 비교하여 스왑 수를 계산하면 다음을 찾습니다.
제한 = 10
- A = 560M 스왑 / 1250M 루프
- B = 1250M 스왑 / 1250M 루프 (루프보다 0.02 % 적은 스왑)
한도 = 50000
- A = 627M 스왑 / 1250M 루프
- B = 850M 스왑 / 1250M 루프
따라서 Limit == 10스왑이 B 정렬에서 99.98 %의 시간 동안 수행 되는 경우에는 분기 예측 자에게 분명히 유리합니다. Limit == 50000스왑이 무작위로 68 % 만 발생 하는 경우 분기 예측자가 덜 유익합니다.
나는 이것이 실제로 분기 예측 오류로 설명 될 수 있다고 생각합니다.
예를 들어 LIMIT = 11 및을 고려하십시오 sortB. 외부 루프의 첫 번째 반복에서 10과 같은 요소 중 하나를 매우 빠르게 발견 할 것입니다 . 따라서 10보다 큰 요소가 없기 a[j]=10때문에, 따라서 확실히 a[j]될 >=a[next]것입니다. 따라서 스왑을 수행합니다. , 그런 다음 한 단계 j만 수행하여 a[j]=10다시 한 번 찾습니다 (스왑 된 동일한 값). 그래서 다시 한번 그것은 a[j]>=a[next], 그래서 하나 가 될 것입니다. 처음에 몇 가지를 제외한 모든 비교는 사실입니다. 마찬가지로 외부 루프의 다음 반복에서 실행됩니다.
에 대해 동일하지 않습니다 sortA. 그것은 대략 같은 방식으로 시작하고, 우연히 발견 a[j]=10되고, 비슷한 방식으로 약간의 스왑을 수행하지만, 발견되는 지점까지만 수행됩니다 a[next]=10. 그러면 조건이 거짓이되고 스왑이 수행되지 않습니다. 등 : a[next]=10오류가 발생할 때마다 조건이 거짓이며 스왑이 수행되지 않습니다. 따라서이 조건은 11 개 중 10 번 ( a[next]0 ~ 9의 값) 참이고 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
Edit 2: This answer is probably wrong in most cases, lower when I say everything above is correct is still true, but the lower portion is not true for most processor architectures, see the comments. However, I will say that it's still theoretically possible there is some JVM on some OS/Architecture that does this, but that JVM is probably poorly implemented or it's a weird architecture. Also, this is theoretically possible in the sense that most conceivable things are theoretically possible, so I'd take the last portion with a grain of salt.
First, I am not sure about the C++, but I can talk some about the Java.
Here is some code,
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;
}
}
Running javap -c on it I get the bytecode
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
}
You'll notice the only difference is if_icmpge (if compare greater/equal) versus if_icmpgt (if compare greater than).
Everything above is fact, the rest is my best guess as to how if_icmpge and if_icmpgt are handled based on a college course I took on assembly language. To get a better answer you should look up how your JVM handles these. My guess is that C++ also compiles down to a similar operation.
Edit: Documentation on
if_i<cond>is here
The way computers compare numbers is subtracting one from the other and checking if that number is 0 or not, so when doing a < b if subtracts b from a and sees if the result is less than 0 by checking the sign of the value (b - a < 0). To do a <= b though it has to do an additional step and subtract 1 (b - a - 1 < 0).
Normally this is a very miniscule difference, but this isn't any code, this is freaking bubble sort! O(n^2) is the average number of times we are doing this particular comparison because it's in the inner most loop.
Yes, it may have something to do with branch prediction I am not sure, I am not an expert on that, but I think this may also play a non-insignificant role.
'Nice programing' 카테고리의 다른 글
| 스마트 진행률 표시 줄 ETA 계산 (0) | 2020.10.27 |
|---|---|
| C / C ++에서 부호없는 왼쪽 시프트 이전의 마스킹이 너무 편집증 적입니까? (0) | 2020.10.27 |
| .gitignore의 git 하위 모듈을 무시하거나 저장소에 커밋합니까? (0) | 2020.10.27 |
| C ++의 접근 자 메서드 (getter 및 setter)에 대한 규칙 (0) | 2020.10.27 |
| iOS Private API 문서 (0) | 2020.10.27 |