Kotlin/JVM Vector, ArrayList, Mutex 수행 시간

결과

• 싱글 스레드 환경에서 Vector는 ArrayList 대비 약 6배의 시간이 소요된다.
• 멀티 스레드 환경에서 Vector는 synchronized ArrayList 대비 약 1.3배의 시간이 소요된다.
• 멀티 스레드 환경에서 synchronized ArrayList은 Mutex.withLock ArrayList 대비 약 2.2배의 시간이 소요된다.
• Vector 대신 ArrayList를 사용하려면 반드시 원자적인 연산만 수행해야 한다.

 

본문

Java에는 배열을 사용한 List 구현체로 Vector와 ArrayList가 있다.

 

Vector는 모든 add, get, set이 synchronized로 작동하는 점이 ArrayList와 다르다.

Vector와 ArrayList와 충분한 capacity만 확보되어 있다면 random access와 \(O(1)\)의 시간복잡도로 tail insert가 가능하다.

Vector는 모든 동작에 synchronized 키워드가 사용되어 속도에 영향이 있다고 한다. 대부분의 경우에서 모든 동작이 synchronized할 이유는 없다고 한다.

Vector synchronizes on each individual operation. That's almost never what you want to do.

Stack OverFlow: Why is Java Vector (and Stack) class considered obsolete or deprecated?

 

  예를 들어 더 이상 수정이 발생하지 않는 상황에서 읽기 접근만 존재한다면 각 thread가 모두 비동기적으로 접근하는 편이 훨씬 유리할 것이다. 하지만 지속적으로 내용 수정이 수행되는 상황에서 읽기가 수행되어야 한다면 적절한 동기화가 필요하므로 일일히 synchronized 블럭을 선언하는 것도 번거로울 뿐더러 교착 상태의 위험까지 수반될 수 있다.

 

  테스트는 두 방법으로 수행된다.

1. 싱글스레드
   - N=데이터의 수
   - 각 자료구조에 N번 add의 시간을 측정한다.
   - N개의 데이터가 삽입되어 있는 각 자료구조에 N번 get의 시간을 측정한다.
2. 멀티스레드
   - N=데이터의 수, M=Thread의 수
   - 각 자료구조에 N * M번 add의 시간을 측정한다. 이때, Vector는 직접 add를 호출하고 ArrayList는 synchronized 블럭에서 add를 수행한다.
   - N개의 데이터가 삽입되어 있는 각 자료구조에 N * M번 get의 시간을 측정한다.

테스트

• N=10,000,000, 단위: ms

시행	Vector		ArrayList
	add	get	add	get
1	282	199	119	47
2	259	198	113	40
3	225	183	116	33
4	253	165	111	36
5	251	169	113	29
6	254	171	117	28
7	263	177	114	30
8	246	180	116	34
9	244	173	109	30
10	210	181	122	30
MIN	210	165	109	28
MAX	280	199	122	47
AVERAGE	248.7	179.6	115	33.7
MEDIAN	252	178.5	115	31.5

 

• N=100,000,000, 단위: ms

시행	Vector		ArrayList
	add	get	add	get
1	3239	1853	1513	373
2	3051	1848	1454	319
3	2607	1838	1491	313
4	2671	1807	1563	299
5	2544	1798	1575	322
6	2500	1831	1613	322
7	2512	1801	1559	291
8	2571	1842	1573	297
9	2520	1757	1458	286
10	2504	1734	1469	298
MIN	2500	1734	1454	286
MAX	3239	1853	1613	373
AVERAGE	2671.9	1810.9	1528.8	312
MEDIAN	2557.5	1819	1536	306

  먼저 싱글 스레드에서 실행 결과다. 두 자료구조 모두 충분한 capacity를 할당한 후 삽입한다면 데이터 수에 비례한 시간 소요를 보였다(\(=O(N)\)). 예상할 수 있듯 Vector는 모두 synchronized 작동을 수행하므로 싱글 스레드에서 압도적으로 불리한 결과를 보인다.  그렇지만 Vector에서 임의 접근하는 데에 소요되는 시간이 ArrayList에 삽입하는 시간보다도 오래 걸리는 것을 확인할 수 있다. ArrayList의 get은 사실상 배열의 get과 call stack의 차이를 제외하고는 같으므로 어디에나 사용할 수 있는 충분히 적은 시간으로 완료되는 것을 알 수 있었다. 어떤 자료구조가 단순히 임의 접근이 가능하다는 사실만으로 시간 복잡도의 계수를 무시하고 '어떤 thread에서나 동기화된다'는 장점만으로 접근하는 것을 시작으로 약 6배의 시간 차이를 받아들이기는 쉽지 않을 것으로 보인다.

 

• N=1,000,000, M=8, 단위: ms

시행	Vector		ArrayList(synchronized)		ArrayList(Mutex)
	add	get	add	get	add	get
