ArrayList/LinkedList 단순 순회시 For, Enhanced For , Iterator, ListIterator, Stream.forEach() 성능비교

 

 

개요

자바에서 컬렉션을 순회하는 방법은 다양하다.

 

대표적으로 for 루프, 향상된 for 루프(Enhanced For), Iterator, 그리고 ListIterator가 있다.

 

각각의 방법은 성능이나 코드의 간결성 측면에서 차이가 있는데 단순히 ~는 객체지향적이기에 사용하면 좋고, ~는 성능이 안좋아서 개선 버전이 있으니 무조건 향상된 for 문을 쓰자 를 넘어서 직접 운영중인 api 의 알고리즘을 대상으로 테스트를 해본다.

 

이번 글에서는 이러한 순회 방법들이 실제로 얼마나 성능 차이가 나는지, 어떤 상황에서 특정 방법을 사용하는 것이 유리한지에 대해 이야기를 해보려한다.

 

 

테스트 대상 특성

 

성능 테스트는 일정 관리 시스템에서 일정을 순회하며 각 일정의 타입을 계산하는 과정으로

 1. 리스트에 삽입/삭제가 이루어지지 않는다.

 2. 순서대로 순회하면서 이전값,플래그 값과 비교를 통해서 연산을 수행한다.

주어진 일정들이 특정 규칙에 따라 서로 연결되어 있는지 확인하고, 그에 따라 "START", "MIDDLE", "END", "SINGLE"과 같은 타입을 할당한다.

 

자세한건 아래 글을 읽어보자

영업시간 디자인 변경에 대응한 리팩토링 일지 [1] (feat: 연결된 일정 구현하기)

 

 

테스트 목적

이러한 작업은 일정의 연속성을 검사하는 논리를 포함하고 있기 때문에, 어떤 순회 방법이 더 효율적인지에 대한 테스트가 필요했다.

 

 

테스트 Case

테스트는 ArrayList와 LinkedList 두 가지 리스트 구조를 사용하여 진행되었으며, 각 구조에 따라서 아래 다섯 가지 순회 방식을 비교했다

1. 일반 for 루프: 인덱스를 사용하여 리스트의 각 요소에 직접 접근
2. 향상된 for 루프(Enhanced For): Iterator를 내부적으로 사용하지만, JIT 컴파일러에 의해 최적화 되어있다.
3. Iterator: 메서드를 통해 리스트를 순차적으로 탐색.
4. ListIterator: Iterator의 확장된 버전으로, 양방향 탐색 및 추가적인 메서드들을 제공.
5. Stream: Stream.forEach()를 사용하였고, 플래그 값과 비교를 했기에 병렬 처리는 시도하지않았다.



테스트 조건

작은 데이터셋과 큰 데이터셋 모두에서 이들 방법의 성능을 비교했으며, 리스트 구조에 따라 성능이 어떻게 달라지는지에 대한 실험도 함께 진행했다.

---

데이터 생성 ;실제 유저의 사용 패턴을 기반

 

1. 날짜의 비연속적 증가

유저가 일정을 입력할 때, 날짜가 반드시 연속적일 필요는 없다. 어떤 일정은 연속된 날에 설정될 수 있지만, 일부 일정은 며칠을 건너뛰고 추가될 수 있다.

 

 

이를 반영하기 위하여 각 일정의 날짜는 1일 또는 2일씩 랜덤하게 증가시킨다.
유저가 일정 관리 시스템에서 연속되는, 연속되지 않는 일정을 추가하는 일반적인 사용 패턴을 따라했다.

int daysToAdd = RANDOM.nextInt(2) + 1; // 1 또는 2일 증가
currentDate = currentDate.plusDays(daysToAdd);

 

 

 

2. 유사한 유형(Type)과 설명(Description) 유지

일정 관리 시스템에서 같은 유형의 일정을 연속해서 추가하는 경우 BlockType이 달라진다.

 

이를 반영하기 위하여 일정의 유형(Type)과 설명(Description)은 30% 확률로 이전 일정과 동일하게 설정을 하여 유저가 반복적인 일정을 추가하는 패턴을 따라했다.

 

