c - 用于稀疏、惰性、不可变数组的线程安全缓存

Question

我有一个应用程序，涉及一个数组集合，这些数组可能非常大(索引最大为 int 的最大值)，但它们是惰性 - 它们内容是动态计算的，并且在请求之前实际上是不知道的。数组也是不可变的 - 每个数组的每个元素的值在程序的整个生命周期中都是恒定的。这些数组是稀疏，因为通常只请求所有数组元素的一小部分(数组不包含大块的零，因此在这个意义上不是“稀疏”。)

查找(并可能在过程中计算)数组元素可能会很昂贵，因此我想添加一个缓存层。缓存应该实现以下接口(interface):

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

其中data充当每个数组的唯一句柄(可以有很多这样的数组)。 point_cache_fetch() 应返回传递给 point_cache_store() 的 value 参数，并具有相同的 data 和 idx 参数，或通过返回特殊值 DATUM_UNKNOWN_VALUE 来指示缓存未命中(调用者永远不会使用 DATUM_UNKNOWN_VALUE 调用 point_cache_store)。

问题是:如何实现 point_cache_fetch() 和 point_cache_store()？ (它们目前是无操作 stub 。)

需要考虑的要点:

• 缓存实现必须是线程安全的。多个线程同时运行，其中任何线程都可以使用任何 data 或 idx 调用 point_cache_store() 或 point_cache_fetch() > 论据。
• 缓存确实是一个缓存； 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()位于“burrow/spectrum/point_cache.c”中。相关基准是“benchmarks/b_cache”。

Answer 1

“非常大的稀疏惰性数组”？听起来你需要一个 hash table .

从您的 point_cache_fetch 函数原型(prototype)和整个问题中，我对您的缓存值是 double 还是不可变数组感到困惑。

我不会提供实现，因为这不是“编码挑战”网站。您应该尝试查找并重用现有的线程安全哈希表库，并根据您的特定需求比较它们的性能。