callumbirks
commented
3 months ago In the Concurrent Hash Tables paper, there is a section on "Complex Key and Value Types". This section describes the hash table allocating space for larger keys and values, and using pointers to those. This is similar to what we already do for keys.
The issue is, to keep folklore's current update operation, the value pointer would need to be updated. However, we'd be unable to delete the previous value, as we can't do so atomically. This means value updates would cause memory leaks. The paper describes how to handle this, which is to use the table's migration protocols to delete unused keys and values.
Therefore, if we want to support larger values, we will first need to support deletions and migrations.
By using the same structure as the key store (ConcurrentArray) for a Value store, we can allow for values of any size. To avoid the potentially increased size for users who only need 2-byte values, could ignore the value store if size_of == 2.