갑자기 궁금해졌는데
linked list랑 array에 똑같이 100000개 정도 자료 처박아 넣은다음에 반복문으로 처음부터 끝까지 순회해서 불러오는거
array가 더 빠름??
아까 밑에 캐쉬히트 어쩌고 저쩌고 하는 이야기 보고나서 생각났는데 linked list는 데이터를 추가할때 마다 매 노드를 계속 동적할당 하잖아ㅛ
그럼 동적할당한 내용은 힙에 쌓일텐데 만약에 linked list에 100000개를 넣을때 연속해서 넣는게 아니라 한개 넣고 중간에 다른짓 (힙에 뭔가 쌓일만한 행동)
하고 다시 넣고 이러면
노드주소들 끼리 거리 멀어져서 캐쉬히트할 확률 낮아짐??
연결리스트랑 배열이랑 비교하면 당연히 배열이 빠르지
ㄴ 근데 빠른 이유가 뭐임?? 내가 궁금한건 "~~"를 내놔라 이런 접근 말고(꼭 인덱스가 있어야 빠른거 말고) 처음부터 끝까지 다 출력하는 경우에도 array는 array의 size만큼 다 붙어 있어서 출력하는데 더 빠른게 맞나 궁금한거라..
캐시를 떠나서 배열은 인덱스에서 정수 덧셈 한번 메모리에서 로드가 한번만 일어나지만 링크드리스트는 메모리에서 로드하고 또 메모리에서 로드함.
내가 기억하기로 메모리에서 로드하는데 코스트가 덧셈 연산보다 클 껄?
링크드는 삭제 추가에 용이해서 쓰는것뿐
linked list 랑 array랑 시작부터 끝까지 다 조회할때 캐쉬가 무한히 커서 캐쉬히트에 영향을 받지 않으면 둘다 똑같아야 하는거 아님? aarray 나 linked list나 둘이 구조는 같은데 array는 서로 다 붙어있기때문에 index라는 숫자로 +1씩 더해줘서 자기 type의 주소만큼 뒤로 밀어줘서 다음 주소를 구하는거고 linked list는 배열 원소 하나하나가 멀리 처박혀 있어서 index대신 다음값의 주소를 갖고 있어야 하는거고
빠르면 비행기
내가 기억하기로는 i++가 i=*k보다 빠를꺼야. 주소 찾는거 때문에.
오프셋 구하고 나면 나머지 과정은 같으니까
그래서배열이빠른거맞아
위에 말이 array의 경우 단순히 index를 ++해주면 (증가연산) 끝이지만 linked list 는 다음 주소를 넣어줘야 하니 다음 주소를 갖고 있는 변수의 주소를 한번 더 참조해야 해서 array가 더 빠르다 라고 이해하면 맞는거임?
ㅇㅇ 그리고 캐시 차이도 맞아.
링크드리스트를 동적할당 안하고 노드를 배열로 선언해서 만들면 캐시 문제랑 상관 없이 테스트 할 수 있는데
그래도 배열 인덱스가 빠르니까 메모리 연산이 한번 많은 링크리스트가 느리다고 생각하는게 맞을거야.
아재들 밤에 일어나면 물어봐. 이런건 변태들이 잘 알꺼야
근데 생각해보면 array도 우리가 보는건 인덱스에 증가연산만 하는거 같지만 실제로 주소를 구할땐 원래주소+sizeof(type)*n 하는 걸텐데 다만 배열을 생성할때 type은 이미 정해져있는 상수이고..n은 1씩 늘어나니 (처음부터 끝까지 다 출력하는 경우) 아시발 헷갈려
고려해야할 요소가 캐시, 그리고 대입연산자 사용 횟수, 메모리 참조 횟수
그런데 사실 캐시 히트는 메모리 참고 횟수가 같거나 비슷할 때 이야기고 메모리 참고 횟수 자체가 많으면 결국 참고 횟수 쪽이 많은 쪽이 느릴거야
접근만 따지고 보면 배열이 빠르지
linked list에서 다음 단계로 넘어가려면, next노드의 주소값을 가져와야지(메모리 참조1번) 그 주소값으로 가서 넥스트 노드의 값을 가져와지(메모리 참조 2번)
array는 시작 주소값 한번만 가져오고 거기에다가 sizeof(값)만 계속 더하면서 메모리를 찾기 때문에 메모리 참조 한번. 일단 여기서 한번만 참조하기에 빠름
그리고 결정적으로 메모리가 캐시에 올라오는데, list같은 경우는 캐시 미스매칭이 일어날 확률이 높다. (리스트가 바로 옆에 저장되리란 보장이 없음) 하지만 배열은 dense하게 한곳에 밀집 되어있기에 캐시에 올렸을때 캐시 미스매칭이 될 확률이 적음
참고로 메모리 참조는, 프로세서에서 한 인스트럭터 계산하는 속도의 40배 느리다고함.