1	866	888	644	672	279	191
2	546	701	504	641	228	163
3	711	408	461	416	249	167
4	650	624	443	423	228	168
5	806	677	444	410	236	163
6	534	711	447	423	228	171
7	871	625	462	412	241	165
8	538	626	452	416	232	165
9	536	793	445	423	237	174
10	483	513	443	401	230	166
MIN	483	408	443	401	228	163
MAX	871	888	644	672	279	191
AVERAGE	654.1	656.6	474.5	463.7	238.8	169.3
MEDIAN	598	651.5	449.5	419.5	234	166.5

 

• N=10,000,000, M=8

시행	Vector		ArrayList(synchronized)		ArrayList(Mutex)
	add	get	add	get	add	get
1	6896	8077	7746	7468	3702	1839
2	4624	7706	5525	7189	2920	1825
3	8887	7194	5563	5694	2836	1856
4	6402	7752	5518	5741	2947	1735
5	6387	6541	5472	5449	3344	1755
6	7250	5189	5440	5916	3029	1754
7	7599	6924	5530	5564	2946	1783
8	8754	7533	5551	5174	3107	1732
9	7342	7121	5450	4436	3126	1716
10	6961	7551	5394	5524	3122	1742
MIN	4624	5189	5394	4436	2836	1716
MAX	8887	8077	7743	7468	3702	1856
AVERAGE	7100.2	7158.8	5718.6	5815.2	3107.9	1772.7
MEDIAN	7105.5	7363.5	5521.5	5629	3068	1754.5

  8개의 thread에서 실행한 결과다. 서로 다른 스레드가 자원을 점유하기 위해 경쟁하고 thread context switching에서 발생하는 오버헤드의 영향으로 싱글 스레드에서보다 훨씬 긴 시간이 소요된다. Vector의 구현 의도대로 싱글 스레드에서의 실행처럼 ArrayList와 큰 차이를 보이지는 않았다. ArrayList 대비 약 1.3배의 차이로 격차가 줄어든 것을 알 수 있지만 1000만개의 데이터는 충분히 가능성이 있는 크기이고, 백엔드 서비스의 응용 프로그램 수준의 캐싱같은 기능이 초 단위의 차이를 보인다면 직접 synchronized 블럭에서 ArrayList 작업을 수행하는 것이 나을 것이다. 또한 get 메소드 호출이 훨씬 빈번하고, 호출이 thread safe함이 보장되지 않아도 되는 경우가 훨씬 많다는 점을 생각하면 결국 ArrayList를 사용할 수 밖에 없다. 주목되는 차이는 Kotlin coroutine에서의 수행 시간이다. Thread와 공정한 비교를 위해 모든 coroutine context를 newSingleThreadContext로 실행했음에도 불구하고 훨씬 적은 시간에 작업이 완료된다. Kotlin에서의 Thread pool 관리로 context swiching 오버헤드가 줄어 생긴 차이로 보이나 정확한 구현을 찾기는 어려웠다.

 

결론

  Vector는 느리다. 모든 호출에서 synchronized(this)를 선언한 것과 같은 효과를 가지므로 원치 않는 상황에서 조차 동기화가 이뤄진다. 따라서 필요에 따른 synchronized 블럭에서의 연산이 가능하다는 점과 모든 연산을 synchronized 블럭에서 수행할 때 조차 ArrayList가 빠르다는 점은 더욱 Vector의 사용을 피하게 만든다.

  그렇다면 Vector는 언제 사용할까? 일일히 synchronized 블럭을 사용하기 귀찮을 때보다는 서로 다른 스레드에서 접근이 명백하고, 내용의 수정과 조회가 순서없이 발생할 수 있을 때라면 고려 대상에 포함할만 하다. 또, synchronized 블럭을 직접 선언하고 critical section에서 작업을 수행하는 것은 완벽히 하나의 작업만 수행할 수 있다면 다행이겠지만, 프로그래머가 작성한 코드에 따라 다른 함수를 호출하거나 다른 변수에 접근할 수도 있다. 그 동작이 동기화를 필요로 한다면 환형 대기 상태로 교착 상태에 빠질 가능성 또한 존재한다. 따라서 ArrayList의 메소드 호출이 또 다른 동기화에 의존적이라면 반드시 피해야 할 것이고, 차라리 Vector를 사용하는 편이 나을 수 있다. 그리고 Java Stack의 사용을 피할 수 없다면 이미 Vector를 사용하고 있는 것이라고도 볼 수 있을 것이다.

 

테스트 환경

JDK: 17.0.5

JVM: 17.0.5

JVM Option: -Xms4096m -Xmx4096m

Kotlin: 1.8.0

Kotlin coroutine: 1.6.4

CPU: Intel Core i9-9880H (8C, 16T)