if (previousType != null && previousDescription != null && RANDOM.nextInt(100) < 30) {
    businessSchedules.add(new BusinessSchedule(previousType, previousDescription, currentDate));
}

 

 

 

3. 새로운 유형(Type)과 설명(Description) 생성

다른 일정을 추가하는 경우도 고려해서 나머지 70%의 경우, 새로운 유형(Type)과 설명(Description)이 무작위로 생성하여 패턴을 따라했다.

else {
    String newType = "Type" + RANDOM.nextInt(3); // Type0, Type1, Type2
    String newDescription = "Description" + RANDOM.nextInt(5); // Description0 ~ Description4
    businessSchedules.add(new BusinessSchedule(newType, newDescription, currentDate));

    // 새로운 값을 이전 값으로 업데이트
    previousType = newType;
    previousDescription = newDescription;
}

 

 

 

 

매주 휴일이 있기에 Single 의 개수가 압도적으로 많다. 또한 Start-Mid-End 세트를 고려하면 단일 휴일 vs 연속 휴일의 비율이 약 1:5~ 정도인데

이는 1.5달에 한번씩 휴일이 있는것으로 적절한 튜닝이었다고 생각한다.

---

 

5가지 순회 방식의 구현

 

자세한 코드는 개인 깃에 올려두었다.

 

performance_test/src/main/java/com/performance/test/iteratorVsForloop at main · ChoMinGi/performance_test

 

 

1. Iterator를 사용하는 메서드

public List<BusinessScheduleWithBlockTypeDTO> createScheduleDTOsUsingIterator(List<BusinessSchedule> businessSchedules) {
    Iterator<BusinessSchedule> iterator = businessSchedules.iterator();

    while (iterator.hasNext()) {
        BusinessSchedule current = iterator.next();
        // 이전 요소와 비교하여 BlockType 결정 및 추가
        // 상태 업데이트
        previous = current;
    }
    // 마지막 요소 처리
    return scheduleDTOs;
}

 

• Iterator를 사용하여 컬렉션의 요소를 순차적으로 탐색
• 각 요소를 탐색하면서 이전 요소와 비교하여 BlockType을 결정하고, DTO 리스트에 추가

 

 

2. For 루프를 사용하는 메서드

 

public List<BusinessScheduleWithBlockTypeDTO> createScheduleDTOsUsingForLoop(List<BusinessSchedule> businessSchedules) {
    for (int i = 1; i < businessSchedules.size(); i++) {
        BusinessSchedule next = businessSchedules.get(i);
        // 이전 요소와 비교하여 BlockType 결정 및 추가
        // 상태 업데이트
        current = next;
    }
    // 마지막 요소 처리
    return scheduleDTOs;
}

• 인덱스를 기반으로 한 일반 for 루프를 사용하여 요소를 탐색
• 각 요소에 인덱스를 통해 접근하며, 이전 요소와 비교하여 BlockType을 결정

 

 

3. 향상된 for 문을 사용하는 메서드

 

public List<BusinessScheduleWithBlockTypeDTO> createScheduleDTOsUsingEnhancedForLoop(List<BusinessSchedule> businessSchedules) {
    for (BusinessSchedule current : businessSchedules) {
        // 이전 요소와 비교하여 BlockType 결정 및 추가
        // 상태 업데이트
        previous = current;
    }
    // 마지막 요소 처리
    return scheduleDTOs;
}

• 향상된 for 문(Enhanced for loop)을 사용하여 컬렉션의 각 요소를 순차적으로 탐색
• 이전 요소와 현재 요소를 비교하여 BlockType을 결정

 

4. ListIterator를 사용하는 메서드

 

public List<BusinessScheduleWithBlockTypeDTO> createScheduleDTOsUsingListIterator(List<BusinessSchedule> businessSchedules) {
    ListIterator<BusinessSchedule> iterator = businessSchedules.listIterator();

    while (iterator.hasNext()) {
        BusinessSchedule current = iterator.next();
        // 이전 요소와 비교하여 BlockType 결정 및 추가
        // 상태 업데이트
        previous = current;
    }
    // 마지막 요소 처리
    return scheduleDTOs;
}

• ListIterator를 사용하여 리스트의 요소를 순차적으로 탐색
•  순방향 탐색만 사용하고 있고 이전 요소와 비교하여 BlockType을 결정

 

 

