dl at cs.oswego.edu
Mon Aug 29 20:20:49 EDT 2011
On 08/29/11 18:02, Charles Fry wrote:
> There are a few typos in the new compute javadocs:
Thanks! Fixed in next update.
> Also, it would be nice to document what "operations on this map by other threads
> may be blocked while computation is in progress." For example, I assume that get
> will never block on computation, but that any writes will.
Read-only operations (get, iterators, etc) never block at all.
Exactly which update operations block is a random phenomenon,
so left fuzzy. The number of entries covered by any given
node serving as a lock is, assuming lack of too many identical
hashCode values by different keys, approximately Poisson
distributed with, on average at steady state, a parameter
of about 0.5 under 0.75 loadFactor. On average, about 75%
of the locks cover exactly one entry, the rest cover two
or more. And roughly, the probability that
holding a given lock will block an unrelated update
is around 1/8n (n the number of elements). On the other hand,
holding the lock will always prevent an ongoing resize operation
from completing, which may cause bins to overpopulate and
overall throughput to degrade. So people should avoid
long computations that are performed within these locks.
Further digressing: Despite disadvantages, using locks
for statistically very short lists turns out to be much more
stable and efficient than alternative non-blocking strategies
I tried that also meet the design goal of supporting efficient
partitioning and traversability, which is needed for upcoming
parallel operations on maps.
More information about the Concurrency-interest