캐시 경계 표현 (0 페이지에서 1 페이지로 간다)

000111111


데이타 2진 탐색 순서

104530002


5번의 위치를 찾아가는 경우를 가정해 보자,

캐시는 무지 빠르고 메모리를 prefetch 하는 속도가 무지 느리다고 가정,


순차탐색의 경우는 0 에서 1로 넘어가는 한 번 prefetch 가 일어난다.

하지만 2진 탐색의 경우는

페이지 0(1), 페이지 1(2), 페이지 0(4), 페이지 1(5)의 순서로 prefetch 된 메모리를 박살내게 된다.


즉 순차 탐색보다 빠르기 힘들다.