[JAVA] 컴퓨터 구조 관점에서 바라본 if문, switch문 성능 차이

권유정·2024년 2월 26일
Computer StructureJava
1

Java

목록 보기
1/2

개요

Java에서 if문과 switch문은 프로그래밍에서 자주 사용되는 조건 분기 구문이다. 이 둘 간에는 성능 차이가 있다. 3학년 때, 컴퓨터 구조 전공을 공부하면서 Switch문은 branch 명령이 없기 때문에 더 좋은 성능을 가진다라고 배웠던 기억이 있다. Java의 컴파일 코드를 보면서 위와 같은 관점으로 성능 차이가 작동하는 지 궁금해졌다.
따라서 이번 글에서는 JVM(+JIT)이 if문과 switch문을 어떻게 처리하는지 살펴보고, 그에 따른 성능 차이를 이해해보려고 한다.


  • Java 7 이후의 변화: Java 7 버전에서 switch문이 문자열(String)을 지원하게 되면서, 이전 버전에 비해 훨씬 더 효율적인 바이트 코드를 생성할 수 있게 되었다
  • switch 문법은 JVM에서 특별히 tableswitch와 lookupswitch 명령을 활용한다.

"자바 컴파일러는 일반적으로 if-then-else문보다 switch 문에서 더 효율적인 바이트 코드를 생성한다."
원문: The Java compiler generates generally more efficient bytecode from switchstatements that use String objects than from chained if-then-else statements.
JAVA7 : Strings in switch Statements
Why is the switch statement faster than if else for String in Java 7?


switch문의 컴파일 과정

  • Java의 JVM 컴파일 과정에서 switch문은 tableswitch 및 lookupswitch 명령을 사용하여 컴파일된다.

  • tableswitch 명령은 밀집된 케이스에서 효율적으로 작동한다.

  • lookupswitch 명령은 희소한 케이스에서 효율적으로 작동한다.

  • 위 명령어들은 상수 시간 (O(1))으로 특정 케이스로 점프할 수 있게 해주므로, 케이스의 수와 무관하게 동일한 시간이 소요된다.

  • 점프 테이블: 컴파일러는 값의 범위에 따라 점프 테이블을 생성하여, 실행 시에 해당 테이블을 참조해 바로 점프할 수 있는 최적화를 수행.

  • 범위 검사: 점프 전에 주어진 값이 유효한 범위 내에 있는지 검사하고, 유효하지 않을 경우 default 구문으로 이동.

    "스위치 문의 컴파일은 tableswitch 및 lookupswitch 명령을 사용합니다."
    원문 : Compilation of switch statements uses the tableswitch and lookupswitch instructions.
    JAVA17 3.10. Compiling Switches


tableswitch 명령

  • dense 케이스에 적합
  • ㄴ= 주로 연속적인 정수 케이스 값에 사용된다.
    • 바이트 코드 해석기나 JIT 컴파일러는 이를통해 빠르게 점프 가능
  • 해당 값에 대한 직접 점프를 허용하는 고정된 테이블을 생성한다.
  • 이는 실행 시간을 개선하고 예측 가능한 성능을 제공한다.

int chooseNear(int i) {
    switch (i) {
        case 0:  return  0;
        case 1:  return  1;
        case 2:  return  2;
        default: return -1;
    }
}

아래는 위의 java 코드를 컴파일한 코드이다. i 값에 대한 케이스가 맞다면 해당 줄로 jump 해버린다.

  • iload_1: 지역 변수 1번(이 경우 메소드의 인자 i)을 스택의 맨 위로 로드
  • tableswitch: 이 명령어는 i의 값에 따라 다른 인덱스로 점프. 인덱스는 0에서 2까지 유효
    • 0 to 2: i 값이 0, 1, 그리고 2에 대응하는 케이스입니다.
    • 각 케이스 숫자 뒤에 오는 숫자는 해당 케이스의 바이트코드 상의 명령 주소를 나타냄.
    • default: i의 값이 해당 범위에 맞지 않는 경우에 실행할 코드의 시작 주소.
Method int chooseNear(int)
0   iload_1             // Push local variable 1 (argument i)
1   tableswitch 0 to 2: // Valid indices are 0 through 2
      0: 28             // If i is 0, continue at 28
      1: 30             // If i is 1, continue at 30
      2: 32             // If i is 2, continue at 32
      default:34        // Otherwise, continue at 34
28  iconst_0            // i was 0; push int constant 0...
29  ireturn             // ...and return it
30  iconst_1            // i was 1; push int constant 1...
31  ireturn             // ...and return it
32  iconst_2            // i was 2; push int constant 2...
33  ireturn             // ...and return it
34  iconst_m1           // otherwise push int constant -1...
35  ireturn             // ...and return it

