[Java] Array, ArrayList, LinkedList 임의의 값 탐색 속도 비교

요약

• Array > ArrayList > LinkedList 순으로 빠릅니다.
• 성능 측정에 jmh를 사용하면 측정하고자 간편하게 측정 테스트 코드를 작성할 수 있습니다.

---

n 개의 원소가 있다고 가정하였을때 Array, ArrayList, LinkedList 연산 비용은 다음과 같이 생각해 볼 수 있습니다.

그런데, i 번째 원소 탐색이 아니고 랜덤한 임의의 값을 찾는 탐색이면 어떨까요?

제 예상으로는 Array > ArrayList > LinkedList 일 것 같습니다.

• Array는 연속적인 메모리 할당으로 cache locality가 좋습니다. CPU 캐시는 한 메모리 주소에 접근할 때 그 주소뿐 아니라 해당 블록을 전부 캐시에 가져오게 되는데요, 이때 Array는 해당 블록에 있는 것들은 함께 캐싱되기 때문에 cache miss가 덜 발생합니다.
• 이에 반해 LinkedList는 비연속적인 메모리 할당을 하기 때문에 효율적인 캐싱이 어렵고 cache miss가 많이 발생하게 되어 이에 따른 오버헤드가 있습니다.
• ArrayList는 내부적으로 Array를 구현하고 있어서 Array의 탐색 속도와 거의 유사할 것으로 보이나, 간접참조하고 있기 때문에 약간의 지연이 있을 것으로 예상됩니다.

이 예상이 맞는지 검증해 보기 위해 코드를 작성해보았습니다.

Array, ArrayList, LinkedList의 랜덤 값 탐색 비용 비교

1. String 타입의 랜덤한 알파벳 문자열 배열을 생성하는 클래스를 정의합니다.

RandomArray.java

public class RandomArray {

    private static Random random = new Random();
    public static String[] makeStrs(int strLen, int arraySize){

        String[] strs= new String[arraySize];
        for(int i=0; i<arraySize; i++){
            strs[i] =makeWord(strLen);
        }
        return strs;
    }

    private static String makeWord(int strLen) {
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<strLen; i++){
            sb.append((char) (random.nextInt(26) + 97));
        }
        return sb.toString();
    }
}

2. 생성한 문자열들을 각 자료구조에 담아서, 동일한 조건으로 탐색할 때의 각 평균 시간을 비교해봅니다.

public class RandomArrayManualTest {

    private static final Random random = new Random();
    private static final int arraySize = 100_000; //배열의 길이
    private static final int strLen = 6; // 한 문자열의 길이
    private static final int times = 100_000; // 수행 횟수
    private String[] strs;
    private List<String> listStrs;
    private List<String> linkedStrs;

    private RandomArrayManualTest(String[] strs, List<String> listStrs, List<String> linkedStrs) {
        this.strs = strs;
        this.listStrs = listStrs;
        this.linkedStrs = linkedStrs;
    }

    public static RandomArrayManualTest makeRandomArrayTest() {
        String[] strs = RandomArray.makeStrs(strLen, arraySize);
        return new RandomArrayManualTest(strs, //배열의 길이와 문자열 길이를 입력받아, 랜덤한 문자열 배열 생성
            // ArrayList 객체로 복사 (new ArrayList 로 생성하지 않을 경우 copy하지 않고 참조만 하여 Array가 캐시 해놓은 것을 쓰기 때문에 성능비교가 제대로 안됨.
            new ArrayList<>(Arrays.asList(strs)),
            new LinkedList<>(Arrays.asList(strs))); // LinkedList 객체로 복사
    }

    public static void main(String[] args) {
        RandomArrayManualTest randomArrayManualTest = RandomArrayManualTest.makeRandomArrayTest();
        randomArrayManualTest.compareSearchTime();
    }

    public void compareSearchTime() {
        long arrayTotalTime = 0; // Array 탐색 시간 측정용
        long arrayListTotalTime = 0; // ArrayList 탐색 시간 측정용
        long linkedListTotalTime = 0; // LinkedList 탐색 시간 측정용

        for (int i = 0; i < times; i++) { // times 만큼 시도하고, times로 나눠 평균 시간을 측정
            // 임의의 문자열을 하나 pick. 동일한 조건으로 테스트 하기 위해 ArrayList와 LinkedList도 동일한 target을 사용한다.
            String target = strs[random.nextInt(arraySize)];

            arrayTotalTime += measureSearchInArray(target);  // Array 탐색 시간 측정

            arrayListTotalTime += measureSearchInArrayList(target); // ArrayList 탐색 시간

            linkedListTotalTime += measureSearchInLinkedList(target); // LinkedList 탐색 시간
        }

        // 각각의 평균값 계산
        System.out.println("Array times : " + (double)arrayTotalTime / times);
        System.out.println("ArrayList times : " + (double)arrayListTotalTime / times);
        System.out.println("LinkedList times : " + (double)linkedListTotalTime / times);
    }

    private long measureSearchInArray(String target) {
        long startTime = System.nanoTime();
        int j = 0;
        while (!strs[j].equals(target)) {
            j++;
        }
        return System.nanoTime() - startTime;
    }

