"IF"가 비싸나요?

"IF"가 비싸나요?

---

저는 제 삶을 위해 우리 선생님이 그날 정확히 말한 것을 기억할 수 없으며 아마도 당신이 알기를 바랍니다.

모듈은 "데이터 구조 및 알고리즘"이며 그는 다음과 같은 내용을 우리에게 말했습니다.

if문은 가장 비싼 [뭔가]입니다. [something]은 [something]을 등록합니다.

네, 끔찍한 기억이 있고 정말 미안하지만 몇 시간 동안 인터넷 검색을했는데 아무것도 나오지 않았습니다. 어떤 아이디어?

---

(하드웨어에서) 매우 낮은 수준에서, 예, 경우 들 비싸다. 이유를 이해하려면 파이프 라인이 작동 하는 방식을 이해해야합니다 .

실행될 현재 명령은 일반적으로 명령 포인터 (IP) 또는 프로그램 카운터 (PC) 라고하는 것에 저장됩니다 . 이러한 용어는 동의어이지만 아키텍처마다 다른 용어가 사용됩니다. 대부분의 명령어에서 다음 명령어의 PC는 현재 PC에 현재 명령어의 길이를 더한 것입니다. 대부분의 RISC 아키텍처에서 명령어는 모두 일정한 길이이므로 PC를 일정한 양만큼 늘릴 수 있습니다. x86과 같은 CISC 아키텍처의 경우 명령어는 가변 길이 일 수 있으므로 명령어를 디코딩하는 로직은 현재 명령어가 다음 명령어의 위치를 ​​찾는 데 걸리는 시간을 파악해야합니다.

들어 가지 지침, 그러나 실행되는 다음 명령은 현재 명령 후 다음 위치가 아닙니다. 분기는 gotos입니다-프로세서에게 다음 명령어가 어디에 있는지 알려줍니다. 분기는 조건부 또는 무조건 부일 수 있으며 대상 위치는 고정 또는 계산 될 수 있습니다.

조건부 대 무조건 부는 이해하기 쉽습니다. 조건부 분기는 특정 조건이 유지되는 경우에만 사용됩니다 (예 : 한 숫자가 다른 숫자와 같은지 여부). 분기를 취하지 않으면 정상적으로 분기 후 다음 명령으로 제어가 진행됩니다. 무조건 분기의 경우 항상 분기가 사용됩니다. 조건부 분기는 if문과 for및 while루프 의 제어 테스트에 표시됩니다 . 무조건 분기는 무한 루프, 함수 호출, 함수 반환 break및 continue명령문, 악명 높은 goto명령문 등에서 표시됩니다 (이 목록은 완전하지 않습니다).

지점 대상은 또 다른 중요한 문제입니다. 대부분의 분기에는 고정 분기 대상이 있습니다. 컴파일 타임에 고정되는 코드의 특정 위치로 이동합니다. 여기에는 if문, 모든 종류의 루프, 일반 함수 호출 등 이 포함됩니다 . 계산 된 분기는 런타임에 분기의 대상을 계산합니다. 여기에는 switch명령문 (때때로), 함수에서 반환, 가상 함수 호출 및 함수 포인터 호출이 포함됩니다.

그렇다면이 모든 것이 성능에 어떤 의미가 있습니까? 프로세서가 파이프 라인에 분기 명령이 표시되는 것을 확인하면 파이프 라인을 계속 채우는 방법을 파악해야합니다. 프로그램 스트림에서 분기 다음에 오는 명령어를 파악하려면 (1) 분기를 사용할 것인지 (2) 분기 대상을 알아야합니다. 이를 파악하는 것을 분기 예측 이라고 하며 어려운 문제입니다. 프로세서가 올바르게 추측하면 프로그램이 최대 속도로 계속됩니다. 대신 프로세서가 잘못 추측 하면 잘못된 것을 계산하는 데 시간이 걸립니다. 이제 파이프 라인을 플러시하고 올바른 실행 경로의 명령으로 다시로드해야합니다. 결론 : 큰 성능 저하.

따라서 if 문이 비싼 이유는 분기 예측 오류 때문 입니다. 이것은 가장 낮은 수준입니다. 고급 코드를 작성하는 경우 이러한 세부 사항에 대해 전혀 걱정할 필요가 없습니다. 성능이 매우 중요한 코드를 C 또는 어셈블리로 작성하는 경우에만주의해야합니다. 이 경우 몇 가지 명령이 더 필요하더라도 분기없는 코드를 작성하는 것이 분기하는 코드보다 우월 할 수 있습니다. 당신은 같은 일을 계산하기 위해 할 수있는 멋진 비트 만지작 트릭이있다 abs(), min()및 max()분기없이.

---

