[질문] 삽입 정렬 하는데 벡터에 비해 리스트가 엄청 느린데

[익명(117.20)]

이미 정렬 된 자료를 InsertSort 하는데 Vector는 10ms 전후로 끝나는데

list는 분단위로 걸림.

정렬 코드는 둘다 rotate쓰는 같은 코드.

이거 캐시 히트율 차이라서 그런거 맞지?

다른 이유는 도저히 생각 안나는데

[익명(117.20)]

언어는 당연히 c++임

[0xrgb(0xrgb)]

insertsort가 어떻게 구현됬는지에 따라 다르지만 list 특성 (중간에 삽입 가능) 못 살리고 일일히 교환하는 코드였으면 느린게 당연하고, 아니면 캐시 히트율 차이가 맞을것

[익명(117.20)]

https://en.cppreference.com/w/cpp/algorithm/rotate
여기 예제 코드 처럼 구현되었습니다.

[익명(117.20)]

근데 이미 정렬된거라 swap 할 일이 없었을텐데 hit 차이만으로 저런 결과가 나오는건가요...

[0xrgb(0xrgb)]

이미 정렬된거면 그냥 한번 쭉 둘러보는거랑 다를게 없는데 그러면 캐시히트율 차이지

[커헠(msca8h)]

캐시히트율 ㅇㅇ 삽입 삭제 할 때 random access 가 안되기 때문에 캐시 다 터져서 느려지쥬 ㅇㅇ - return 0;

[익명(117.20)]

무섭네요;; 참조 지역성이 이렇게 컸었네

[커헠(msca8h)]

캐시 레벨별 접근 레이턴시 계산해보면 나오는거 아냐? L2 L3 만 가도 몇십 몇배 느려지는데 그만큼 삽입삭제도 느려지는거지 - return 0;