개요
프로젝트를 하면서 Call to 'list.containsAll(collection)' may have poor performance 문제가 발생하였는데, 원인이 무엇이고 개선할 수 있는 방법은 무엇인지 공유하고자 합니다.
containsAll 메서드는?
먼저, containsAll 메서드는 자바의 컬렉션 (Collection)에 내장되어 있는 메서드입니다.
- 메서드를 호출한 컬렉션이 지정된 컬렉션의 모든 원소를 포함하고 있다면 true를 반환합니다.
- 파라미터 c: 컬렉션에 포함되어 있는지 여부를 확인할 컬렉션
- 반환: 컬렉션이 지정된 컬렉션의 모든 원소를 포함하고 있을 경우 true를 반환
- 반환되는 예외
- ClassCastException: 지정된 컬렉션이 가지고 있는 하나 이상의 원소가 메서드를 호출한 컬렉션과 적합하지 않은 관계가 될 경우 발생
- NullPointerException: 지정된 컬렉션이 하나 이상의 null 원소를 포함하면서 메서드를 호출한 컬렉션이 null 원소를 허용하지 않거나, 또는 지정된 컬렉션이 null인 경우 발생
이렇듯 containsAll 메서드는 말 그대로 모든 원소를 포함 (contain)하고 있는지 검사하는 간단한 메서드입니다.
발생한 문제 상황은?
프로젝트에서 발생한 문제는 아래 상황이었습니다.
// import, 어노테이션 생략
public class MemberSurveyService {
private final MemberSurveyService memberSurveyService;
private final SurveyRepository surveyRepository;
public void submitSurvey(final Long memberId, final List<SurveySubmitRequest> requests) {
validateIsContainsAllRequiredSurveys(requests);
requests.forEach(request -> submitEachSurvey(memberId, request));
}
private void validateIsContainsAllRequiredSurveys(final List<SurveySubmitRequest> requests) {
List<Long> requiredSurveyIds = extractRequiredSurveyIds(); // 필수 과목 ID 목록 추출 내부 코드
List<Long> submittedSurveyIds = extractSubmittedSurveyIds(requests); // 입력한 ID 목록 추출 내부 코드
// IntelliJ 경고 발생 위치
if (!submittedSurveyIds.containsAll(requiredSurveyIds)) {
throw new RequiredSurveyNotSubmittedException();
}
}
...
}
- Survey는 연애 모의고사 (연애 설문)을 의미합니다. 필수, 선택 과목으로 구분되어 있습니다.
- 회원은 연애고사 데이터를 제출할 때 과목 id를 포함하여 제출합니다.
- 이때, 제출한 과목 ID 목록은 필수 과목 말고도 선택 과목들을 포함할 수 있기 때문에 필수 ID 목록보다 더 많이 있을 수 있습니다. 따라서 제출한 과목 ID 목록이 필수 과목 ID 목록을 전부 포함하고 있지 않다면 예외를 발생하도록 설계하였습니다.
- List<Long>을 반환하는 메서드들은 마지막에 toList()를 붙여서 List 타입으로 반환하도록 하였는데, 이때 자바 내부 코드를 보면 Collections.unmodifiableList를 반환합니다. 후술 할 AbstractImmutableList와 관계되어 있으니 이 점 유의해 주시기 바랍니다.
containsAll의 내부 원리
Collection은 인터페이스이기 때문에 이를 구현하는 구현체가 필요합니다.
자바 공식 문서를 보면 Collection의 골격 구현체는 AbstractCollection 추상 클래스라고 되어 있습니다. 그렇다면 AbstractCollection에서 구현한 containsAll의 내부 코드를 살펴보겠습니다.
구현 내용을 보시면 매우 간단하게 되어 있습니다. 파라미터로 제공된 또 다른 컬렉션 c의 각 원소에 대해 메서드를 호출한 컬렉션이 해당 원소를 하나라도 가지고 있지 않으면 false를 반환하고, 그 경우가 아니라면 (전부 가지고 있다면) true를 반환하고 있습니다.
contains의 내부 원리
그러면 저기에 있는 contains 메서드는 어떤 것을 사용하고 있는 걸까요? (Collection에서는 추상 메서드로만 정의되어 있습니다.)
동일하게 AbstractCollection의 contains를 호출하는 줄 알았으나, 디버깅과 자바 문서를 참고하면 AbstractImmutableList에서 다루고 있음을 보실 수 있습니다. (반환 타입으로 List를 받도록 하였으므로 이 클래스가 구현체로 선정됩니다.
구조 관계로는 AbstractImmutableList가 List 인터페이스의 contains 메서드를 구현하기에 AbstractImmutableList의 contains 메서드를 수행하게 됩니다.
indexOf의 원리
이제 indexOf를 살펴보면 됩니다.
테스트 디버깅을 계속하다 보면 넘긴 List가 ImmutableCollections 중 ListN 클래스라는 것을 확인할 수 있고, 이 ListN 클래스는 위에서 contains 메서드를 가지고 있던 AbstractImmutableList를 상속받으므로, 결과적으로 AbstractImmutableList의 부모인 List 인터페이스에 위치한 indexOf 메서드를 구현하게 됩니다.
참고로, 진행한 테스트 코드는 아래와 같습니다.
@Test
void 필수_과목을_응시하지_않으면_예외가_발생한다() {
// given
List<SurveySubmitRequest> requests = 선택_과목_질문_두개_제출_요청(); // 입력에는 id 2만 제출
surveyRepository.save(연애고사_필수_과목_질문_두개씩()); // 필수 과목 id는 1
surveyRepository.save(연애고사_선택_과목_질문_두개씩()); // 선택 과목 id는 2
// when & then
assertThatThrownBy(() -> memberSurveyService.submitSurvey(memberId, requests))
.isInstanceOf(RequiredSurveyNotSubmittedException.class);
}
잠깐 정리!
클래스가 여러 개 나와서 헷갈리실 수도 있는데요, 잠깐 정리하자면 클래스 간의 관계는 다음과 같습니다.
- 문제 상황에 따르면, toList 메서드를 호출하여 만들어진 List<Long> 등의 List 타입은 ImmutableCollections의 ListN 타입으로 반환됩니다. (주어진 데이터)
- 모든 컬렉션은 Collection 인터페이스와 관계있습니다. contains, containsAll 메서드가 처음 등장합니다.
- List의 경우 Collection 인터페이스로부터 상속받은 인터페이스이며, indexOf 추상 메서드를 가집니다.
- AbstractCollection은 Collection의 골격 구현체입니다. (공식 문서) contains, containsAll 메서드를 구현합니다.
- ImmutableCollections 안에는 AbstractImmutableCollection, 그리고 이를 상속받는 AbstractImmutableList, 또 이를 상속받는 ListN 클래스가 있으며, ListN 클래스에서 List 인터페이스에 있던 indexOf 메서드를 구현합니다.
- AbstractImmutableList에서 contains 메서드를 재정의하므로 결과적으로 사용하게 되는 contains 메서드는 AbstractImmutableList의 메서드입니다.
그림으로 나타내면 다음과 같은 관계를 가집니다.
- 넘겨받은 컬렉션의 각 원소마다 contains를 호출합니다.
- 각 원소는 indexOf 메서드를 탑니다.
- 메서드를 호출한 컬렉션의 원소들 (elements) 중 원소와 같은 게 최종적으로 전달되지 않을 경우 -1을 반환합니다.
- 따라서, containsAll 메서드는 한 원소라도 -1이 된 경우라면 false, 그 반대의 경우에는 true가 반환됩니다.
최악의 경우..
자, 이제 눈치가 빠르신 분들은 인텔리제이가 경고 알림을 주는 이유를 파악하셨을 겁니다.
흔히 시간 복잡도라고 하죠. 컴퓨터는 평균적으로 1초에 1억 번 정도의 연산을 수행할 수 있습니다. 그리고 우리가 시간 복잡도를 계산할 때는 for문 등 반복문을 통해 유추하곤 합니다.
지금까지의 과정을 보면, for문이 총 두 번 호출됨을 알 수 있습니다.
첫 번째는 containsAll에서 인자로 주어진 컬렉션의 원소 개수, 두 번째는 indexOf에서 호출한 컬렉션의 원소 개수가 됩니다. 각각 N, M개라고 가정한다면, 결과적으로 list.containsAll(list)의 시간 복잡도는 O(N * M)이 나오게 됩니다.
만약 인자로 주어진 컬렉션 (비교할 컬렉션)의 원소 개수가 1억 개, 메서드를 호출할 컬렉션의 원소 개수가 1억 개라고 한다면 시간 복잡도는 O(100,000,000 * 100,000,000) = O(10,000,000,000,000,000)으로, 약 1경으로 1초에 1억 번을 수행한다고 가정하면 1억 (초) / 60 (분으로 만들기) / 60 (시간으로 만들기) / 24 (일로 만들기) = 약 1,157.407.. 일이 걸리게 됩니다.
물론 현실적으로 생각해 봤을 때 과목이 1억 개씩 입력되고 저장된 경우는 거의 희박할 것입니다. 그렇지만 이런 부분에서 최대한 시간 복잡도를 개선한다면, 사용자에게 응답을 반환해 주는 대기 시간이 최소화되지 않을까요? 그러면 이 점을 개선해 보겠습니다.
HashSet 적용
인텔리제이의 경고를 보면 HashSet을 적용하면 된다고 나와있습니다.
HashSet은 자주 접하셨을 자료구조일 텐데요, Set (집합 - 중복 제거)과 Hash (해시)의 특징을 적용한 자료구조입니다.
인텔리제이의 추천대로 코드를 수정해 보면 아래와 같습니다. (물론 더 나은 코드를 위해 변수를 추출하는 등의 작업을 진행할 수도 있습니다.)
Set
Set 인터페이스는 List와 같이 Collection 인터페이스를 상속받고, contains 추상 메서드와 containsAll 추상 메서드가 있습니다.
관련 자료를 정리하면 아래와 같이 구성됩니다. (Set 관련 부분은 간단하게 말씀드리겠습니다.)
- 인자 컬렉션의 각 원소마다 contains를 호출합니다.
- 호출한 HashSet에서 contains를 검사할 때는 내부적으로 가지고 있는 HashMap에 원소 키를 가지고 있는지를 이용하여 판단합니다. 해시 특성상 O(1)의 시간복잡도를 가집니다. (해시는 다른 글에서 추후 다루겠습니다.)
해시의 장점을 활용하여 기존 O(N * M)에서 O(N)의 시간 복잡도로 크게 향상되었습니다. 최악의 케이스에서는 1경 번의 연산이 걸렸는데, 이제는 최악의 케이스에서도 1억 번의 연산이 걸리게 된 것입니다.
간단한 성능 비교하기
VisualVM을 이용하여 List의 경우와 HashSet의 경우를 간단히 비교해 보겠습니다. 최악의 케이스처럼 1억 개씩 저장하면 Out Of Memory 현상이 발생하기에, 사이즈를 조금 줄였습니다.
List (ArrayList)
실습 코드
데이터를 매우 많이 넣어놔야 하기 때문에 ArrayList를 활용하였습니다.
public class Main {
public static void main(String[] args) {
long beforeTime = System.currentTimeMillis();
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 1_000_000; i++) {
list.add(i);
}
List<Integer> another = new ArrayList<>();
for (int i = 0; i < 500_000; i++) {
another.add(i);
}
boolean isAllContains = list.containsAll(another);
System.out.println("isAllContains = " + isAllContains);
long afterTime = System.currentTimeMillis();
long secDiffTime = (afterTime - beforeTime) / 1000;
System.out.println("시간 (초): " + secDiffTime);
}
}
결과
- CPU의 최고 사용률은 16.9%가 나왔습니다.
- 알고리즘은 CPU 사용률에 영향을 미칩니다.
- 측정 시간은 106초가 나왔습니다. 원래 이론적으로라면 100만 * 50만 / 1억 = 5,000초가 나와야 하지만, M1 맥 특성상 더욱 빠르게 설계되어 이렇게 나온 것 같습니다.
HashSet
실습 코드
다음은 HashSet 기반의 코드입니다.
public class Main {
public static void main(String[] args) throws InterruptedException {
long beforeTime = System.currentTimeMillis();
Set<Integer> set = new HashSet<>();
for (int i = 0; i < 1_000_000; i++) {
set.add(i);
}
Set<Integer> another = new HashSet<>();
for (int i = 0; i < 500_000; i++) {
another.add(i);
}
boolean isAllContains = set.containsAll(another);
System.out.println("isAllContains = " + isAllContains);
long afterTime = System.currentTimeMillis();
long secDiffTime = (afterTime - beforeTime) / 1000;
System.out.println("시간 (초): " + secDiffTime);
Threa.sleep(10000);
}
}
결과
- 매우 빨라서 측정이 거의 불가능했습니다. 그래서 실행이 끝난 후 Thread.sleep을 통해 잠금을 걸어뒀습니다.
- CPU의 최고 사용률은 1.0%이 나왔습니다. HashSet 방식은 메서드를 비교할 컬렉션의 원소 개수에만 영향을 받기 때문에 O(50만) = 1초 미만으로 나오는 것입니다.
- 따라서 측정 시간은 0초가 나왔습니다.
느낀 점
단순히 HashSet을 이용하여 시간 복잡도를 수정하면 되겠지라는 생각으로 넘어갈 수도 있었으나, 근본적인 이유를 파헤치기 위해 작성하다 보니 뜻밖으로 자바의 컬렉션 프레임워크에 대해 더 깊게 이해할 수 있었습니다.
더불어 알고리즘적으로만 공부했던 시간 복잡도를 비즈니스적으로 생각해 보는 계기가 되기도 했고 (서비스의 잠재 장애 시간을 단축시킬 수 있는 것 등), 시간이 매우 빠르게 끝날 경우에 분석을 하고 싶다면 Thread.sleep을 걸면 된다는 점도 배웠습니다.
혹시라도 틀린 점이 있다면 언제든지 말씀해 주시면 감사하겠습니다!
Reference
- Java docs - AbstractCollection
- Java docs - AbstractImmutableList
- 해시 - 골든래빗 (참고하시면 좋을 것 같아 공유합니다.)
