I found a fascinating paper on a lock free implementation of maps when I was looking for ways to implement a lock-free graph. Here is the link to the paper:
In summary, the main tool introduced is the concept of a hazard pointer, which is basically a single-writer, multiple reader, shared pointer. Basically when reading a map, a processor must first acquire a hazard pointer and store the mem-address of the map it is reading in memory. After the processor is done reading the map, it releases the hazard pointer.
To update the map, the writer processor will create a completely new map and store the old map in a retired map vector. Periodically, scans are performed through the vector to see if any of the current hazard pointer still point to each map in the retired set. If no pointers exists, then it is safe to delete the map.
The overhead of copying a map is not significant because the paper assumes that Map Reads are much more common than Map Writes.
I found a fascinating paper on a lock free implementation of maps when I was looking for ways to implement a lock-free graph. Here is the link to the paper:
http://erdani.com/publications/cuj-2004-12.pdf
In summary, the main tool introduced is the concept of a hazard pointer, which is basically a single-writer, multiple reader, shared pointer. Basically when reading a map, a processor must first acquire a hazard pointer and store the mem-address of the map it is reading in memory. After the processor is done reading the map, it releases the hazard pointer.
To update the map, the writer processor will create a completely new map and store the old map in a retired map vector. Periodically, scans are performed through the vector to see if any of the current hazard pointer still point to each map in the retired set. If no pointers exists, then it is safe to delete the map.
The overhead of copying a map is not significant because the paper assumes that Map Reads are much more common than Map Writes.
This comment was marked helpful 1 times.