"비싸다"는 매우 상대적인 용어로, 특히 " if"문과의 관계와 관련 하여 조건의 비용도 고려해야하기 때문입니다. 이는 몇 가지 짧은 CPU 명령어에서 원격 데이터베이스를 호출하는 함수의 결과를 테스트하는 것까지 다양합니다.

나는 그것에 대해 걱정하지 않을 것입니다. 임베디드 프로그래밍을하지 않는 한 " if" 의 비용에 대해 전혀 걱정할 필요가 없습니다 . 대부분의 프로그래머를 들어 그냥 않을거야 지금까지 앱의 성능을 구동 요인.

---

특히 RISC 아키텍처 마이크로 프로세서의 분기는 가장 값 비싼 명령어 중 일부입니다. 이는 많은 아키텍처에서 컴파일러가 가장 가능성이 높은 실행 경로를 예측하고 해당 명령을 실행 파일에 배치하므로 분기가 발생할 때 이미 CPU 캐시에 있기 때문입니다. 브랜치가 다른 방향으로 가면 메인 메모리로 돌아가서 새 명령어를 가져와야합니다. 이는 상당히 비쌉니다. 많은 RISC 아키텍처에서 모든 명령어는 분기 (종종 2 사이클 임)를 제외하고 하나의 사이클입니다. 여기서는 주요 비용에 대해 말하는 것이 아니므로 걱정하지 마십시오. 또한 컴파일러는 99 %의 시간보다 더 잘 최적화됩니다. ) EPIC 아키텍처 (Itanium이 예)에 대한 정말 멋진 점 중 하나는 브랜치의 양쪽에서 명령을 캐시 (및 처리 시작) 한 다음 브랜치의 결과가 나오면 필요하지 않은 세트를 버린다는 것입니다. 모두 다 아는. 이렇게하면 예상치 못한 경로를 따라 분기되는 경우 일반적인 아키텍처의 추가 메모리 액세스가 절약됩니다.

---

셀 성능에 대한 분기 제거 를 통한 성능 향상 기사를 확인하십시오 . 또 다른 재미있는 것은 Real Time Collision Detection Blog의 분기없는 선택 에 대한이 게시물 입니다.

이 질문에 대한 답변으로 이미 게시 된 우수한 답변 외에도 "if"문이 값 비싼 저수준 작업으로 간주되지만 상위 수준 환경에서 분기없는 프로그래밍 기술을 활용하려고한다는 점을 상기시켜 드리고 싶습니다. 스크립팅 언어 또는 비즈니스 로직 레이어 (언어에 관계없이)와 같은은 엄청나게 부적절 할 수 있습니다.

대부분의 경우 프로그램은 먼저 명확성을 위해 작성되고 두 번째로 성능에 최적화되어야합니다. 성능이 가장 중요한 여러 문제 영역이 있지만 대부분의 개발자는 렌더링 엔진의 핵심 또는 몇 주 동안 실행되는 고성능 유체 역학 시뮬레이션의 핵심에서 사용할 모듈을 작성하지 않습니다. 솔루션이 "그냥 작동"하는 것이 최우선 과제 인 경우 마지막으로 생각하는 것은 코드에서 조건 문의 오버 헤드를 줄일 수 있는지 여부입니다.

---

가능한 가장 낮은 수준 if은 다음과 같이 구성됩니다 (특정에 대한 모든 앱별 전제 조건을 계산 한 후 if).

• 일부 테스트 지침
• 테스트가 성공하면 코드의 특정 위치로 이동하고 그렇지 않으면 앞으로 진행합니다.

그와 관련된 비용 :

• 낮은 수준의 비교-일반적으로 1 CPU 작업, 매우 저렴
• 잠재적 인 점프-비용이 많이들 수 있음

점프가 비싸다는 이유에 대한 공명 :

• CPU에 의해 캐시되지 않은 것으로 밝혀지면 메모리에있는 임의 코드로 이동할 수 있습니다. 메인 메모리에 액세스해야하므로 속도가 더 느립니다.
• 최신 CPU는 분기 예측을 수행합니다. 성공 여부를 추측하고 파이프 라인에서 코드를 미리 실행하므로 속도가 빨라집니다. 예측이 실패하면 파이프 라인이 미리 수행 한 모든 계산이 무효화되어야합니다. 그것은 또한 비싼 작업입니다

요약하자면 :

• 만약 당신이 정말로, 정말로, 정말로 성능에 관심이 있다면.
• You should care about it if and only if you are writing real time raytracer or biological simulation or something similar. There is no reason to care about it in most of the real world.

---

