LinkedList와 ArrayList의 성능에 대한 궁금증

지금 보니 반복문 잘못 만들었구나..

 

 

어제 코드 스테이츠 라이브 섹션 중, 자바 기초를 배울 때 늘 듣는 "ArrayList는 탐색속도는 빠르지만 LinkedList보다 중간 요소의 삽입,삭제는 더 느리다"라는 멘트를 길게 듣고 있는데 동기분들 중 한 분이 배열 중간에서부터 삭제하는 게 LinkedList가 빠르더라도 인덱스를 탐색하는 시간이 오래 걸리면 배열이 커질수록 오히려 중간을 수정, 삭제하더라도 ArrayList보다 느린 게 아니냐고 질문하셨다.

 

어떻게 생각해보면 당연한 이야기지만 직접 테스트해보니 엄청나게 차이가 났다.

그리고 찾아보니 실제로도 이 문제와 다른 요인들 때문에 LinkedList는 거의 사용하지 않는다고 한다.

 

https://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist-in-java

When to use LinkedList over ArrayList in Java?

 

옛날옛적 컴퓨터 성능이 별로 좋지 않던 시절에는 LinkedList가 특정 상황에 더 유리한 경우도 꽤나 있었으나, 지금의 컴퓨터는 엄청나게 빠르기 때문에 오히려 Cache miss를 발생시켜 Cpu의 연산을 방해할 수 있는 LinkedList는 어떤 경우에서도 최악의 선택이 될 확률이 높다는 것이다.

 

대기열 같은 FIFO 구조에서는 LinkedList가 유리할 수도 있다고 하는데 내가 직접 테스트해본 부분이 아니라 쩝..

사실 해당 링크에 있는 글들도 내 지식의 부족으로 인해 완전히 이해하지 못하고 있는 상태이다.

 

더 공부하고 언젠가 해당 내용에 대해 완벽하게 정리해서 정보글을 작성하고 싶다.

 

 

 

 

2022/08/30 --

 

가상 메모리와 캐시에 대해 공부하면 왜 LinkedList를 사용하지 않는지 알 수 있다.

데이터 로드 시 당장 불러낸 자료에 대해서만 가져오는 것이 아니라, 같은 열에 위치한 데이터는 같이 쓰일 확률이 높으며, 비슷한 시간에 저장된 정보는 같이 쓰일 확률이 높다는 조건에 의해 인근에 위치한 데이터까지 한 번에 불러와서 캐시에 저장한다.

그리고 이렇게 저장된 데이터를 활용해 주 기억장치(RAM)에 직접 접근하지 않고 캐시 저장소에서 바로 데이터를 가져오는 것을 "Cache Hit"라고 부른다.

LinkedList의 경우 메모리 주소가 정렬되어 있지 않기 때문에 Cache Miss가 일어날 확률이 굉장히 높아지는데, 옛날에는 연산 낭비나 자원 활용의 이점을 활용하기 위해 경우에 따라 LinkedList를 사용했지만 지금은 고작 가정용 공유기에도 8gb 메모리가 들어가는 시대다.

게다가 CPU가 보조 기억장치, 주 기억장치에 비해 너무나도 빠른 나머지 어떻게든 I/O장치들과의 병목현상을 줄이기 위해 가능한 모든 부품에 캐시를 덕지덕지 붙이고 있는데 그럼에도 조금만 삐끗하면 병목한상이 일어난다.

즉, 저장 공간이나 연산 시간 같은 건 훌륭한 컴퓨터 부품들이 알아서 다 해결해주니까 최대한 빨리 CPU로 넘겨만 주면 그만이라는 것이다.

이에 따라 현 시점에서는 특수한 경우가 아니라면 묻지도 따지지지도 않고 메모리 주소가 가지런히 정렬되어 있는 List를 대부분의 경우에 사용하게 되었다.