On Tue, Jan 7, 2014 at 12:42 PM, Rajiv Kurian <[email protected]> wrote:
> I am trying to design a lock-free or close to lock-free hash map of int keys
> and int values. I have a single writer thread that writes to the hash-map.
> My efforts to do better than a RW mutex around the map haven't yielded
> anything good. My gut feeling says I should be able to do better given it's
> a single writer. I have the following requirements:
>
> 1) A single-writer multiple reader map of int keys and int values.
> 2) Keys are guaranteed to be monotonically increasing. These are just ids
> and are generated by incrementing an integer.
> 3) The operations I need are:
>
> append(key, value) where key is guaranteed to be higher than anything in the
> map so far - only called on the writer thread.
> delete(key) - only called on the writer thread.
> set(key, value) where key is required to be already in the map - only called
> on the writer thread.
> get(key) - could be called by writer/reader threads.
>
> 4) All the reader threads and the single writer thread are known during the
> creation of the map. Reader threads do not pop up or die. They stay constant
> for the lifetime of the application.
>
> I am struggling to use anything cheaper than RW locks (changed for a single
> writer) for the implementation since the delete and append operations could
> require resizing of buckets or moving elements around and the reader threads
> could observe the changes in between.
>
> Any pointers?
Hi!
The most efficient solution is always tailored to your particular
situation. Lots of details matter. In particular in this case: 1. what
is the number of reader threads? 2. what is the relative frequencies
of different operations?
Also the fastest way to do something is to not do it all.
Can you replace integers with pointers? Even if you send them across
network, you can verify that the received pointer is valid before
using it, e.g:
#define MAX_OBJECT_IN_FLIGHT (1<<20)
object_t objects[MAX_OBJECT_IN_FLIGHT];
bool verify_pointer(object_t *o) {
if(o < objects || o >= objects + MAX_OBJECT_IN_FLIGHT)
return false;
if(((uintptr)o - (uintptr)objects) % sizeof(object_t))
return false;
// OK, this is a valid pointer into objects.
// A client can spoof it, but he can spoof the integer as well.
return true;
}
--
Then if you can limit the difference between the newest and the oldest
object, then you can use a ring buffer with direct indexing. If a
reader asks for a very old object (older than the threshold), then,
sorry, no luck.
--
If you can not afford to reject requests for very old ids, but you
expect them to not happen in common case, then you can have fast path
for recent ids and slow path for older ids. E.g.:
// We do not expect to receive requests for ids older than this
#define N (1<<20)
struct table_element {
int key;
int val;
table_element_slow* slow;
};
table_element table[N];
int find(int key) {
int idx = key % N;
table_element* e = &table[idx];
if(e->key == key)
return val;
// consult e->slow
// this can be slow, but we do not expect this to happen in common case
}
This needs special care wrt atomic accesses to key/val, and also some
protection for slow, and other details. But I hope the idea is clear.
--
There can be other "special" solutions.
It all these cases, accesses are extremely fast in common case.
If that does not work for you, then I would consider taking a normal
hashmap, partitioning it into lots of partitions and protecting each
partition with own rw mutex. On top of that you can have a mutex for
each thread/partition, readers lock own mutex but the writer need to
lock mutexes of all threads. This will eliminate contention between
readers, but make writer slower. Since you know number of readers
ahead of time, this must be really simple to implement.
--
Dmitry Vyukov
All about lockfree/waitfree algorithms, multicore, scalability,
parallel computing and related topics:
http://www.1024cores.net
--
---
You received this message because you are subscribed to the Google Groups
"Scalable Synchronization Algorithms" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/lock-free/CAEeQi3sUtknNXtnKiPZwdWeRGjDiU3wWYLjMMcoR3oevQR4gcQ%40mail.gmail.com.
For more options, visit https://groups.google.com/groups/opt_out.
