Java에서 곱하고 나누는 것보다 비트 이동이 더 빠릅니까?

Java에서 곱하고 나누는 것보다 비트 이동이 더 빠릅니까? .그물?

---

2의 거듭 제곱을 사용하는 경우 대부분의 CPU에서 비트를 왼쪽과 오른쪽으로 이동하는 것이 곱셈 및 나눗셈 작업보다 훨씬 빠릅니다. 그러나 일부 판독기 및 일부 알고리즘에서는 코드의 명확성을 떨어 뜨릴 수 있습니다. 성능을 위해 비트 시프 팅이 정말로 필요합니까, 아니면 컴파일러 또는 VM이 ​​사례를 인식하고 최적화 할 것으로 예상 할 수 있습니까 (특히, 2의 거듭 제곱이 리터럴 일 때)? 저는 주로 Java 및 .NET 동작에 관심이 있지만 다른 언어 구현에 대한 통찰력도 환영합니다.

---

오늘날 대부분의 컴파일러는 2의 거듭 제곱으로 곱하기 또는 나누기를 변환하여 연산을 이동하는 것 이상을 수행합니다. 최적화 할 때 많은 컴파일러는 2의 거듭 제곱이 아니더라도 컴파일 시간 상수를 사용하여 곱하기 또는 나누기를 최적화 할 수 있습니다. 종종 곱하기 또는 나누기는 일련의 시프트 및 더하기로 분해 될 수 있으며, 일련의 연산이 더 빠를 경우 곱하기 또는 나누기보다 컴파일러가이를 사용합니다.

상수로 나누기 위해 컴파일러는 종종 연산을 '매직 넘버'와 시프트로 곱하는 것으로 변환 할 수 있습니다. 곱셈이 나눗셈 연산보다 훨씬 더 빠르기 때문에 이것은 클록 사이클을 크게 절약 할 수 있습니다.

Henry Warren의 책인 Hacker 's Delight 에는이 주제에 대한 풍부한 정보가 있으며,이 주제는 동반 웹 사이트에서도 잘 다룹니다.

• http://www.hackersdelight.org/

다음에서 토론 (링크 포함)을 참조하십시오.

• 어셈블리 코드 읽기

어쨌든,이 모든 것은 컴파일러가 마이크로 최적화의 지루한 세부 사항을 처리 할 수 ​​있도록 귀결됩니다. 컴파일러를 능가하는 작업을 수행 한 지 몇 년이 지났습니다.

---

소금의 가치가있는 거의 모든 환경이이를 최적화 할 것입니다. 그렇지 않으면 더 큰 물고기를 튀길 수 있습니다. 진지하게, 이것에 대해 1 초 더 생각을 낭비하지 마십시오. 성능 문제가있을 때 알 수 있습니다. 그리고 프로파일 러를 실행 한 후에는 원인을 알 수 있으며 해결 방법이 명확해야합니다.

당신은 "그럼 내가 대신 무작위로 시작, 내 응용 프로그램이 너무 느렸다 사람의 말을 듣지 않습니다 x * 2으로 x << 1모든 것이 해결되었습니다!" 성능 문제는 일반적으로 동일한 작업을 1 % 더 빠르게 수행하는 방법을 찾는 것이 아니라 훨씬 적은 작업을 수행하는 방법을 찾는 것으로 해결됩니다.

---

이 경우 인간은 잘못되었습니다.

99 %가 현대 (그리고 미래의) 컴파일러를 두 번째로 추측하려고 할 때.
99.9 %가 현대 (그리고 미래의 모든) JIT를 동시에 추측하려고 할 때.
현대적 (그리고 미래의 모든) CPU 최적화를 두 번째 추측하려고 할 때 99.999 %.

수행 방법이 아니라 수행하려는 작업을 정확하게 설명하는 방식으로 프로그래밍하십시오. JIT, VM, 컴파일러 및 CPU의 향후 버전은 모두 독립적으로 개선되고 최적화 될 수 있습니다. 너무 작고 구체적인 것을 지정하면 향후 모든 최적화의 이점을 잃게됩니다.

---

시프트 연산에 대한 리터럴 2 제곱 곱셈 최적화에 거의 확실히 의존 할 수 있습니다. 이것은 컴파일러 구성의 학생들이 배우게 될 첫 번째 최적화 중 하나입니다. :)

그러나 나는 이것에 대한 어떤 보장도 없다고 생각합니다. 소스 코드는 옵티 마이저에게 무엇을해야하는지 알려주기보다는 의도를 반영해야합니다 . 수량을 늘리려면 곱하기를 사용하십시오. 비트 필드를 한 위치에서 다른 위치로 이동하는 경우 (RGB 색상 조작을 생각해보십시오) 시프트 연산을 사용하십시오. 어느 쪽이든 소스 코드는 실제로 수행하는 작업을 반영합니다.

---

아래로 이동하고 나누면 (자바에서) 음수, 홀수에 대해 다른 결과가 제공됩니다.

int a = -7;
System.out.println("Shift: "+(a >> 1));
System.out.println("Div:   "+(a / 2));

인쇄물:

Shift: -4
Div:   -3

Java에는 부호없는 숫자가 없기 때문에 Java 컴파일러가이를 최적화 할 수는 없습니다.

