제리의 배움 기록
[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
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에 맡기고 실제 벤치마크 하고 싶은 대상에 집중 하도록 코드를 분리하여 작성할 수 있습니다.
'자바' 카테고리의 다른 글
[Java] 성능 테스트 할 땐 JVM Warm-up 하기 (0) | 2022.01.14 |
---|---|
[Java] JVM 클래스 로더 (0) | 2022.01.13 |
[Java] 프로세스와 스레드 - <1> JVM 메모리 관점에서 분석 (0) | 2021.12.15 |
[Java] 프로세스와 스레드 - <2> LifeCycle 비교 (0) | 2021.12.14 |
[Java] Compiling Switches : tableswitch 와 lookupswitch (0) | 2021.12.07 |
Comments