lookupswitch 명령

  • sparse 케이스 값에 적합
  • tableswitch 명령의 테이블 표현의 단점
    • 스위치 케이스가 드문드문할 경우, 공간 측면에서 비효율적
    • 이 때, lookupswitch 명령이 대신 사용될 수도 있음
  • 비연속적인 케이스 값에 사용되며, 케이스 값과 함께 키-값 쌍을 사용하는 테이블을 포함한다.
    • 키-값 쌍의 탐색 방법은 일반적으로 이진 탐색(binary search)을 활용하기 때문에, 탐색 시간은 케이스의 개수에 대해 O(log n) 시간 복잡도를 가짐.
  • lookupswitch 명령 실행 시간에, 스위치의 식 값은 테이블의 키와 비교된다.
    • 키 중 하나가 식 값과 일치하면, 일치하는 케이스로 점프한다.
    • 키가 일치하지 않으면, 실행은 기본 타겟에서 계속된다.

int chooseFar(int i) {
    switch (i) {
        case -100: return -1;
        case 0:    return  0;
        case 100:  return  1;
        default:   return -1;
    }
}

아래는 위 java 코드를 컴파일한 코드이다.

  • iload_1: 지역 변수 1번(이 경우 메소드의 인자 i)을 스택의 맨 위로 로드
  • lookupswitch:
    • 3: 테이블에 있는 키-값 쌍의 개수
    • 키-값 쌍: 다음과 같이 정의됨.
      • 100: 36: i가 -100일 경우, 명령어 주소 36으로 점프
      • 0: 38: i가 0일 경우, 명령어 주소 38으로 점프.
      • 100: 40: i가 100일 경우, 명령어 주소 40으로 점프.
    • default: 42: 케이스에 해당하지 않는 모든 값에 대해서는 명령어 주소 42로 점프.
Method int chooseFar(int)
0   iload_1
1   lookupswitch 3:
         -100: 36
            0: 38
          100: 40
      default: 42
36  iconst_m1
37  ireturn
38  iconst_0
39  ireturn
40  iconst_1
41  ireturn
42  iconst_m1
43  ireturn

if문의 컴파일 코드는?

  • 단적인 조건 검사
    • if-then-else문은 조건 검사를 순차적으로 수행하여 참인 조건을 찾을 때까지 반복.
    • 이 과정에서 분기 예측(branch prediction) 부하가 발생할 수 있으며, 조건이 늘어날수록 검사 시간도 증가한다(O(n)).
  • 'if' 문은 주로 ifeq, ifne 같은 비교 연산자와 함께 사용되어 조건에 따라 프로그램의 흐름을 제어한다.
    • 조건이 참이면 지정된 블록으로 제어를 옮기고, 그렇지 않으면 다음 구문으로 넘어간다.

if (x == 1) {
    // do something
} else if (x == 2) {
    // do something else
} else {
    // default action
}

아래는 위의 코드 컴파일한 코드이다.

  • 이 경우, 각 if 문마다 조건을 확인하고, 해당 조건이 참일 경우 해당 코드 블록으로 분기한다.
    • +) ifcmpne('같지 않음' 테스트에 대해 두 값 비교)는 branch 명령어에 해당한다.
  • 또한, if문은 if_acmpeq, if_icmpeq 등의 명령어를 사용하여 조건을 체크하고, 이는 선형 시간(complexity O(n))을 필요로 한다. 따라서 if문의 조건이 많아질수록 실행 시간도 증가하게 되는 것.
0: iload_1     // 로컬 변수 테이블에서 변수 x를 스택에 푸시
1: iconst_1    // 정수 1을 스택에 푸시
2: if_icmpeq 8 // 스택의 상위 두 개의 int 값을 비교하고, 두 값이 같으면(즉, x == 1이면) 프로그램의 흐름을 바이트코드의 8번째 줄로 이동시킴
5: iconst_2    // 정수 2를 스택 푸시합
6: if_icmpeq 14// 스택의 상위 두 개의 int 값을 비교하고, 두 값이 같으면(즉, x == 2이면) 프로그램의 흐름을 바이트코드의 14번째 줄로 이동시킴
9: // default action. 위의 모든 조건이 거짓이었을 경우 실행되는 기본 동작 코드
...

성능 측정

아래는 성능 측정을 위한 코드이다.

package Performance;

public class SwitchVSIf {
    long startTime, endTime;

    public void process() {
        this.TestTableSwitch();
        this.TestLookupSwitch();
        this.TestIfElse();
    }

    private void TestTableSwitch() {
        startTime = System.nanoTime();
        for (int i = 0; i <= 100000; i++) {
            switch (i % 10) {
                case 1:
                case 2:
                case 3:
                case 4:
                case 5:
                case 6:
                case 7:
                case 8:
                case 9:
                case 10:
                    break;
                default:
                    break;
            }
        }
        endTime = System.nanoTime();
        System.out.println("Time for tableswitch: " + (endTime - startTime) + " ns");
    }