---

테스트 한 컴퓨터에서 정수 나누기는 다른 작업보다 4 ~ 10 배 느립니다 .

컴파일러가 나눗셈을 2의 배수로 바꾸고 차이를 볼 수없는 경우, 2의 배수가 아닌 나눗셈은 상당히 느립니다.

예를 들어, 255로 많은 분할이 많은 (그래픽) 프로그램이 있습니다. 실제로 내 계산은 다음과 같습니다.

r = (((top.R - bottom.R) * alpha + (bottom.R * 255)) * 0x8081) >> 23;

이전 계산보다 훨씬 빠르다는 것을 확인할 수 있습니다.

r = ((top.R - bottom.R) * alpha + (bottom.R * 255)) / 255;

따라서 컴파일러는 최적화의 모든 트릭을 수행 할 수 없습니다.

---

나는 "그게 중요한 일을하고있는거야?"라고 물을 것입니다. 먼저 가독성과 유지 보수성을 위해 코드를 디자인하십시오. 비트 시프트 대 표준 곱셈을 수행하면 성능 차이가 발생할 가능성은 매우 작습니다.

---

하드웨어에 따라 다릅니다. 마이크로 컨트롤러 또는 i386에 대해 이야기하고 있다면 시프트가 더 빠를 수 있지만 여러 답변에 따르면 컴파일러는 일반적으로 최적화를 수행합니다.

최신 (Pentium Pro 이상) 하드웨어에서 파이프 라이닝은이를 완전히 무관하게 만들고 일반적으로 얻을 수있는 것보다 훨씬 더 많은 최적화를 잃어버린다는 것을 의미합니다.

마이크로 최적화는 시간 낭비 일뿐만 아니라 제대로하기가 매우 어렵습니다.

---

이 microbenchmark 의 결과에 따르면 이동은 나누는 것보다 두 배 빠릅니다 (Oracle Java 1.7.0_72).

---

컴파일러 (컴파일 타임 상수) 또는 JIT (런타임 상수)가 제수 또는 곱셈이 2의 거듭 제곱이고 정수 산술이 수행되고 있음을 알고 있으면이를 시프트로 변환합니다.

---

방금이 코드를 작성하고 1 씩 이동하는 것이 실제로 2를 곱하는 것보다 느리다는 것을 깨달았을 때 저는 놀랐습니다!

(편집 : 마이클 마이어스의 제안 후 오버플로를 중지하도록 코드를 변경했지만 결과는 동일합니다! 여기서 무엇이 잘못 되었나요?)

import java.util.Date;

public class Test {
    public static void main(String[] args) {
        Date before = new Date();
        for (int j = 1; j < 50000000; j++) {
            int a = 1 ;
            for (int i = 0; i< 10; i++){
                a *=2;
            }
        }
        Date after = new Date();
        System.out.println("Multiplying " + (after.getTime()-before.getTime()) + " milliseconds");
        before = new Date();
        for (int j = 1; j < 50000000; j++) {
            int a = 1 ;
            for (int i = 0; i< 10; i++){
                a = a << 1;
            }
        }
        after = new Date();
        System.out.println("Shifting " + (after.getTime()-before.getTime()) + " milliseconds");
    }
}

결과는 다음과 같습니다.

639 밀리 초 곱하기
718 밀리 초 이동

---

대부분의 컴파일러는 적절한 경우 곱셈과 나눗셈을 비트 시프트로 전환합니다. 가장 쉬운 최적화 방법 중 하나입니다. 따라서 주어진 작업에 대해 더 쉽게 읽을 수 있고 적절한 작업을 수행해야합니다.

---

이것은 Savvas Dalkitsis가 수행 한 벤치 마크 분석입니다. 이 테스트는 비트 시프 팅에 대한 곱셈 속도를 확인하지만 사용 된 값은 동일하지 않습니다. 값을 표시하는 C #에서 아래 코드를 확인하십시오.)

for (int i = 0, j = 1, k = 1; i < 10; i++)
{
  j = j * 2;
  k <<= 2;
  Console.WriteLine("{0} {1}", j, k);
}

C #에 표시된 값이있는 Savvas Dalkitsis 예제의 해당 코드는 다음과 같습니다.

    public static void Main(String[] args)
    {
        for (int i = 0, j = 1, k = 1; i < 10; i++)
        {
            j = j * 2; k <<= 2;
            Console.WriteLine("{0} {1}", j, k);
        }
        Console.WriteLine("-----------------------------------------------");


        DateTime before = DateTime.Now;
        for (int j = 1; j < 500000000; j++)
        {
            int a = 1;
            for (int i = 0; i < 10; i++) a *= 2;
        }
        DateTime after = DateTime.Now;

        Console.WriteLine("Multiplying " + (after - before).ToString() + " milliseconds");

        before = DateTime.Now;
        for (int j = 1; j < 500000000; j++)
        {
            int a = 1;
            for (int i = 0; i < 10; i++) a = a << 1;
        }
        after = DateTime.Now;
        Console.WriteLine("Shifting " + (after - before).ToString() + " milliseconds");
        Console.ReadKey();
    }

참고URL : https://stackoverflow.com/questions/1168451/is-shifting-bits-faster-than-multiplying-and-dividing-in-java-net