if in itself is not slow. Slowness is always relative i bet for my life that you haven't ever felt the "overhead" of an if-statement. If you are going to make a high-performance code, you migh want to avoid branches anyway. What makes if slow is that the processor is preloading code from after the if based on some heuristic and whatnot. It will also stop pipelines from executing code directly after the if branch instruction in the machine code, since the processor doesn't know yet what path will be taken (in a pipelined processor, multiple instructions are interleaved and executed). Code executed could have to be executed in reverse (if the other branch was taken. it's called branch misprediction), or noop's be filled at those places so that this doesn't happen.

If if is evil, then switch is evil too, and &&, || too. Don't worry about it.

---

Maybe the branching kills the CPU instruction prefetching?

---

Modern processors have long execution pipelines which means that several instructions are executed in various stages at the same time. They may not always know the outcome of one instruction when the next one begins to run. When they run into a conditional jump (if) they sometimes have to wait until the pipeline is empty before they can know which way the instruction pointer should go.

I think of it as a long freight train. It can carry a lot of cargo fast in a straight line, but it corners badly.

Pentium 4 (Prescott) had a famously long pipeline of 31 stages.

More on Wikipedia

---

The only thing I can imagine this might be referring to is the fact that an if statement generally can result in a branch. Depending on the specifics of the processor architecture, branches can cause pipeline stalls or other less than optimal situations.

However, this is extremely situation specific - most modern processors have branch prediction capabilities that attempt to minimize the negative effects of branching. Another example would be how the ARM architecture (and probably others) can handle conditional logic - the ARM has instruction level conditional execution, so simple conditional logic results in no branching - the instructions simply execute as NOPs if the conditions are not met.

All that said - get your logic correct before worrying about this stuff. Incorrect code is as unoptimized as you can get.

---

As pointed out by many, conditional branches can be very slow on a modern computer.

That being said, there are a whole lot of conditional branches that don't live in if statements, you can't always tell what the compiler will come up with, and worrying about how long basic statements will take is virtually always the wrong thing to do. (If you can tell what the compiler will generate reliably, you may not have a good optimizing compiler.)

---

CPUs are deeply pipelined. Any branch instruction (if/for/while/switch/etc) means that the CPU doesn't really know what instruction to load and run next.

The CPU either stalls while waiting to know what to do, or the CPU takes a guess. In the case of an older CPU, or if the guess is wrong, you'll have to suffer a pipeline stall while it goes and loads the correct instruction. Depending on the CPU this can be as high as 10-20 instructions worth of stall.

Modern CPUs try to avoid this by doing good branch prediction, and by executing multiple paths at the same time, and only keeping the actual one. This helps out a lot, but can only go so far.

Good luck in the class.

Also, if you have to worry about this in real life, you're probably doing OS design, realtime graphics, scientific computing, or something similarly CPU-bound. Profile before worrying.

---

Also note that inside a loop is not necessarily very expensive.

Modern CPU assumes upon first visit of an if-statement, that the "if-body" is to be taken (or said the other way: it also assumes a loop-body to be taken multiple times) (*). Upon second and further visits, it (the CPU) can maybe look into the Branch History Table, and see how the condition was the last time (was it true? was it false?). If it was false the last time, then speculative execution will proceed to the "else" of the if, or beyond the loop.

(*) The rule is actually "forward branch not taken, backward branch taken". In an if-statement, there is only a [forward] jump (to the point after the if-body) if the condition evaluates to false (remember: the CPU anyways assumes to not take a branch/jump), but in a loop, there is maybe a forward branch to the position after the loop (not to be taken), and a backward branch upon repetetion (to be taken).

This is also one of the reasons why a call to a virtual function or a function-pointer-call is not that worse as many assume (http://phresnel.org/blog/)

---

Write your programs the clearest, simplest, cleanest way that isn't obviously inefficient. That makes the best use of the most expensive resource, you. Be it writing or later debugging (requires understanding) the program. If the performance isn't enough, measure where the bottlenecks are, and see how to mitigate them. Only on extremely rare occasions will you have to worry about individual (source) instructions when doing so. Performance is about selecting the right algorithms and data structures in the first line, careful programing, getting a fast enough machine. Use a good compiler, you'd be surprised when seeing the kind of code restructuring a modern compiler does. Restructuring code for performance is a sort of last resort measure, the code gets more complex (thus buggier), harder to modify, and thus all-around more expensive.

---

I had this argument with a friend of mine once. He was using a very naive circle algorithm, but claimed his to be faster than mine (The kind that only calculates 1/8th of the circle) because mine used if. In the end, the if statement was replaced with sqrt and somehow that was faster. Perhaps because the FPU has sqrt built in?

---

Some CPU's(like X86) provides branch prediction to programming level to avoid such a branch prediction latency.

Some compiler exposes(like GCC) these as a extension to higher level programming languages(like C/C++).

Refer likely()/unlikely() macros in the Linux kernel - how do they work? What's their benefit?.

---

The most expensive in terms of ALU usage? It uses up CPU registers to store the values to be compared and takes up time to fetch and compare the values each time the if statement is run.

Therefore an optimization of that is to do one comparison and store the result as a variable before the loop is run.

Just trying to interpret your missing words.

참고URL : https://stackoverflow.com/questions/315306/is-if-expensive