[future] read/write furtex for dict and deque

[tiran]

dict and collections.deque is one of the few objects that are heavily utilized by multiple threads. Dicts are used for module name spaces. Module dicts are mostly read-only. threadings.Condition and the queue module use deque internally.

It makes sense to implement r/w locking to allow multiple concurrent readers.

[larryhastings]

deque doesn't need multiple readers. most operations on deques are "append" (write lock) and "pop" or "popleft" (write lock).

dict so far hasn't really needed multiple readers. x.py is a worst-case scenario for dict; it has seven threads looking up "fib" in the module dict over and over, and "fib" is a small recursive function. really it does very little else. the actual lookup is super-fast, so it doesn't hold the lock for very long, so even in this worst case contention is pretty low.

meanwhile, any kind of locking is going to add synchronization overhead. I don't know what % of the overhead of looking up "fib" in the module dict is pure synchronization overhead vs actual contention and waiting. my suspicion is it is primarily the former.

Dino said he can do the experiment pretty cheaply because his locks already support multiple readers. until I see some numbers that say "yes multiple reader locks are a win" it's not very high on my priority list.

[JustAMan]

We had a small discussion with Anton about that, and I think you had some, too, at the sprint. It seems to me that the implementation of r/w lock for a dictionay might not be an easy thing, because both read and write locks probably need to be recursive and it should be possible to hold both at the same time by a single thread (the case when some object sets a dict value during the process of getting some other value).

Implementing a r/w lock so it knows if the current thread is the only one reading so we can safely grab a write lock does not sound as something very easy to achieve.

I think I can play and try to prototype a naive approach (ignoring the issue above) to try and see if this gives us anything useful for x.py benchmark.