    private long measureSearchInArrayList(String target) {
        long startTime = System.nanoTime();
        int j = 0;
        while (!listStrs.get(j).equals(target)) {
            j++;
        }
        return System.nanoTime() - startTime;
    }

    private long measureSearchInLinkedList(String target) {
        long startTime = System.nanoTime();
        linkedStrs.indexOf(target);
        return System.nanoTime() - startTime;
    }
}

이렇게만 하면 제대로 된 비교를 할 수 없습니다. JVM warm-up을 고려하지 않았기 때문입니다.

JVM warm-up에 대해서 궁금하신 분들은 다음 포스팅을 참고해주세요.
JVM Warm-up

[Java] 성능 테스트 할 땐 JVM Warm-up 하기

 

3. 사전에 동일 코드를 실행하는 수동 warm-up 작업 수행 후 속도 측정

main 메서드에 warm-up 작업을 추가합니다.

    public static void main(String[] args) {
        RandomArrayManualTest randomArrayManualTest = RandomArrayManualTest.makeRandomArrayTest();

        System.out.println("warm-up start --");
        for (int i = 0; i < 3; i++) {
            randomArrayManualTest.compareSearchTime();
            System.out.println();
        }
        System.out.println("warm-up finish --\n");

        System.out.println("measure start --");
        randomArrayManualTest.compareSearchTime();
        System.out.println("measure finish --");
    }

이제 한번 실행해 보겠습니다.

수행결과

warm-up start --
Array times : 129975.05053 ArrayList times : 166805.10206 LinkedList times : 163665.04139
Array times : 128572.66606 ArrayList times : 184162.17661 LinkedList times : 150690.30376
Array times : 130992.8485 ArrayList times : 145600.93208 LinkedList times : 162436.40015
warm-up finish -- 

measure start -- 
Array times : 130123.11445 ArrayList times : 144901.96628 LinkedList times : 161553.342
measure finish --

Array > ArrayList > LinkedList 순으로 속도가 빠른 것을 확인 할 수 있습니다.
(warm-up 타임에 중간에 예상을 벗어난 결과가 한번 발생하기도 했습니다.)

4. jmh를 활용하여 JVM warm-up 후 속도 측정

@Setup
    public void setup(){
        strs = RandomArray.makeStrs(strLen, arraySize); //배열의 길이와 문자열 길이를 입력받아, 랜덤한 문자열 배열 생성
        // ArrayList 객체로 복사 (new ArrayList 로 생성하지 않을 경우 copy하지 않고 참조만 하여 Array가 캐시 해놓은 것을 쓰기 때문에 성능비교가 제대로 안됨.
        listStrs = new ArrayList<>(Arrays.asList(strs));
        linkedStrs = new LinkedList<>(Arrays.asList(strs)); // LinkedList 객체로 복사
        target = strs[random.nextInt(arraySize)];
    }

    @Benchmark // 벤치마크 대상
    public void measureInArray() {
        int i = 0;
        while (!strs[i].equals(target)) {
            i++;
        }
    }

    @Benchmark // 벤치마크 대상
    public void measureInArrayList() {
        // listStrs.indexOf(target); // indexOf의 인자를 체크하는 비용이 추가로 발생하므로 get으로 체크
        int i = 0;
        while (!listStrs.get(i).equals(target)) {
            i++;
        }
    }

    @Benchmark // 벤치마크 대상
    public void measureInLinkedList() {
        // Array, ArrayList 처럼 get으로 체크하는 경우 매번 첫 노드부터 탐색하므로 indexOf 사용
        linkedStrs.indexOf(target);
    }

수행 결과

Benchmark                                     Mode  Cnt       Score       Error  Units
RandomArrayBenchmarkTest.measureInArray       avgt   25  125827.852 ± 68359.890  ns/op
RandomArrayBenchmarkTest.measureInArrayList   avgt   25  156598.104 ± 66299.047  ns/op
RandomArrayBenchmarkTest.measureInLinkedList  avgt   25  229503.123 ± 73539.186  ns/op

수동 warm-up을 했을 때와 동일한 Array > ArrayList > LinkedList 순으로 속도가 빠른 것을 확인 할 수 있습니다.

저는 두가지 측면에서 jmh를 활용하는 것이 좋다고 생각합니다.

• 첫번째로, 수동 warm-up을 활용하였을 때는 위에서도 알 수 있듯이 결과가 일정하지 않습니다. 보다 정교한 성능 측정을 위해선 jmh를 사용하기를 권장합니다.
• 보다 코드를 깔끔하게 짤 수 있습니다.
  • 수동 warm-up을 활용한 경우, 성능 측정을 위해 흐름을 제어하는 코드와 실제 측정하고 싶은 연산이 코드에 혼재되어 있습니다.
  • jmh를 활용하는 경우, 성능 측정을 위한 흐름 제어는 jmh에 맡기고 실제 벤치마크 하고 싶은 대상에 집중 하도록 코드를 분리하여 작성할 수 있습니다.

[전체 코드 보기]

GitHub - jerry92k/java-study-test: 자바 학습테스트

 

[참고]
Array, LinkedList cache locality