5. Stream.forEach를 사용하는 메서드

 

public List<BusinessScheduleWithBlockTypeDTO> createScheduleDTOsUsingStream(List<BusinessSchedule> businessSchedules) {
    AtomicReference<BusinessSchedule> previousRef = new AtomicReference<>(null);
    AtomicReference<Boolean> isPreviousLinkedRef = new AtomicReference<>(false);

    businessSchedules.stream().forEach(current -> {
        BusinessSchedule previous = previousRef.get();
        // 이전 요소와 비교하여 BlockType 결정 및 추가
        // 상태 업데이트
        previousRef.set(current);
    });

    // 마지막 요소 처리
    return scheduleDTOs;
}

• 스트림 API의 forEach 메서드를 사용하여 컬렉션의 요소를 순차적으로 처리
• 상태(previous, isPreviousLinked)를 AtomicReference로 관리하여, 람다 표현식 내부에서 변경할 수 있도록 한다.
• 상태가 존재하기 때문에 장점인 병렬처리를 수행하지 못한다.

 

---

 

성능 테스트 준비

 

Runtime 내의 gc() 메서드를 이용해 각 메서드 별로 사용하고 있는 메모리를 저장하고 StopWatch 를 이용해 각 로직별로 걸린 시간을 측정해보았다.

 

메모리 측정 로직

// 시작 메모리 측정
long beforeMemory = runtime.totalMemory() - runtime.freeMemory();

stopWatch.start(taskName);
task.run();
stopWatch.stop();

// 끝난 후 메모리 측정
long afterMemory = runtime.totalMemory() - runtime.freeMemory();

long memoryUsed = afterMemory - beforeMemory;

 

 

 시간 측정

StopWatch 의 prettyPrint()를 이용하여 아주 간단하게 구현했다.

public void testPerformance() {
    List<BusinessSchedule> businessScheduleList = createTestData();

    StopWatch stopWatch = new StopWatch("Performance Testing");

    // ArrayList 테스트
    measureMemoryAndTime("ArrayList Iterator", () -> runTestWithIterator(new ArrayList<>(businessScheduleList)), stopWatch);
    measureMemoryAndTime("ArrayList For Loop", () -> runTestWithForLoop(new ArrayList<>(businessScheduleList)), stopWatch);
    measureMemoryAndTime("ArrayList Enhanced For Loop", () -> runTestWithEnhancedForLoop(new ArrayList<>(businessScheduleList)), stopWatch);
    measureMemoryAndTime("ArrayList ListIterator", () -> runTestWithListIterator(new ArrayList<>(businessScheduleList)), stopWatch);
    measureMemoryAndTime("ArrayList Stream", () -> runTestWithStream(new ArrayList<>(businessScheduleList)), stopWatch);

    // LinkedList 테스트
    measureMemoryAndTime("LinkedList Iterator", () -> runTestWithIterator(new LinkedList<>(businessScheduleList)), stopWatch);
    measureMemoryAndTime("LinkedList For Loop", () -> runTestWithForLoop(new LinkedList<>(businessScheduleList)), stopWatch);
    measureMemoryAndTime("LinkedList Enhanced For Loop", () -> runTestWithEnhancedForLoop(new LinkedList<>(businessScheduleList)), stopWatch);
    measureMemoryAndTime("LinkedList ListIterator", () -> runTestWithListIterator(new LinkedList<>(businessScheduleList)), stopWatch);
    measureMemoryAndTime("LinkedList Stream", () -> runTestWithStream(new LinkedList<>(businessScheduleList)), stopWatch);

    System.out.println(stopWatch.prettyPrint());

    calculateAndPrintBlockTypeDistribution(businessScheduleList);
}

 

---

 

 

 

테스트 결과

 

메모리 영역 (좌측부터 리스트 요소 개수 50000, 10000, 1000, 100)

50000번 (좌측) / 10000번 (우측)

1000번 (좌측) / 100번 (우측)

메모리의 경우에는 순회 방식과는 차이가 없기에 ArrayList, LinkedList 와의 비교가 될것 같다.

