Java에서 (a*b!= 0)이 (a!= 0 & b!= 0)보다 빠른 이유는 무엇입니까?
자바에서 코드를 쓰고 있는데, 어느 시점에서 프로그램의 흐름은 두 개의 int 변수 "a"와 "b"가 0이 아닌지에 따라 결정됩니다(참고: a와 b는 절대 음이 아니며 정수 오버플로 범위 내에 있지 않습니다).
나는 그것을 로 평가할 수 있다.
if (a != 0 && b != 0) { /* Some code */ }
또는 다른 방법으로
if (a*b != 0) { /* Some code */ }
그 코드 조각이 실행당 수백만 번 실행될 것으로 예상되기 때문에 어떤 것이 더 빠를지 궁금했습니다.랜덤으로 생성된 거대한 어레이에서 이 어레이를 비교하여 실험을 수행했으며, 어레이의 희소성(데이터 분포 = 0)이 결과에 어떤 영향을 미치는지도 궁금했습니다.
long time;
final int len = 50000000;
int arbitrary = 0;
int[][] nums = new int[2][len];
for (double fraction = 0 ; fraction <= 0.9 ; fraction += 0.0078125) {
for(int i = 0 ; i < 2 ; i++) {
for(int j = 0 ; j < len ; j++) {
double random = Math.random();
if(random < fraction) nums[i][j] = 0;
else nums[i][j] = (int) (random*15 + 1);
}
}
time = System.currentTimeMillis();
for(int i = 0 ; i < len ; i++) {
if( /*insert nums[0][i]*nums[1][i]!=0 or nums[0][i]!=0 && nums[1][i]!=0*/ ) arbitrary++;
}
System.out.println(System.currentTimeMillis() - time);
}
그 나 'b가 ~이 될 되면 'a'는 'b'는 0%~3% 정도 .a*b != 0a!=0 && b!=0:
왜 그런지 궁금해요.누구 불 좀 밝혀줄 사람?컴파일러입니까, 아니면 하드웨어 레벨입니까?
편집: 궁금해서...분기 예측에 대해 배웠기 때문에 OR b에 대해 아날로그 비교가 0이 아닌 것을 알 수 있는지 궁금했습니다.
분기 예측의 효과는 예상과 같으며, 흥미롭게도 그래프는 X축을 따라 약간 뒤집혀 있습니다.
갱신하다
- 1을 더했습니다.!(a==0 || b==0)을 사용하다
도 2- 아는데요. - 아, 아, 아, 2- 아는데요.a != 0 || b != 0,(a+b) != 0 ★★★★★★★★★★★★★★★★★」(a|b) != 0호기심에서, 나뭇가지 예측에 대해 배우고 나서.단, 논리적으로 다른 식과 동일하지 않습니다.이는 OR b가 0이 아니어야 true가 반환되기 때문에 처리 효율을 비교할 수 없기 때문입니다.
3- 분석에 사용한 실제 벤치마크도 추가했습니다.이것은 임의의 int 변수를 반복하고 있을 뿐입니다.
은 4-를 했습니다.a != 0 & b != 0a != 0 && b != 0행동할 것이라는 예측과 함께a*b != 0분기 예측 효과를 제거할 수 있기 때문입니다.는 그것을 &을 사용하다 정수를 사용하는 이진 연산에만 사용되는 줄 알았습니다.
주의: 이 모든 것을 고려하던 상황에서 int overflow는 문제가 되지 않지만, 일반적인 상황에서는 확실히 중요한 고려 사항입니다.
CPU: 인텔 Core i7-3610QM @ 2.3GHz
버전: ™: 1.8.0_45
런타임 Java(TM) SE는 1.8.0_45-b14)
VM 25 모드Java HotSpot(TM) 64 트(VM ( 25 . 45 - b02, )
저는 당신의 벤치마킹에 결함이 있을 수 있다는 문제를 무시하고 그 결과를 액면 그대로 받아들이고 있습니다.
컴파일러입니까, 아니면 하드웨어 레벨입니까?
그 후자는, 다음과 같습니다.
if (a != 0 && b != 0)
2개의 메모리 로드와 2개의 조건부 브랜치로 컴파일 됩니다.
if (a * b != 0)
는 2개의 메모리 로드, 1개의 조건부 브랜치로 컴파일 됩니다.
하드웨어 수준의 분기 예측이 유효하지 않은 경우 두 번째 조건부 분기보다 곱셈 속도가 빠를 수 있습니다.비율을 높이면...지점 예측의 효과가 저하되고 있습니다.
조건부 분기가 느린 이유는 명령 실행 파이프라인이 정지하기 때문입니다.분기 예측은 분기 방향을 예측하고 이를 바탕으로 다음 명령을 추측적으로 선택함으로써 정지를 회피하는 것입니다.예측이 실패하면 다른 방향에 대한 명령이 로드되는 동안 지연이 발생합니다.
(주의: 위의 설명은 지나치게 단순합니다.보다 정확한 설명을 위해서는 어셈블리 언어 코더 및 컴파일러 라이터에 대해 CPU 제조원이 제공하는 자료를 참조해야 합니다.Branch Predictors의 Wikipedia 페이지는 좋은 배경입니다.)
단, 이 최적화에 주의할 필요가 있는 것이 있습니다." " " " " " " 에는 요?a * b != 0 오답? 을 계산하면 오버플로가 해 보십시오.제품을 계산하면 정수 오버플로가 발생하는 경우를 고려해 보십시오.
갱신하다
당신의 그래프는 내가 말한 것을 확인하는 경향이 있다.
분기에는 .
a * b != 0그리고 이건 그래프에 나와있어요.X 축에 0.9를 초과하는 곡선을 투영하면 1) 두 곡선이 약 1.0에서 만나고 2) 집합점은 X = 0.0의 Y 값과 거의 동일합니다.
업데이트 2
안 가요.a + b != 0 및a | b != 0사건들. 지점 예측자들의 논리에 뭔가 영리한 것이 있을 수 있어요.아니면 뭔가 다른 걸 나타낼 수도 있어요
(이러한 것은 특정 칩 모델 번호 또는 짝수 버전에 따라 다를 수 있습니다.벤치마크 결과는 다른 시스템에서 다를 수 있습니다.)
둘 다 가 아닌 인 러, 둘, 둘, 둘, 둘, 둘, 둘, 둘, 둘, 둘, 둘, however, however, however, however, however, however, however, however, however, however, however, however, however, however, however, however, however, however, however, however, however, , however,a ★★★★★★★★★★★★★★★★★」b.
당신의 벤치마크에는 몇 가지 결함이 있어 실제 프로그램에 대해 추론하는 데 유용하지 않을 수 있습니다.제 생각은 이렇습니다.
(a|b)!=0★★★★★★★★★★★★★★★★★」(a+b)!=0두 값 중 하나가 0이 아닌지를 테스트합니다.a != 0 && b != 0★★★★★★★★★★★★★★★★★」(a*b)!=0둘 다 0이 아닌지 테스트합니다.따라서 단순히 계산의 타이밍을 비교하는 것이 아닙니다.조건이 더 자주 참일 경우 더 많은 실행이 발생합니다.if몸매도 더 오래 걸립니다.(a+b)!=00이 되는 양의 값과 음의 값은 잘못된 동작을 하기 때문에 일반적인 경우에는 사용할 수 없습니다.,의 도,a=b=0x80000000(MIN_VALUE), 유유 ( ( ( ( ( ( ( ( ( ( ( ( ( ( (.similarly유 similarly,, similarly 、
(a*b)!=0값이 오버플로우하면 잘못된 일을 하게 됩니다.랜덤 예: 196608 * 327680은 0입니다.진정한 결과는 2로 나눌32 수 있기 때문입니다.따라서 32비트의 하한은 0입니다.또한 이 비트만이 이 비트일 경우 얻을 수 있는 값입니다.int★★★★★★ 。VM)의 첫 몇 의 실행 동안 합니다.
fraction)는, 「」, 「Doop입니다.fraction브랜치가 거의 취득되지 않는 경우는 0 입니다.는, 「시작하다」를하면, 을 실시할 .fraction0.여기서 VM이 어레이 경계 검사 중 일부를 제거할 수 없는 한 경계 검사만으로 표현식에 4개의 다른 지점이 있습니다. 이는 낮은 수준에서 무슨 일이 일어나고 있는지 파악하는 데 있어 복잡한 요인입니다.을 2개의 배열로 2차원 배열을 2차원 배열을 바꾸면 수 .
nums[0][i]★★★★★★★★★★★★★★★★★」nums[1][i]로로 합니다.nums0[i]★★★★★★★★★★★★★★★★★」nums1[i].CPU 분기 예측 변수는 데이터의 짧은 패턴 또는 모든 분기 실행 또는 수행 여부를 탐지합니다.랜덤하게 생성된 벤치마크 데이터는 분기 예측 변수의 경우 최악의 시나리오입니다.실제 데이터에 예측 가능한 패턴이 있거나 모두 0 및 모두 0이 아닌 값이 장기간 실행되는 경우 브랜치 비용이 훨씬 절감될 수 있습니다.
는 조건 평가 을 미칠 수 될 수 여부, 수 있는지 여부, 중 가 있는지 을 미치기 입니다. 때문에 조건 자체의 평가 성능에 영향을 미칠 수 있습니다.
nums조건을 평가한 후 값을 재사용해야 합니다.단순히 벤치마크에서 카운터를 늘리는 것은 실제 코드가 수행하는 작업에 대한 완벽한 자리 표시자가 아닙니다.System.currentTimeMillis()대부분의 시스템에서 +/- 10ms보다 정확하지 않습니다.System.nanoTime()보통 더 정확합니다.
여러 가지 불확실성이 존재하며, VM 또는 CPU에서 속도가 더 빠른 트릭은 다른 VM 또는 CPU에서 속도가 더 느릴 수 있기 때문에 이러한 종류의 마이크로 최적화에서는 항상 명확한 말을 하기 어렵습니다.64비트 버전이 아닌 32비트 HotSpot JVM을 실행하는 경우 "클라이언트" VM은 "서버" VM과 다른 (웨이커) 최적화 기능을 가지고 있습니다.
VM에서 생성된 머신 코드를 분해할 수 있다면 VM의 기능을 추측하지 말고 분해하십시오.
여기 답변은 좋지만, 상황을 개선할 수 있는 아이디어가 있었습니다.
2개의 브런치 및 관련된 브런치 예측이 원인일 가능성이 높기 때문에 로직을 전혀 변경하지 않고 브런치를 1개의 브런치로 줄일 수 있습니다.
bool aNotZero = (nums[0][i] != 0);
bool bNotZero = (nums[1][i] != 0);
if (aNotZero && bNotZero) { /* Some code */ }
하는 것도 효과적일 수 있다
int a = nums[0][i];
int b = nums[1][i];
if (a != 0 && b != 0) { /* Some code */ }
그 이유는 단락 규칙에 따라 첫 번째 부울이 false일 경우 두 번째 부울은 평가되지 않기 때문입니다.하지 않기 더.nums[1][i]nums[0][i]그러면여러분들은그렇게생각하지않을수도있습니다.nums[1][i]평가되지만 컴파일러는 사용자가 평가했을 때 범위를 벗어나거나 null ref를 참조하지 않는다고 확신할 수 없습니다.을 단순한는 두 것을 할 수 .
곱셈을 할 때 숫자 하나가 0이라도 곱은 0입니다.쓰면서
(a*b != 0)
제품의 결과를 평가하여 0부터 시작하는 반복의 처음 몇 가지 발생을 제거합니다.그 결과 비교는 조건이 다음과 같은 경우보다 적다.
(a != 0 && b != 0)
여기서 모든 요소를 0과 비교하여 평가합니다.따라서 필요한 시간이 단축됩니다.하지만 두 번째 조건이 더 정확한 해결책을 줄 수 있다고 생각합니다.
분기를 예측할 수 없게 만드는 랜덤화된 입력 데이터를 사용하고 있습니다.실제로 브랜치는 예측 가능한 경우가 많기 때문에(~90%) 실제 코드에서는 브랜치 풀 코드가 더 빠를 가능성이 있습니다.
할지 모르겠네요.a*b != 0 수 (a|b) != 0일반적으로 정수 곱셈은 비트 단위 OR보다 비용이 많이 듭니다.하지만 이런 일들은 가끔 이상해져요.예를 들어 Gallery of Processor Cache Effects의 "예 7: 하드웨어 복잡성" 예를 참조하십시오.
오래된 질문인 것은 알지만 호기심과 훈련을 위해 JMH를 사용하여 몇 가지 테스트를 해봤습니다. 결과는 약간 달랐습니다.
- OR( 「」OR( )
a | b != 0) 및 )a * b != 0가 가장 빨랐습니다 - AND 준 and AND ）
a!=0 & b!=0. - OR('AND' OR')
a!=0 && b!=0,!(a!=0 || b!=0)느리다
면책사항:나는 JMH 전문가도 되지 않았다.
이 코드는 문제가 된 코드를 재현하기 위해 비트 단위 OR을 추가했습니다.
@Warmup(iterations = 5, time = 100, timeUnit = TimeUnit.MILLISECONDS)
@Measurement(iterations = 10, time = 100, timeUnit = TimeUnit.MILLISECONDS)
@Fork(value = 3)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@State(Scope.Benchmark)
public class MultAnd {
public static void main(String[] args) throws RunnerException {
Options opt = new OptionsBuilder()
.include(MultAnd.class.getSimpleName())
.build();
new Runner(opt).run();
}
private static final int size = 50_000_000;
@Param({"0.00", "0.10", "0.20", "0.30", "0.40", "0.45",
"0.50", "0.55", "0.60", "0.70", "0.80", "0.90",
"1.00"})
private double fraction;
private int[][] nums;
@Setup
public void setup() {
nums = new int[2][size];
for(int i = 0 ; i < 2 ; i++) {
for(int j = 0 ; j < size ; j++) {
double random = Math.random();
if (random < fraction)
nums[i][j] = 0;
else
nums[i][j] = (int) (random*15 + 1);
}
}
}
@Benchmark
public int and() {
int s = 0;
for (int i = 0; i < size; i++) {
if ((nums[0][i]!=0) & (nums[1][i]!=0))
s++;
}
return s;
}
@Benchmark
public int andAnd() {
int s = 0;
for (int i = 0; i < size; i++) {
if ((nums[0][i]!=0) && (nums[1][i]!=0))
s++;
}
return s;
}
@Benchmark
public int bitOr() {
int s = 0;
for (int i = 0; i < size; i++) {
if ((nums[0][i] | nums[1][i]) != 0)
s++;
}
return s;
}
@Benchmark
public int mult() {
int s = 0;
for (int i = 0; i < size; i++) {
if (nums[0][i]*nums[1][i] != 0)
s++;
}
return s;
}
@Benchmark
public int notOrOr() {
int s = 0;
for (int i = 0; i < size; i++) {
if (!((nums[0][i]!=0) || (nums[1][i]!=0)))
s++;
}
return s;
}
}
결과는 다음과 같습니다.
REMEMBER: The numbers below are just data. To gain reusable insights, you need to follow up on
why the numbers are the way they are. Use profilers (see -prof, -lprof), design factorial
experiments, perform baseline and negative tests that provide experimental control, make sure
the benchmarking environment is safe on JVM/OS/HW level, ask for reviews from the domain experts.
Do not assume the numbers tell you what you want them to tell.
Benchmark (fraction) Mode Cnt Score Error Units
MultAnd.and 0.00 avgt 30 33.238 ± 0.883 ms/op
MultAnd.and 0.10 avgt 30 48.011 ± 1.635 ms/op
MultAnd.and 0.20 avgt 30 48.284 ± 1.797 ms/op
MultAnd.and 0.30 avgt 30 47.969 ± 1.463 ms/op
MultAnd.and 0.40 avgt 30 48.999 ± 2.881 ms/op
MultAnd.and 0.45 avgt 30 47.804 ± 1.053 ms/op
MultAnd.and 0.50 avgt 30 48.332 ± 1.990 ms/op
MultAnd.and 0.55 avgt 30 47.457 ± 1.210 ms/op
MultAnd.and 0.60 avgt 30 127.530 ± 3.104 ms/op
MultAnd.and 0.70 avgt 30 92.630 ± 1.471 ms/op
MultAnd.and 0.80 avgt 30 69.458 ± 1.609 ms/op
MultAnd.and 0.90 avgt 30 55.421 ± 1.443 ms/op
MultAnd.and 1.00 avgt 30 30.672 ± 1.387 ms/op
MultAnd.andAnd 0.00 avgt 30 33.187 ± 0.978 ms/op
MultAnd.andAnd 0.10 avgt 30 110.943 ± 1.435 ms/op
MultAnd.andAnd 0.20 avgt 30 177.527 ± 2.353 ms/op
MultAnd.andAnd 0.30 avgt 30 226.247 ± 1.879 ms/op
MultAnd.andAnd 0.40 avgt 30 266.316 ± 18.647 ms/op
MultAnd.andAnd 0.45 avgt 30 258.120 ± 2.638 ms/op
MultAnd.andAnd 0.50 avgt 30 259.727 ± 3.532 ms/op
MultAnd.andAnd 0.55 avgt 30 248.706 ± 1.419 ms/op
MultAnd.andAnd 0.60 avgt 30 229.825 ± 1.256 ms/op
MultAnd.andAnd 0.70 avgt 30 177.911 ± 2.787 ms/op
MultAnd.andAnd 0.80 avgt 30 121.303 ± 2.724 ms/op
MultAnd.andAnd 0.90 avgt 30 67.914 ± 1.589 ms/op
MultAnd.andAnd 1.00 avgt 30 15.892 ± 0.349 ms/op
MultAnd.bitOr 0.00 avgt 30 33.271 ± 1.896 ms/op
MultAnd.bitOr 0.10 avgt 30 35.597 ± 1.536 ms/op
MultAnd.bitOr 0.20 avgt 30 42.366 ± 1.641 ms/op
MultAnd.bitOr 0.30 avgt 30 58.385 ± 0.778 ms/op
MultAnd.bitOr 0.40 avgt 30 85.567 ± 1.678 ms/op
MultAnd.bitOr 0.45 avgt 30 32.152 ± 1.345 ms/op
MultAnd.bitOr 0.50 avgt 30 32.190 ± 1.357 ms/op
MultAnd.bitOr 0.55 avgt 30 32.335 ± 1.384 ms/op
MultAnd.bitOr 0.60 avgt 30 31.910 ± 1.026 ms/op
MultAnd.bitOr 0.70 avgt 30 31.783 ± 0.807 ms/op
MultAnd.bitOr 0.80 avgt 30 31.671 ± 0.745 ms/op
MultAnd.bitOr 0.90 avgt 30 31.329 ± 0.708 ms/op
MultAnd.bitOr 1.00 avgt 30 30.530 ± 0.534 ms/op
MultAnd.mult 0.00 avgt 30 30.859 ± 0.735 ms/op
MultAnd.mult 0.10 avgt 30 33.933 ± 0.887 ms/op
MultAnd.mult 0.20 avgt 30 34.243 ± 0.917 ms/op
MultAnd.mult 0.30 avgt 30 33.825 ± 1.155 ms/op
MultAnd.mult 0.40 avgt 30 34.309 ± 1.334 ms/op
MultAnd.mult 0.45 avgt 30 33.709 ± 1.277 ms/op
MultAnd.mult 0.50 avgt 30 37.699 ± 4.029 ms/op
MultAnd.mult 0.55 avgt 30 36.374 ± 2.948 ms/op
MultAnd.mult 0.60 avgt 30 100.354 ± 1.553 ms/op
MultAnd.mult 0.70 avgt 30 69.570 ± 1.441 ms/op
MultAnd.mult 0.80 avgt 30 47.181 ± 1.567 ms/op
MultAnd.mult 0.90 avgt 30 33.552 ± 0.999 ms/op
MultAnd.mult 1.00 avgt 30 30.775 ± 0.548 ms/op
MultAnd.notOrOr 0.00 avgt 30 15.701 ± 0.254 ms/op
MultAnd.notOrOr 0.10 avgt 30 68.052 ± 1.433 ms/op
MultAnd.notOrOr 0.20 avgt 30 120.393 ± 2.299 ms/op
MultAnd.notOrOr 0.30 avgt 30 177.729 ± 2.438 ms/op
MultAnd.notOrOr 0.40 avgt 30 229.547 ± 1.859 ms/op
MultAnd.notOrOr 0.45 avgt 30 250.660 ± 4.810 ms/op
MultAnd.notOrOr 0.50 avgt 30 258.760 ± 2.190 ms/op
MultAnd.notOrOr 0.55 avgt 30 258.010 ± 1.018 ms/op
MultAnd.notOrOr 0.60 avgt 30 254.732 ± 2.076 ms/op
MultAnd.notOrOr 0.70 avgt 30 227.148 ± 2.040 ms/op
MultAnd.notOrOr 0.80 avgt 30 180.193 ± 4.659 ms/op
MultAnd.notOrOr 0.90 avgt 30 112.212 ± 3.111 ms/op
MultAnd.notOrOr 1.00 avgt 30 33.458 ± 0.952 ms/op
「이것들」은 다음과 같습니다.
언급URL : https://stackoverflow.com/questions/35531369/why-is-ab-0-faster-than-a-0-b-0-in-java
'IT이야기' 카테고리의 다른 글
| stubing에 Argument Captor를 사용하는 방법 (0) | 2022.06.29 |
|---|---|
| 함수 포인터, 폐쇄 및 람다 (0) | 2022.06.29 |
| Java에서 'public static void'는 무엇을 의미합니까? (0) | 2022.06.29 |
| Vue@click.native가 작동하지 않습니까? (0) | 2022.06.29 |
| [Vue warn] :지시문을 확인하지 못했습니다. bin (0) | 2022.06.29 |