[Java] MapN의 비트 연산 사용

최근에 기본 패키지를 뜯어보는 것에 재미가 들려서 `Map.of()` 도 확인해보다 `MapN`에 비트연산이 많이 사용된 것을 확인했다.

ImmutableCollections의 MapN

MapN의 생성자

`MapN`의 생성자는 비트연산을 정말 많이 사용한다.

MapN(Object... input) {
    if ((input.length & 1) != 0) { // implicit nullcheck of input
        throw new InternalError("length is odd");
    }
    size = input.length >> 1;
    
    // len을 짝수로 강제하는 과정
    int len = EXPAND_FACTOR * input.length;
    len = (len + 1) & ~1; // ensure table is even length
    table = new Object[len];

    // 실제 데이터 입력 생략
}

 

기본적으로 `Map`은 `<Key, Value>` 한 쌍이 되어야 하기 때문에 길이가 짝수여야 하고, 입력 받은 길이의 절반이 Map의 길이다.

 

짝수 확인

`length % 2 == 1` 대신 `length & 1 != 0`

 

논리적으로 `input.length % 2 == 1` 인 경우를 비트연산으로 바꿔서 `(input.length & 1) != 0`을 확인하고 있다.

일반적으로 현대 컴퓨터의 ALU는 비트연산을 32비트 (혹은 64비트) 단위로 한 번에 처리할 수 있다. (MBR 레지스터 크기에 따라 다름) input의 길이가 42억(2^32)이 넘어갈리는 없으니 위 비트 연산은 한 번에 처리가 가능하다. % 연산에 비해서 연산 수가 훨씬 적다.

 

나누기 2

`size = length / 2` 대신 `size = length >> 1`

 

Map의 길이인 `size`는 `input.length`의 절반이다. 역시나 `input.length / 2`를 할 수도 있지만 시프트 연산을 사용해도 된다.

 

평소에도 쓸까?

물론 실무에서 라이브러리를 개발하지 않는 이상 극한의 최적화보다는 사람이 이해하기 좋은 `length % 2 == 1` 이나 `size = input.length / 2`를 사용하는게 좋다고 생각한다.

 

그리고 중요한 점... 런타임에 JIT 컴파일러가 알아서 최적화해준다.

Note that this inspection is not relevant for modern JVMs (e. g., HotSpot or OpenJ9) because their JIT compilers will perform this optimization. It might only be useful in some embedded systems where no JIT compilation is performed.

출처: https://www.jetbrains.com/help/inspectopedia/MultiplyOrDivideByPowerOfTwo.html

 

런타임에 이런 저런 최적화를 해주는 것을 보면... Java의 JVM이 가상머신이라는 점이 단점이라기보다는 오히려 점점 더 매력적으로 보인다.

 

임베디드 시스템에서는 JIT 컴파일이 작동하지 않는 경우도 있다는 걸 보아하니 JVM 종류가 어려가지 있다는 것도 알게 됐다. JVM 종류에 대해 더 자세히 다루는 것은 주제를 너무 벗어나는 것 같으니 따로 확인해 보기를 바란다.