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

Joe Bowbeer joe.bowbeer at gmail.com
Tue Jun 6 10:08:30 EDT 2006


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?

Plan B:

The hashcode for Strings is computed as:

  s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

For numeric keys, each s[i] will contain a digit '0' .. '9'

That is: 48 <= s[i] <= 57

So maybe this hash function already works well with a table size of 128?

Given the comments in HashMap and ConcurrentHashMap, however, I would
hesitate to use 2^N locks without using a hash spreader (or performing
further analysis on the hashcodes).


On 6/6/06, Greg Luck <gluck at gregluck.com> wrote:
>
> Joe
>
> 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%.
>
> See the following test. I have tried a couple different ways of generating
> keys which give much the same result. Note that BlockingCache is
> overwhelmingly used with
> database IDs which are number in similar ranges to the ones I am generating.
>
>    /**
>      * Tests that stripes are evently distributed
>      */
>     public void testStripingDistribution() {
>         int[] lockIndexes = new int[128];
>         for (int i = 0; i < 5000; i++) {
>             String key = new String("" + i * 3 / 2 + i);
>             key += key.hashCode();
>             int lock = blockingCache.selectLock(key);
>             lockIndexes[lock]++;
>         }
>
>         for (int i = 0; i < 128; i++) {
>             assertTrue("Lock index " + i + " outside of range: " +
> lockIndexes[i], 20 <= lockIndexes[i] && lockIndexes[i] <= 55);
>         }
>     }
>
>
>     /**
>      * Selects a lock for a key. The same lock is always used for a given
> key.
>      * @param key
>      * @return the selected lock index
>      */
>     int selectLock(final Object key) {
>         if (key == null) {
>             return 0;
>         } else {
>             int hash = hash(key) & (LOCK_NUMBER - 1);
>             return hash;
>         }
>
>     }
>
>
>     /**
>      * Returns a hash code for non-null Object x.
>      * Uses the same hash code spreader as most other java.util hash tables.
>      *
>      * @param object the object serving as a key
>      * @return the hash code
>      */
>     private int hash(Object object) {
>         int hashcode = object.hashCode();
>         hashcode += ~(hashcode << 9);
>         hashcode ^= (hashcode >>> 14);
>         hashcode += (hashcode << 4);
>         hashcode ^= (hashcode >>> 10);
>         return hashcode;
>     }
>
>
>
>
>
>
> On 06/06/2006, at 8:36 PM, Joe Bowbeer wrote:
>
>
> Greg,
>
> I'm disappointed you're not using the Future-based approach.  I was
> hoping you'd benchmark it and report back.  I'm interested to know how
> it performs :-)
>
> However, I can suggest a couple optimizations for your striping
> implementation.
>
> 1. Spread the bits in the hash code.
>
> ConcurrentHashMap spreads the hash with the following:
>
>     /**
>      * Returns a hash code for non-null Object x.
>      * Uses the same hash code spreader as most other java.util hash tables.
>      * @param x the object serving as a key
>      * @return the hash code
>      */
>     static int hash(Object x) {
>         int h = x.hashCode();
>         h += ~(h << 9);
>         h ^=  (h >>> 14);
>         h +=  (h << 4);
>         h ^=  (h >>> 10);
>         return h;
>     }
>
> Rationale: Hashcodes are generally unique, but they are not random.
> The method above disperses the bits, producing a more random
> distribution after division.
>
>
> 2. Require LOCK_NUMBER to be a power of two, such as 128.
>
> In this way, a binary AND (&) can replace division (/).
>
>
> Applying both of these to getLockForKey:
>
>    /**
>     * The default number of locks to use. Must be a power of 2.
>     */
>    protected static final int LOCK_NUMBER = 128;
>
>    private Mutex getLockForKey(final Serializable key) {
>        if (key == null)
>            return locks[0];
>        assert (LOCK_NUMBER & (LOCK_NUMBER-1)) == 0; // power of 2
>        int h = hash(key) & (LOCK_NUMBER-1);
>        return locks[h];
>    }
>
> --
> Joe ~ joebowbeer.thruhere.net
>


More information about the Concurrency-interest mailing list