java 박싱 언박싱과 오버헤드에 대한 이야기

 백준 1325번은 c,c++로 풀면 쉽게 풀리는 dfs, bfs 문제 중 하나입니다. 그런데 Java로 풀면 시간이 빡빡한데요. 그 이유 중 하나는 박싱, 언박싱에 의한 객체 생성 때문입니다. 이에 대해서 아직 익숙하지 않으시다면, 이 포스트를 보고 오시는 것도 좋습니다.

 

---

 통과를 하시고 나서, java로 통과한 코드 중에서 1등과 2등 코드의 차이를 보면 대충 3초 가량이 나는 것을 볼 수 있습니다. 이 두 코드를 보시면, 하나는 primitive type 배열을 썼고, 다른 하나는 그렇지 않았음을 볼 수 있는데요. 3초 차이라니. O(nm) 복잡도에서, 아슬아슬하게 통과할 복잡도에서, 3초면 상당히 큽니다.

 

 그 원인 중 하나가 필요 없는 객체 생성이라 했으니, trace를 해 보겠습니다.

 

 

 jdk 8 기준으로는, VM options에 -XX:+PrintGCDatails 옵션을 주면, gc log를 찍게 됩니다. 다른 옵션이 없으므로, 콘솔에다가 찍겠네요.

 

 

 다음에 Integer 배열을 선언하였습니다. int와 같은 듯 보이지만, 엄연히 Integer는 객체입니다. int를 boxing한 객체입니다.

 

 

 프로그램을 실행해 보면, GC log가 꽤 찍히는 것을 알 수 있습니다. 이는 객체가 생성이 되고, 어느 순간에 도달 가능하지 않게 되었기 때문입니다. object가 생성되었고, 어느 순간에 gc가 돌았다는 것이 중요합니다. 어디서 생성되었을까요?

 

 

 

 먼저 9번째 줄을 보면, arr[j]에 int형 값을 집어넣음을 볼 수 있습니다. arr[j]는 Integer 객체를 가리킬 테고, 우변은 int일 텐데. 이 줄에서 Boxing이 일어나는데요. Integer의 valueOf를 호출하게 됩니다.

 

 

 이 코드를 보면, i가 일정 범위 내에 있으면 cache된 객체를 돌려주고, 그렇지 않으면 새로 생성하는 것을 알 수 있습니다. 어찌 되었던, 새로 생성이 되었다는 것이 중요합니다. 이를 boxing이라고 합니다.

 

 

 다음에 이 부분을 보면, Integer에다가 M을 나누는데요. 이 때, intValue 값이 호출됩니다. 객체가 primitive type의 값으로 변하고 있습니다. 이를 unboxing이라고 합니다.

 

 

 당연하게도, arr[j]에 대한 intValue입니다. 이것이 unboxing이 되면서 int 값으로 바뀌어 버립니다. 그러면 M으로 나눈 나머지 또한 구할 수 있습니다. for loop 안에 있는 것을 정리해 보면 boxing을 하고, 그걸 또 unboxing 하는 작업을 반복합니다.

 

 

 이런 박스를 하나 만듭니다.

 

 

 그리고 바로 값을 꺼냈습니다. 박스는 아무런 일도 하지 않았습니다.

 

---

 primitive type으로 바꾸면 어떨까요?

 

 

 gc log가 출력되지 않습니다. object가 수억 회 가량 생성이 되지 않았기 때문입니다. 시간을 비교해 보면 어떨까요?

 

 

  7.64초가 걸렸습니다.

 

 

 Integer 배열을 써서 Boxing, unBoxing이 10억회 가량 일어났을 때 8.76초가 걸렸습니다. 유의미한 차이를 보여줍니다. 1325번은 인접 리스트를 표현하기 위해서 ArrayList를 써야 할 듯 한데요. 이것은 기본 타입을 받지 못하고. 맞습니다. 그런데, 우리는 전처리를 해 놓는다면 해당 노드가 몇 개의 노드와 연결이 되어 있는지를 알 수 있습니다. 크기를 아는 경우에는 배열을 써도 된다는 것이 핵심입니다.