поточно-кэш для разреженных, ленивых, неизменных массивов

Question

У меня есть приложение, которое включает в себя коллекцию массивов, которые могут быть очень большие (индексы вплоть до максимального значения в int), но которые ленивых - их содержание рассчитываются «на лету» и до настоящего времени не известны. Массивы также являются неизменяемыми - значение каждого элемента каждого массива является постоянным на протяжении всего срока службы программы. Массивы в том смысле, что часто лишь небольшое подмножество всех элементов массива либо запрошенной редких (массивы не содержат большие блоки нулей и не «разреженные» в этом смысле.)

Подняв (и, возможно, вычисления в процессе) элемент массива может быть дорогостоящим, поэтому я хочу добавить слой кэширования. Кэш должен реализовать следующий интерфейс:

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

где data служит уникальной ручкой для каждого массива (там может быть много из них). point_cache_fetch() должен вернуть value аргумент, передаваемый point_cache_store() с теми же data и idx аргументами, или указать промах кэша, возвращая особое значение DATUM_UNKNOWN_VALUE (абонент никогда не будет называть point_cache_store с 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». Соответствующим эталоном является «контрольные показатели/b_cache».

Answer 1

«Очень большой разреженный ленивый массив»? Похоже, вам нужен hash table.

Из вашего прототипа point_cache_fetch и по всему вашему вопросу, я смущен о том, являются ли ваши кешированные значения двойными или неизменяемыми массивами.

Я не собираюсь предоставлять реализацию, так как это не веб-сайт, посвященный кодированию. Вам следует попытаться найти и повторно использовать существующие библиотеки потокобезопасных хеш-таблиц и сравнить их производительность для ваших конкретных потребностей.