[concurrency-interest] Problem with using an unbounded map of Mutex lock objects
Joe Bowbeer
joe.bowbeer at gmail.com
Tue Jun 13 03:22:04 EDT 2006
Correction:
I wrote:
> If the hash function is random, then I think the sums should be
> normally distributed, in which case a fairly wide distribution is
> likely. (How unlikely is it that the sums all lie within +/- 20% of
> the mean?)
>
> The less normal the distribution, the less random the hash function,
> and the more likely it is that certain sets of data will amplify
> patterns inherent in the hash function, resulting in undesirable lock
> contention.
>
Scratch the bit about "normal distribution". It's probably not true
and it just confuses the issue anyway.
The point I'm trying to make is that a random number generator will
not typically produce hit counts within +/- 20% of the mean in only
5000 trials, so I think it's unreasonable to expect a hash function to
do that well.
(Is there a statistician in the house? With 128 buckets and 5000
random trials, how unlikely is it that the hit counts all lie within
+/- 20% of the mean?)
I corrected a bug in my code and added more info to the printout:
import java.security.SecureRandom;
import java.util.Random;
import java.util.SortedMap;
import java.util.TreeMap;
public class BucketTest {
public static final int NUM_BUCKETS = 128;
public static final int NUM_TRIALS = 5000;
public static void main(String[] args) {
Random rnd = new SecureRandom();
int[] bucket = new int[NUM_BUCKETS];
for (int n = NUM_TRIALS; --n >= 0; )
bucket[rnd.nextInt(bucket.length)]++;
int[] sum = new int[NUM_TRIALS];
for (int i = 0; i < bucket.length; i++)
sum[bucket[i]]++;
SortedMap<Integer, Integer> map =
new TreeMap<Integer, Integer>();
for (int i = 0; i < sum.length; i++)
if (sum[i] != 0)
map.put(i, sum[i]);
System.out.println(map);
double mean = (double) NUM_TRIALS / NUM_BUCKETS;
System.out.println(
((mean - map.firstKey()) * 100.0 / mean) + "% - " +
((map.lastKey() - mean) * 100.0 / mean) + "%");
}
}
run:
hit counts: {20=1, 27=4, ... , 53=1, 56=1}
range: 48.8% - 43.36%
--Joe
More information about the Concurrency-interest
mailing list