• ArrayList의 메모리 사용량은 리스트 요소 개수에 따라 선형적으로 증가하며, 순회 방식에 따라 차이가 거의 없다.
  •  ArrayList가 내부적으로 배열을 사용하여 고정된 크기의 메모리를 할당하기 때문에 발생하는 현상
• LinkedList가 ArrayList에 비해서 더 많은 메모리를 사용하는 이유?
  • LinkedList가 각 노드가 양방향 링크를 포함하는 노드를 가지고 있고 추가적인 포인터를 저장하기 위해 더 많은 메모리를 차지

 

 걸리는 시간

50000번 (좌측) / 10000번 (우측)

1000번 (좌측) / 100번 (우측)

 

시간은 꽤나 일관성있고 특성에 맞추어서 결과가 나와서 분석을 해볼수있을것 같다.

 

우선 LinkedList에서 크기가 커질수록 클래식한 For 문의 성능이 급격하게 나빠졌고 병렬순회를 사용하지 못해서 두 리스트 형식에서 모두 안좋은 성능이 나올것이라고 예상하던 Stream이 ArrayList에서는 성능이 안좋았지만 예상외로 큰 규모의 LinkedList 에서 좋은 성능을 보여줬다.

 

1. Iterator

• Iterator는 next() 메서드를 통해 리스트를 순차적으로 순회하는 특성이 있다.
• ArrayList에서는 내부 배열에서 순차적으로 요소를 읽어오므로 효율적으로 나타났다. 하지만 For Loop 에 비해서 추가적인 메서드 구현이 존재하기에 오버헤드는 존재한다.
• LinkedList에서도 Iterator는 요소를 순차적으로 접근하기 때문에 인덱스 기반 접근에 비해 상대적으로 효율적이다. 하지만 여전히 각 요소를 탐색할 때 다음 노드로 이동하는 추가적인 작업이 필요하기에 작은 크기에서는 무척 안좋은 성능을 가지지만 크기가 커질수록 좋은 성능을 보인다.

2. For Loop

• For Loop는 인덱스를 이용하여 리스트의 요소에 접근한다.
• ArrayList의 경우 인덱스를 통한 접근이 O(1)의 시간 복잡도를 가지기 때문에, ArrayList에서 For Loop의 성능이 가장 좋다.
• LinkedList의 경우, For Loop의 성능이 매우 떨어진다. 인덱스를 이용해 특정 요소에 접근하려면, 첫 번째 노드부터 차례대로 순회해야 하기에 요소의 개수가 많아질수록 인덱스를 기반으로 한 접근은 O(n)의 시간 복잡도가 요소마다 발생한다.
  이로 인해, 특히 큰 리스트일수록 상당한 오버헤드와 시간지연이 두드러졌다.

3. Enhanced For Loop

• Enhanced For Loop는 내부적으로 Iterator를 사용하여 리스트를 순회한다.
• 따라서 ArrayList와 LinkedList 모두에서 Iterator와 비슷한 성능을 보인다.

4. ListIterator

• ListIterator는 Iterator의 확장하여 구현한 버전으로, 리스트를 양방향으로 순회할 수 있는 기능을 제공한다. Iterator와 비슷한 성능을 보이지만 역시나 추가적인 메서드 구현으로 인해서 Iterator 에 비해서 오버헤드가 발생한다.
• LinkedList의 경우, ListIterator는 기본적인 Iterator와 유사한 성능을 제공하지만 양방향 순회를 지원하기 때문에 이전 노드에 대한 정보를 좀더 빠르게 가져올수 있어서 빠르지 않았나 추측한다.

5. Stream

• Stream API를 사용한 순회는 내부적으로 Spliterator를 사용하여 데이터를 순회한다. (분할 가능 반복자)
• ArrayList에서 Stream을 사용하는 것은 내부 구조를 효율적으로 활용하기 때문에 크기가 큰 데이터를 처리할 때 병렬 처리를 사용하지 않더라도 유리하다고 한다.
• LinkedList의 경우,LinkedList의 요소 접근 방식과 Stream의 순차 처리 방식이 잘 맞지 않기 때문에 요소가 많아질수록 처리 시간이 길어질 수 있다.

Spliterator (Java Platform SE 8 )