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

Greg Luck gluck at gregluck.com
Tue Jun 6 08:51:50 EDT 2006


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
>
>
> On 6/6/06, Greg Luck <gluck at gregluck.com> wrote:
>>
>> Brian et al
>>
>> Thanks so much for everyone's contributions.
>>
>> I tested out Brian's lock striping with my suite of concurrency tests
>> (BlockingCacheTest in ehcache) which hammer BlockingCache with 100  
>> threads.
>> It seems to work very well.
>>
>> Mutex objects use 24 bytes so I opted to go for 100. That is 2400  
>> bytes in
>> total, way down from the tens of MBs that is common now in ehcache  
>> for large
>> systems.
>>
>> I also looked into the  allocation of locks for different keys. In  
>> the tests
>> I did for lock selection, locks were evenly selected +- 20%.
>>
>> In all this looks to be an excellent solution with minimal change  
>> to the
>> BlockingCache. The newly revised blocking cache is reproduced  
>> below. I would
>> appreciate anyone letting me know if there are any shortcomings in  
>> it.
>>
>> One point to note. In Brian's implementation, getLockForKey 
>> (Serializable
>> key) was synchronized. I think this is unncecessary and  
>> potentially harmful
>> to scalability. Mine is not synchronized.
>>
>> Finally thanks to Tim Peieris and others for alternate solutions.  
>> I don't
>> want to bring another lib at this time. One of the attractions of  
>> ehcache,
>> which I would like to preserve,  is the minimal dependencies.
>>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at altair.cs.oswego.edu
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
>



Regards

Greg Luck

web: http://gregluck.com
skype: gregrluck
yahoo: gregrluck
mobile: +61 408 061 622



-------------- next part --------------
An HTML attachment was scrubbed...
URL: /pipermail/attachments/20060606/f3b518cd/attachment-0001.html 


More information about the Concurrency-interest mailing list