    private void TestLookupSwitch() {
        startTime = System.nanoTime();
        for (int i = 0; i <= 100000; i++) {
            switch (i % 10) {
                case 1:
                case 3:
                case 5:
                case 7:
                case 9:
                    break;
                default:
                    break;
            }
        }
        endTime = System.nanoTime();
        System.out.println("Time for lookupswitch: " + (endTime - startTime) + " ns");
    }

    private void TestIfElse () {
            startTime = System.nanoTime();
            for (int i = 0; i <= 100000; i++) {
                if (i % 10 == 1 || i % 10 == 2 || i % 10 == 3 || i % 10 == 4 || i % 10 == 5
                        || i % 10 == 6 || i % 10 == 7 || i % 10 == 8 || i % 10 == 9 || i % 10 == 10) {
                } else {
                }
            }
            endTime = System.nanoTime();
            System.out.println("Time for if-else: " + (endTime - startTime) + " ns");
        }
}

위 코드 결과

tableswitch의 실행 시간: 2,862,400나노초
lookupswitch의 실행 시간: 2,255,000나노초
if-else의 실행 시간: 4,963,000나노초


성능 측정 결론 도출

  • **성능 : if-else < tableswitch < lookupswitch의**
  • lookupswitch가 tableswitch보다 약 21% 빠름
  • lookupswitch가 if-else보다 약 55% 빠름
  • tableswitch가 if-else보다 약 42% 빠름
  • 해당 시나리오에서는 이론적으로 예측한 성능차이와 같이 lookupswitch가 가장 빠른 실행 시간을 보이며, if-else는 가장 느린 실행 시간을 보인다.

정리

컴퓨터 구조에서의 Control Flow

  • 컴퓨터 구조에서 control flow를 바꾸는 것은 중요하다.
  • branch는 control flow에서 conditional instructions 즉, 코드의 흐름을 바꾸는 친구
  • jump는 control flow에서 unconditional changes 즉, 코드의 흐름을 바꾸지 않는 변화

컴퓨터 구조로 보는 if문과 switch문

  • switch문은 조건에 맞으면 goto를 통해 jump(unconditional changes)한다. 이는 코드의 흐름을 바꾸지 않고 위치만 이동하는것.
  • 그러나 If-than-else는 branch 명령어를 사용한다. 조건에 따른 동작을 하기위해 사용하는데, 이는 코드의 흐름을 바꾸는 행위이다.
    • 이는 cost가 크다.
    • flow를 바꾸어버리기 때문에 컴퓨터 입장에서 다음을 예측할 수가 없다.
    • 이는 pipedline을 방해하는 요소 중 하나이기도 하기에 성능에 영향을 미치는 것이다. (branch miss penalty)
    • cpu가 조건문을 만나면 갸우뚱🤔 해서 늦는다고 보면됨 (귀엽)

JVM로 보는 if문과 switch문

  • switch 문은 정수, 문자, 열거형 등의 조건을 각 케이스에 직접 매핑
  • if 문은 조건을 순차적으로 검사하는데, 이는 조건의 수만큼 체크가 이루어져 O(n)의 시간 복잡도를 가짐
  • 반면에 switch 문은 lookupswitch나 tableswitch 같은 특별한 JVM 명령어를 사용하여 상수 시간(complexity of O(1))에 특정 케이스로 점프

하지만,

  • JIT은 위 if문에서 나타난 branch 명령을 최적화하는 능력이 뛰어나다. JIT뿐만아니라 다른 컴파일러들도 당연히 .
  • 예를들어 우리가 매일 똑같은 학교로 등교를한다고 가정하면 처음에는 길을 헤메겠지만 다음 부터는 앞으로 갈 길을 예상하여 빠르게 갈 수 있다. 이처럼 컴퓨터 똑같이 if문을 만나면 처음에는 갸우뚱 거리지만 JIT을 통해 다음 코드의 흐름을 예측할 수 있는 것이다.
  • 이처럼 최적화 컴파일러를 통해 switch와 if문의 성능차이를 미미하게 만들 수 있다.
    • 위와같은 분기 예측(branch prediction)말고도 다양한 최적화가 존재한다.
    • 추가로 컴퓨터가 이 예측이 틀리게 되면 파이프라인에 지연이 발생게 되고, 이를 "브랜치 미스 페널티"라고 부른다.
  • 현대의 컴파일러 최적화 기술 덕분에 실제로는 두 구문 간의 성능 차이가 거의 없기때문에
  • 미미한 성능차이보다 가독성과 유지 보수성이 더 중요시 되므로 상황별로 switch문과 if문을 적절히 사용해야한다.⚖️

JIT 최적화와 'if' 문 제거에 대한 자세한 설명
'if' 문을 활용한 JVM 언어 생성 과정
JVM 해석과 컴파일에 대한 가이드


profile
권유정
인생 살자. (@yujeongkwon)
다음 포스트

[JAVA] JVM 메모리 구조와 OS 가상 메모리 구조 비교

0개의 댓글