출처 : https://dzone.com/articles/performance-of-array-vs-linked-list-on-modern-comp
Performance of Array vs. Linked-List on Modern Computers
위에서 설명했다시피 Linked-list는 특정 지점에서 Array보다 일반적으로 더 빨랐을지 모르지만, 현대 기술이 개선 된 후 배열이 더 선호되고 있다.
여기서 언급된 Array는 자동적으로 배열의 크기가 조정되는 Array (C++의 vector, Java의 ArrayList 혹은 C#의 List) 다.
물론 이론적으론...
지금까지 배운 이론적인 내용으로는 Linked-list가 Array에 비해서 random-insertion과 random-deletion에서 더 빠르다고 말한다.
그래서 인터넷에서 많은 사람들이 수많은 random-insertion과 random-deletion이 필요한 경우 linked-list를 제안하는 것을 많은 포스팅에서 봐왔다.
...To Practice
※ 참고
위에 나오는 "list"는 C++에서 구현된 doubly linked-list 다. 그리고 "vector"는 C++에서 자동으로 재할당된(automatically-reallocated) 배열로 구현되어있다.
위 성능 그래프를 보면 실제로 "Linked-list가 Array에 비해서 random-insertion과 random-deletion에서 더 빠르다" 라고 하는것은 사실이 아닌 것을 확인할 수 있다.
과거에 CPU 속도가 아주 느린 때에는 이론적으로는 사실이였다. 그러나 현재는, 상황이 변했다, 그리고 컴퓨터 아키텍쳐또한 변했다. 그러므로, 몇몇 상황에서 더 이상 위 이론은 사실이 아니다.
현대 컴퓨터의 CPU 속도는 너무 빠르며, RAM 접근 속도보다 훨씬 빠르다.
RAM으로 부터 읽기를 하려면 수백개의 CPU cycles이 필요하고 이 작업은 매우 느리다. 만약 이런 경우라면, 대부분의 시간에 CPU는 그냥 앉아서, 차를 한잔 마시고, 그리고 베스트 프랜드인 RAM을 기다릴 것이다.
And Then, CPU Caches Come into Play
CPU에서 RAM에 있는 데이터를 직접 처리한다면, RAM에 접근하는 속도는 아주 느릴뿐더러 이때 99%의 CPU 속도가 낭비될 것이다. 그러면 이때 우리는 CPU의 1%의 파워만 사용할 수 있다. 그러므로, 이 문제를 해결하기 위해서 CPU cache가 등장했다
Cache memory 는 아주 빠르고 CPU에 직접 내장되어있다. 접근 속도는 CPU 속도에 근접한다. 그래서 현재는, RAM의 데이터에 직접 접근하는 대신, CPU는 RAM의 데이터에 L1 cache를 통해서 간접적으로 접근한다. (보통은 3가지 레벨의 cache가 있다, 그리고 L1 cache는 그중 가장 빠르다.)
그러나, CPU cache는 문제를 완전히 해결하지 못한다. 왜냐하면 메모리 cache 크기가 RAM보다 훨씬 작기 때문이다.
우리는 여전히 RAM을 메인 메모리로써 필요하다. 그래서 CPU cache는 가까운 미래에 CPU에서 필요할 것 같은 데이터의 작은 조각을 갖고 있는다. 하지만 때때로, CPU가 다음에 접근할 데이터가 미리 L1 cache (또는 L2나 L3 cache도 없는 상태)에 있지 않는다. 그리고 그것은 RAM으로 부터 가지고 와야만 한다. 그러면 CPU는 수백 cycle을 데이터가 사용가능해질 때까지 기다려야만 할것이다. 이것을 우리는 cache miss라 부른다.
그러므로, cache miss 를 줄이기 위해, CPU가 RAM의 x 주소에 있는 데이터에 접근하길 원할 때, 주소 x에 데이터만 가져오는 것이 아니라 주소 x 의 이웃 주소 역시 가져온다. 왜냐하면 우리는 "특정 시간에 특정 메모리 위치가 참조되었다면, 그 메모리 위치 근처에도 가까운 미래에 참조 될 수 있다[3]"고 가정하기 때문이다. 이것을 우리는 locality of reference 라 부른다. 그래서, 만약 CPU에 의해 처리될 데이터가 서로 인접해 있다면, 우리는 locality of reference 를 사용할 수 있게 할 수 있고 자주 발생하면 큰 부하가 될 수 있는 cache miss를 줄일 수 있다.
The Problem of Linked-List
요소들이 서로 바로옆에 있어서 Cache-friendly 데이터 구조인 Array와는 다르게, linked-list의 요소들은 메모리의 어디에나 배치될 수 있다. 그래서 linked-list를 순회할때, 수많은 cache-miss 를 발생시킬 수 있다(우리가 locality of reference를 사용할 수 없기 때문에), 그리고 수많은 성능 부하를 유발한다.
Performance of Array vs Linked-List
물론 Random-insertion 혹은 random-deletion이 array에서 수행될 때, 뒤에있는 요소들은 이동(Shift)과정을 거쳐야한다.
그러나 작은 요소 리스트들에 대해(POD 타입의 리스트 혹은 포인터들의 리스트), 요소들을 옮기는 비용은 cache miss의 비용보다 훨씬 싸다.
그러므로, 대부분의 시간, 작은 데이터 타입의 리스트로 작업할때 (어떤 연산이든 간에: 순회, random-insertion, random deletion 부터 수의 계산까지), Array의 성능은 linked-list보다 훨씬 더 좋을 것이다.
그러나 우리가 큰 요소들의 리스트로 작업하는 경우( > 32 bytes), 요소들을 이동시키는 비용은 linked-list의 "일반적인" cache miss 비용보다 더 커진다. 이때 Linked list는 더 Array보다 더 성능이 좋을 것이다.
Conclusion
결론적으로 우리는 POD, 포인터 혹은 Java의 레퍼런스와 같은 작은 요소로 된 리스트로 작업할때, Linked-list보다 Array를 더 선호해야 한다.
그리고 대부분의 경우, 다음의 이유로 배열을 사용한다.
- C++에서, 우리는 큰 데이터 타입의 리스트를 자주 사용하지 않는다, 그러나 큰 데이터 타입을 가리키는 포인터의 리스는 자주 사용한다. 만약 우리가 큰 크기의 클래스/구조체 그리고 수많은 random-insertion 과 random-deletion이 필요하다면, linked-list가 더 나은 선택이다.
- Java에서, 우리는 오브젝트의 리스트 대신에 힙에 있는 오브젝트를 가리키는 레퍼런스의 리스트를 사용해야한다. 왜냐하면 레퍼런스 타입은 기본적으로 힙에 배치되므로, 우리는 그것의 레퍼런스를 만들 수 있기 때문이다. 레퍼런스는 포인터로 관리되어지기 때문에, 그것의 크기는 8 bytes를 넘지 않는다.
CPU cache는 현대 컴퓨터에서 프로그램 성능 향상에 아주 중요한 역할을 하다.
References
- [1] vector vs list performance benchmark, Baptiste Wicht: http://baptiste-wicht.com/posts/2012/11/cpp-benchmark-vector-vs-list.html
- [2] C++ vector, list, deque performance benchmark, Baptiste Wicht: http://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html
- [3] Locality of reference: https://en.wikipedia.org/wiki/Locality_of_reference
- [4] Understanding CPU caching and performance, Jon Stokes: http://arstechnica.com/gadgets/2002/07/caching/