Avoid contention on reference count for readers

[jonhoo]

The current implementation has an Arc behind the atomic pointer to the currently active map. This is used by the writer to determine when there are no more readers present for the previous map when doing a refresh(). Unfortunately, this also leads to readers contending on the cache-line of that Arc, even when there are no writes.

evmap should move away from the Arc-based scheme to a solution that does not incur this cost (nor the extra pointer indirection that Arc introduces). We can do that by shifting more work onto the writer. The gist of the idea is that every reader will have a local epoch number, which they increment when they read from the map. After swapping, the writer will wait until it has seen the epoch number change for every reader, which ensures that every reader has moved on to the new map.

Specifically, WriteHandle and ReadHandle will both hold an Arc<Mutex<Vec<Arc<AtomicUsize>>>>. Whenever a ReadHandle is cloned, a new AtomicUsize will be allocated, and will be added to the Vec by taking the Mutex. This may seem as though it adds a lot of overhead, but notice that a) the outer Arc is only ever updated when a new Reader is created; b) the Mutex is only taken by readers when one is cloned — in the common case, only the writer is accessing it; and c) the Arc wrapping the AtomicUsize will always carry a reference count of 2, and will only be modified when a reader arrives or leaves (i.e., during creation and destruction). Note also that only the writer needs to use strong consistency when accessing the AtomicUsize; the readers can update it with Ordering::Relaxed.

It is worth noting that the scheme as described thus far encounters problems when a reader does a single read, and then never reads again. The writer will never observe its epoch number change, and thus will wait forever after doing a swap. To combat this, the per-reader AtomicUsize also includes a bit to indicate that the reader has finished its read. The writer can now ignore any reader epochs that are marked as "finished", since it knows they cannot be accessing the map through the old pointer.

This should significantly improve the read performance in situations where there are many fast readers, especially when working with many cores or on NUMA architectures. Implementation of this will likely not happen for a little while, as more pressing tasks are awaiting elsewhere, but at least we now have a plan.

[jonhoo]

Change seems promising thus far.