MTF/LRU 최적화 in Bit level

MTF/LRU란, 가장 최근에 쓰인 값을 리스트의 가장 최상위에 넣는 것이다. 정해진 리스트보다 값이 크면 가장 쓰이지 않던 값을 빼고, 만약 이미 리스트에 있는 값이 다시 쓰이면 기존 값을 다시 꺼내서 맨 위로 올릴 수 있다 (그렇게 함으로서 최근에 쓴 값을 더 우선순위를 높이는 방식으로 구현을 할 수도 있을 것이다.)

우리는 여기에 적합한 주된 자료구조로 queue를 사용하곤 하는데, 보통 뺀 값을 다시 맨 윗 단에 넣을 수가 있다.

for (uint i = rep_idx; i > 0; --i)
        offsets[i] = offsets[i - 1];
    offsets[0] = tmp;

하지만 이 구현이 정말 효율적인 구현일까? 8개의 element가 들어있고 가장 마지막 원소가 재사용 되었다면, 우리는 7개의 값을 다시 내리고 맨 아래 1개의 값을 올려야 한다. 총 8Load + 8Store의 고된 작업, O(n)이다. 리스트가 커지면 이는 더 곤란한 상황이 된다.

가장 대중적이고 쉽게 떠올리는 방법은 Linked List이다. 단순히 자료구조의 연결고리를 풀고, 맨 앞에 붙이면 그만이다. 아마 링크드 리스트의 처음과 끝을 가지고 있으면 쉽게 구현할 수 있다. 하지만 이 경우, 중간 값의 액세스가 시간이 걸릴 수 있어서 한정된 용도로 사용해야 함을 염두에 둘 필요가 있다.

new_back = offsets_back.prev
offsets_back.prev.next = NULL
offsets_back = new_back
tmp.next = offsets
offsets = tmp

하나 또 재미있는 것은, 리스트 갯수가 충분히 제한되어 있다고 상정한다면 (이 경우에는, 32bit machine, 8개 이하), 이러한 리스트 순서를 bit 형태로 관리할 수 있다는 것이다. offset_bit 과 같은 변수를 두어 shift operation을 하고, 기존 리스트 값을 변경하기만 하면 끝이다. 이 경우, offset_bit = 0x76543210 으로 초기화 되어야 할 것이다.

Link

https://fgiesen.wordpress.com/2016/03/07/repeated-match-offsets-in-bitknit/