Return to Question

Edited 3/27/2012 to explain selection of answer: After giving this some more thought, I have come around to William Morris' view (see accepted answer) that this is basically the wrong approach. I am not totally convinced that it's impossible to implement this cache without locking, but I am convinced that it is quite hard. This is code I wrote several years ago and I now see it as an example of premature optimization. Since this cache is used a lot, I wanted to avoid mutexes. However I think the best thing to do now is to take a step back, take another look at what motivated this data structure, and think about a better solution.

I am trying to implement a shared cache for arrays. It must support two operations: set(owner, idx, value) and fetch(owner, idx) where idx is the index into the array and owner is an opaque handle to an owning object -- fetch(owner_1, idx) should return the value stored by set(owner_1, idx) only if the owner argument matches. The cache must be thread - safe but I do not want to rely on locking, i.e. mutexes. Failure in looking up cached values is fine - it is OK and expected that other threads will overwrite existing values in the shared cache, in which case fetch should just fail.

I am trying to implement a shared cache for arrays. It must support two operations: set(owner, idx, value) and fetch(owner, idx) where idx is the index into the array and owner is an opaque handle to an owning object -- fetch(owner_1, idx) should return the value stored by set(owner_1, idx) only if the owner argument matches. The cache must be thread - safe but I do not want to rely on locking, i.e. mutexes. Failure in looking up cached values is fine - it is OK and expected that other threads will overwrite existing values in the shared cache, in which case fetch should just fail.

I am trying to implement a shared cache for arrays. It must support two operations: set(owner, idx, value) and fetch(owner, idx) where idx is the index into the array and owner is an opaque handle to an owning object -- fetch(owner_1, idx) should return the value stored by set(owner_1, idx) only if the owner argument matches. The cache must be thread - safe but I do not want to rely on locking, i.e. mutexes. Failure in looking up cached values is fine - it is OK and expected that other threads will overwrite existing values in the shared cache, in which case fetch should just fail.

Edited 3/27/2012 to explain selection of answer: After giving this some more thought, I have come around to William Morris' view (see accepted answer) that this is basically the wrong approach. I am not totally convinced that it's impossible to implement this cache without locking, but I am convinced that it is quite hard. This is code I wrote several years ago and I now see it as an example of premature optimization. Since this cache is used a lot, I wanted to avoid mutexes. However I think the best thing to do now is to take a step back, take another look at what motivated this data structure, and think about a better solution.

I am trying to implement a shared cache for arrays. It must support two operations: set(owner, idx, value) and fetch(owner, idx) where idx is the index into the array and owner is an opaque handle to an owning object -- fetch(owner_1, idx) should return the value stored by set(owner_1, idx) only if the owner argument matches. The cache must be thread - safe but I do not want to rely on locking, i.e. mutexes. Failure in looking up cached values is fine - it is OK and expected that other threads will overwrite existing values in the shared cache, in which case fetch should just fail.

I am trying to implement a shared cache for arrays. It must support two operations: set(owner, idx, value) and fetch(owner, idx) where idx is the index into the array and owner is an opaque handle to an owning object -- fetch(owner_1, idx) should return the value stored by set(owner_1, idx) only if the owner argument matches. The cache must be thread - safe but I do not want to rely on locking, i.e. mutexes. Failure in looking up cached values is fine - it is OK and expected that other threads will overwrite existing values in the shared cache, in which case fetch should just fail.

So the fetch operation has to read the cache slot's owner field to check against its argument, and if it matches return the cache slot's value field. The problem is, without locks, another thread could overwrite one of these fields during that operation. This approach tries to get around that by assigning a version field to each cache slot. It only increases. The fetch operation reads the version (atomically) at the start of the operation and at the end; if these are not the same, something changed during the read and the result is invalid, even if the owner field apparently matched.

The code below ensures that version is always incremented before value is updated, thus preventing fetch from returning a value from a different owner. (The functions g_atomic_... are provided by glib.) It "seems to work" - but can it be proven correct or incorrect?

struct _cache_slot
{
  void*        owner;
  gint         version;
  gdouble      value;
};

struct _cache_slot cache[SIZE];

int
point_cache_fetch(void *owner, gdouble* ret, gsize idx)
{
   struct _cache_slot = cache[idx];

   gint version_start  = g_atomic_int_get(&(slot.version));
   void* slot_owner    = g_atomic_pointer_get(&(slot.owner));
   gdouble value       = slot.value;
   gint version_finish = g_atomic_int_get(&(slot.version));

   if ((version_start == version_finish) && (slot_owner == owner))
   {
     *ret = value;
     return 1;
   }
   else
   {
     return 0;
   }
}

void
point_cache_store(void *owner, gsize idx, gdouble value)
{
   struct slot = cache[idx];

   g_atomic_pointer_set(&(slot.owner), NULL);
   slot.version++;
   g_atomic_pointer_set(&(slot.owner), owner);
   slot.value = value;
}

I am trying to implement a shared cache for arrays. It must support two operations: set(owner, idx, value) and fetch(owner, idx) where idx is the index into the array and owner is an opaque handle to an owning object -- fetch(owner_1, idx) should return the value stored by set(owner_1, idx) only if the owner argument matches. The cache must be thread - safe but I do not want to rely on locking, i.e. mutexes. Failure in looking up cached values is fine - it is OK and expected that other threads will overwrite existing values in the shared cache, in which case fetch should just fail.

So the fetch operation has to read the cache slot's owner field to check against its argument, and if it matches return the cache slot's value field. The problem is, without locks, another thread could overwrite one of these fields during that operation. This approach tries to get around that by assigning a version field to each cache slot. It only increases. The fetch operation reads the version (atomically) at the start of the operation and at the end; if these are not the same, something changed during the read and the result is invalid, even if the owner field apparently matched.

The code below ensures that version is always incremented before value is updated, thus preventing fetch from returning a value from a different owner. (The functions g_atomic_... are provided by glib.) It "seems to work" - but can it be proven correct or incorrect?

struct _cache_slot
{
  void*        owner;
  gint         version;
  gdouble      value;
};

struct _cache_slot cache[SIZE];

int
point_cache_fetch(void *owner, gdouble* ret, gsize idx)
{
   struct _cache_slot *slot = &cache[idx];

   gint version_start  = g_atomic_int_get(&(slot->version));
   void* slot_owner    = g_atomic_pointer_get(&(slot->owner));
   gdouble value       = slot->value;
   gint version_finish = g_atomic_int_get(&(slot->version));

   if ((version_start == version_finish) && (slot_owner == owner))
   {
     *ret = value;
     return 1;
   }
   else
   {
     return 0;
   }
}

void
point_cache_store(void *owner, gsize idx, gdouble value)
{
   struct _cache_slot *slot = &cache[idx];

   g_atomic_pointer_set(&(slot->owner), NULL);
   slot->version++;
   g_atomic_pointer_set(&(slot->owner), owner);
   slot->value = value;
}