[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