LRU 제한된 크기의 C로 된 캐시 디자인

Question

저는 메모리가 매우 작은 모바일 플랫폼 소프트웨어를 개발 중입니다. I/O 병목 현상의 경우, seek 연산을 사용하여 img 파일에서 몇 바이트를 읽어야합니다 (memmry에서 직접 읽는 것보다 seek가 약 10 배 정도 느릴 것이라고 가정 할 수 있음). 필자의 테스트에서이 함수는 7480325 번 호출되었고 bytes_offset 6800에서 130000으로 바이트를 읽음으로써 모든 바이트가 평균 100 번 읽혔다 (일부 바이트는 3 ~ 4 번, 1000 번 이상 읽혔다).

아래는 제 통계입니다.

bytes offset 6800 ~ 6900: 170884 times 
bytes offset 6900 ~ 7000: 220944 times 
bytes offset 7000 ~ 7100: 24216 times 
bytes offset 7100 ~ 7200: 9576 times 
bytes offset 7200 ~ 7300: 14813 times 
bytes offset 7300 ~ 7400: 22109 times 
bytes offset 7400 ~ 7500: 19748 times 
bytes offset 7500 ~ 7600: 43110 times 
bytes offset 7600 ~ 7700: 157976 times 
... 
bytes offset 121200 ~ 121300: 1514 times 
bytes offset 121300 ~ 121400: 802 times 
bytes offset 121400 ~ 121500: 606 times 
bytes offset 121500 ~ 121600: 444 times 
bytes offset 121600 ~ 121700: 398 times 

max_bytes_offset 121703 
min_bytes_offset 6848 

그런 다음 I/O 성능을 향상시키기 위해 LRU 스키마를 사용하여 캐시를 작성하려고합니다. 다른 사람들의 질문에서, 나는 해시 테이블 + 이중 연결리스트가 좋은 방법이라는 것을 발견했다. 그러나 최선의 방법으로 내 문제를 개선하기위한 구조를 만드는 방법은 무엇입니까? 1300 개의 버킷을 만들 계획이며 모든 버킷은 최대 크기가 10 인 이중 연결 목록을 소유하고 있습니다. 그런 다음 총 메모리는 약 13KB입니다. 구현 및 유지 관리는 간단하지만 효율이 가장 좋지 않다고 생각합니다.

내 통계에는 간격이 약간있는 반면 오프셋 간격이 더 많은 조회수 비율이 있습니다. 통계를 적용 할 수있는 구조를 만들려면 어떻게해야합니까?

키를 검색 할 때 크기가 10 인 전체 목록을 탐색해야합니다. 검색 효율이 높은 다른 방법이 있습니까?

일부 모바일 플랫폼에서는 캐시가 더 많은 메모리를 사용할 수 있지만 다른 플랫폼은 더 적은 메모리를 사용할 수 있습니다. 버킷의 크기를 변경하는 것을 제외하고 허용 된 메모리 변경 사항을 적용하도록 캐시를 만들려면 어떻게해야합니까?

카페의 방법이 더 좋은 것처럼 보입니다. 큰 이중 연결 목록과 큰 해시 테이블을 사용하여 키를 노드 항목에 매핑하는 것이 더 적합하며 LRU를 더 많이 활용합니다. 그러나 해시 함수를 설계하는 것은 어려운 문제가되고 있습니다. 당신은 단지 당신이 가능성이 이중 연결리스트와 분배 더 나을 것, 각 버킷에 10 개 항목의 최대를 가질려고하는 경우에 나는 당신의 제안을 기다리고 있어요

는 ~

Answer 1

감사합니다 각 버킷을 원형 배열 (단지 10 개의 항목과 "목록의 최상위"색인 임)로 만듭니다.

10 방향 집합 연관 디자인을 삭제하고 직접 매핑 된 캐시 (더 큰 해시 테이블이있는 곳, 각 버킷에 하나의 항목 만 저장)을 사용하는 것이 더 나을지도 있습니다. 세트 연관 설계는 하드웨어에서 우수합니다. 병렬 하드웨어에서 n 방향 비교를 수행 할 수 있지만 소프트웨어에서는 그렇지 않습니다 (벡터 단위를 사용하지 않는 한).

통계에 적응하는 한 가지 방법은 서로 다른 크기의 주소 범위를 각 버킷에 매핑하여 각 버킷의 액세스 빈도가 거의 같도록 해시 함수를 설계하는 것입니다.

해시 테이블의 크기를 변경하는 것은 캐시의 크기를 조정하는 또 다른 분명한 방법입니다.