스파 스, 게으른 불변의 불변의 배열을위한 스레드 안전 캐시

Question

매우 클 수있는 배열 (int의 최대 값까지의 인덱스)을 포함하는 응용 프로그램을 가지고 있지만, 지연 시간이 느림 - 그 내용 즉석에서 계산되며 요청 될 때까지 실제로 알려지지 않습니다. 배열은 또한 불변입니다 - 각 배열의 각 요소 값은 프로그램 수명 내내 일정합니다. 배열은 (배열이 제로의 큰 블록을 포함하지 그 의미에서 "스파 스"하지 않습니다.) 종종 모든 배열 요소의 작은 부분 집합 적 요구하는 의미에서 스파 스 있습니다

(최대 찾고 아마도 프로세스에서 계산할 때) 배열 요소가 비쌀 수 있으므로 캐싱 레이어를 추가하고 싶습니다. data는 각 배열에 대해 고유 한 핸들의 역할을 어디

void point_cache_store (gpointer data, gsize idx, gdouble value); 
gdouble point_cache_fetch (gpointer data, gsize idx); 

가 (이 많이있을 수 있습니다) : 캐시는 다음과 같은 인터페이스를 구현해야합니다. point_cache_fetch()는 (호출자가 DATUM_UNKNOWN_VALUE와 point_cache_store를 호출하지 않습니다) 같은 data 및 idx 인수 point_cache_store()에 전달 된 value 인수를 반환하거나 특수 값 DATUM_UNKNOWN_VALUE을 반환하여 캐시 미스를 표시해야합니다.

질문 : point_cache_fetch()과 point_cache_store()을 어떻게 구현할 수 있습니까? (그들은 현재 어떤 조합 스텁입니다.)

포인트 고려 :

• 캐시 구현이 스레드 안전해야합니다. 여러 스레드가 동시에 실행 중이며 point_cache_store() 또는 point_cache_fetch()을 data 또는 idx 인수와 함께 호출 할 수 있습니다.
• 캐시는 실제로 캐시입니다. point_cache_fetch()이 그 값을 알고 있더라도 항상 DATUM_UNKNOWN_VALUE을 반환해도 괜찮습니다. 호출자는이 경우 일반 조회 만 수행합니다.
• 배열은 변경 불가능합니다. 주어진 data 및 idx 인수의 경우 호출자는 항상 동일한 value 인수를 제공합니다.

나는 이것을 할 수있는 많은 방법이 있으며 절충안이 관련되어 있다는 것을 알고 있습니다. 이 질문에 대해서는 답변을 하나의 매우 구체적인 기준으로 평가할 것입니다. 즉, 질문에서 영감을 얻은 응용 프로그램의 특정 벤치 마크에서 성능을 향상시킬 지 여부입니다. 당신이 여분의 마일을 이동하고 벤치 마크를 직접 실행하려면, 여기를 수행하는 방법입니다 :

git clone git://github.com/gbenison/starparse 
git clone git://github.com/gbenison/burrow-owl.git -b point-cache-base 

기능 point_cache_fetch() 및 point_cache_store()는 "굴/스펙트럼/point_cache.c"에서 발견된다. 관련 벤치 마크는 "benchmarks/b_cache"입니다.

Answer 1

"매우 큰 희소 한 게으른 배열"? hash table이 필요한 것 같습니다.

point_cache_fetch 함수 프로토 타입과 모든 질문을 통해 캐시 된 값이 double인지 immutable인지에 대해 혼란 스럽습니다.

'코딩 도전'웹 사이트가 아니기 때문에 구현을 제공하지 않을 것입니다. 쓰레드 안전 해시 테이블의 기존 라이브러리를 찾아 재사용하고 특정 요구 사항에 대한 성능을 비교해야합니다.