이번 글에서는 흥미로운 문제 하나를 살펴보겠습니다. 아래에 제시된 두 개의 코드 조각은 모두 이중 중첩 루프로 구성되어 있습니다. 과연 어느 쪽이 더 빠르게 실행될까요? 단, 컴파일러가 코드를 최적화하지 않는다는 조건을 전제로 합니다.
코드 조각 1
for(int i = 0; i < 10; i++){
for(int j = 0; j<100; j++){
//code
}
}코드 조각 2
for(int i = 0; i < 100; i++){
for(int j = 0; j<10; j++){
//code
}
}두 코드 모두 실제 연산 본문은 동일하게 10,000번(10 × 100) 실행됩니다. 겉보기에는 성능 차이가 없어 보일 수 있습니다. 그러나 자세히 들여다보면 두 번째 코드가 첫 번째 코드보다 더 많은 부가 작업을 수행한다는 사실을 알 수 있습니다.
핵심은 내부 루프가 반복되는 횟수입니다. 루프가 한 번 시작될 때마다 초기화, 조건 검사, 증감 연산이라는 오버헤드가 발생하기 때문입니다.
- 첫 번째 코드에서는 외부 루프가 10번 도는 동안 내부 루프가 매번 새로 시작됩니다. 즉, 내부 루프의 초기화·조건 검사·증감 연산은 총 10번만 수행됩니다.
- 반면 두 번째 코드에서는 외부 루프가 100번 도는 동안 내부 루프가 100번 새로 시작됩니다. 따라서 같은 오버헤드 작업이 무려 100번이나 반복됩니다.
결과적으로 두 번째 코드는 첫 번째 코드보다 불필요한 루프 관리 비용이 훨씬 크기 때문에 실행 시간이 더 오래 걸립니다. 이처럼 반복 횟수가 같더라도 루프 구조를 어떻게 배치하느냐에 따라 성능이 달라질 수 있다는 점이 이 퍼즐의 핵심입니다. 일반적으로 반복 횟수가 적은 루프를 바깥에, 많은 루프를 안쪽에 배치하는 것이 유리합니다.