[번역]Performance of Array vs. Linked-List on Modern Computers

개인 공부용으로 번역한 거라 잘못 번역된 내용이 있을 수 있습니다.

또한 원작자의 동의 없이 올려서 언제든 글이 내려갈 수 있습니다.

출처 : 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보다 일반적으로 더 빨랐을지 모르지만, 현대 기술은 개선 된 후 배열이 더 선호되어질 수 있습니다. 

 

A Few Notes

여기서 언급된 Array는 자동적으로 배열의 크기가 조정되는 Array (C++의 vector, Java의 ArrayList 혹은 C#의 List) 입니다. 이 글에 있는 vector와 list의 벤치마크 그래프는 이글의 "Baptiste Wicht"의 것입니다. (내 시간을 절약해준 밴치마크에 감사합니다)

From Theory...

사람들은 Linked-list가 Array에 비해서 random-insertion과 random-deletion에서 더 빠르다고 말합니다. 그것은 또한 우리가 배운 이론입니다.

그래서 나는 인터넷에서 많은 사람들이 수많은 random-insertion과 random-deletion이 필요한 경우 linked-list를 제안하는 것을 봐왔습니다.

 

...To Practice

"어떻게 이럴수가 있을까요?"

 

"Impossible!"

 

주의: 위에 나오는 "list"는 C++에서 구현된 doubly linked-list 입니다. 그리고 "vector"는 C++에서 자동으로 재할당된(automatically-reallocated) 배열로 구현되어졌습니다.

사람들이 말한 것은 사실이 아닙니다. 이전에 CPU 속도가 아주 느린 때에는 이론적으로는 사실입니다. 그러나 현재는, 상황이 변했습니다, 그리고 컴퓨터 아키텍쳐는 변했습니다. 그러므로, 몇몇 상황에서 더 이상 이것은 사실이 아닙니다.

현대 컴퓨터의 CPU 속도는 너무 빠르며, RAM 접근 속도보다 훨씬 빠릅니다. RAM으로 부터 읽기를 하려면 수백개의 CPU cycles이 필요합니다. 이것은 아주 느립니다. 만약 이런 경우라면, 대부분의 시간이, CPU는 그냥 앉아서, 차를 한잔 마시고, 그리고 베스트 프랜드인 RAM을 기다릴 것입니다.

 

And Then, CPU Caches Come into Play

CPU에 RAM에 있는 데이터를 직접 처리한다면, RAM 접근 속도는 아주 느립니다, 99%의 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에서 수행될때, 후속 요소들은 이동되어져야 합니다.

그러나 작은 요소 리스트들에 대해(POD 타입의 리스트 혹은 포인터들의 리스트), 요소들을 옮기는 비용은 쌉니다, cache miss의 비용보다 훨씬 쌉니다. 그러므로, 대부분의 시간, 작은 데이터 타입의 리스트로 작업할때 (어떤 연산이든 간에: 순회, random-insertion, random deletion 부터 수의 계산까지), Array의 성능은 linked-list보다 훨씬 더 좋을 것입니다.

그러나 우리가 큰 요소들의 리스트로 작업하는 경우( > 32 bytes), 요소들을 이동시키는 비용은 linked-list의 "일반적인" cache miss 비용보다 더 커집니다. 이때 Linked list는 더 Array보다 더 성능이 좋을 것입니다.

Conclusion

우리는 POD, 포인터 혹은 Java/C#의 레퍼런스와 같은 작은 요소로 된 리스트로 작업할때, Linked-list보다 Array를 더 선호해야합니다.

그리고 대부분의 경우, 다음의 이유로 배열을 사용합니다:

 

• C++에서, 우리는 큰 데이터 타입의 리스트를 자주 사용하지 않습니다, 그러나 큰 데이터 타입을 가리키는 포인터의 리스는 자주 사용합니다. 만약 우리가 큰 크기의 클래스/구조체 그리고 수많은 random-insertion 과 random-deletion이 필요하다면, linked-list가 더 나은 선택입니다.
• Java에서, 우리는 오브젝트의 리스트 대신에 힙에 있는 오브젝트를 가리키는 레퍼런스의 리스트를 사용해야합니다, 왜냐하면 레퍼런스 타입은 기본적으로 힙에 배치되므로, 우리는 그것의 레퍼런스를 만들 수 있습니다. 레퍼런스는 포인터로 관리되어지기 때문에, 그것의 크기는 8 bytes를 넘지 않습니다.
• C#에서, 우리는 종종 struct 대신의 class를 사용합니다, 그래서 우리는 힙에 있는 오브젝트를 가리키는 레퍼런스의 리스트를 다뤄야만 합니다. 그리고 만약 우리가 구조체를 사용하면, C#에서 큰 크기의 구조체를 만드는 것은 나쁜 예이므로 우리는 큰 구조체를 만들지 않습니다.

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/