[concurrency-interest] Problem with using an unbounded map of Mutex lock objects

Joe Bowbeer joe.bowbeer at gmail.com
Mon Jun 12 20:55:42 EDT 2006


On 6/6/06, Joe Bowbeer <joe.bowbeer at gmail.com> wrote:
> On 6/6/06, Greg Luck <gluck at gregluck.com> wrote:
> >
> > I have tested the hash code spreader.  It performs noticeably poorer than
> > using key.hashCode(), which spread evenly with the full distribution within
> > +- 20%.
> > This new one is +- 49%.
> >
>
> Are you sure the hash spreader isn't increasing randomness, resulting
> in more bumps?  In other words, is smoother really better?
>

Follow-up:

I ran your test using a pseudo random number generator in place of a
hash function and found that ranges of +/- 50% or more are not
uncommon.  (I observed 19 <= count <= 61.)

This suggests that the hash-spreader *is* producing more random
assignments, as desired.

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 is 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.

    public static final int NUM_BUCKETS = 128;
    public static final int NUM_TRIALS = 5000;

    public static void main(String[] args) {
        Random rnd = new Random();
        int[] bucket = new int[NUM_BUCKETS];
        for (int n = NUM_TRIALS; --n >= 0; )
            bucket[rnd.nextInt(bucket.length)]++;
        int[] sum = new int[bucket.length];
        for (int i : bucket)
            sum[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);
    }

--Joe


More information about the Concurrency-interest mailing list