On 20/07/2018 03:25, Kris Maglione wrote:
On Thu, Jul 19, 2018 at 07:17:13PM -0700, Jeff Gilbert wrote:
Using a classic read/write exclusive lock, we would only every contend
on read+write or write+write, which are /rare/.
That might be true if we gave up on the idea of switching to Robin Hood
hashing. But if we don't, then every lookup is a potential write, which
means every lookup required a write lock.
I'm a bit puzzled by this statement, actually.... my understanding of
Robin Hood hashing (based on looking at a few articles; I don't claim
anything like in-depth study) is that it may move existing entries
during *insertion*, and potentially during *deletion* (if using a
backward-shift deletion approach, rather than tombstones), but *lookup*
operations wouldn't modify anything.
So we should be able to use Robin Hood hashing with an RWLock that
allows reading from multiple threads without contention; only writing
(which for prefs is pretty rare, I believe) would block other threads.
Or is there a more advanced version of the Robin Hood design, where
*lookup* also rearranges entries?
JK
_______________________________________________
dev-platform mailing list
dev-platform@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-platform
