commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From robert burrell donkin <robertburrelldon...@blueyonder.co.uk>
Subject Re: [logging]: WeakHashtable
Date Mon, 15 Nov 2004 20:49:36 GMT
hi brian

sorry i haven't got back early (didn't seem to stop all weekend). been  
a bit embarrassed since (after sleeping on the code i last committed) i  
released that reference queues were a more efficient approach but that  
i wasn't going to have the time to fix it before anyone noticed ;)

i've taken a first pass through your emails and i'll definitely be  
drafting replies but i'm not sure how much time i'll get tonight (and i  
might need to sleep on the code...)

- robert

On 15 Nov 2004, at 04:12, Brian Stansberry wrote:

> I've attached a patch that adds a couple more tests
> and fixes a problem found by one of them.  New test
> LogFactoryTest.testHoldsFactories() shows that
> WeakHashtable does not keep a LogFactory from being
> gc'ed even if the ClassLoader associated with it is
> still alive.  So, calls to LogFactory.getFactory()
> result in new factories being created.  The patch to
> WeakHashtable is largely designed to fix that.
>
> The patched WeakHashtable holds values in the table
> until the WeakReference to the associated ClassLoader
> is removed, even if the classloader itself has been
> gc'ed.  Because of this, the potential amount of
> garbage left in the table is greater than it was
> before.  The patch partly tries to remedy that by
> doing a purge before each rehash.
>
> The patch also switches the purge mechanism to one
> that uses a ReferenceQueue.  This should be more
> performant, as it allows the purging process to only
> deal with items (if any) that definitely need to be
> removed from the hashtable, rather than iterating
> through all entries in the map.  ReferenceQueue.poll()
> itself is quite fast, basically consisting of popping
> off the first element in a linked list.
>
> In this patch the way LogFactories are kept from being
> dropped from the hashtable is not ideal.  Basically
> the keys in the map hold hard references to the
> LogFactories, keeping the WeakReferences to the
> LogFactories from being cleared.  This approach is a
> leftover remnant of a failed attempt on my part at
> getting the hashtable itself to clear unneeded
> factories without the need for a call to purge().  It
> would be much cleaner to just have the hashtable hold
> normal hard references to the LogFactories.  I didn't
> include such a change in this patch as 1) it may have
> made the patch overly complicated, and 2) I didn't
> have time ;-)  If the powers that be agree that the
> LogFactories should be held directly by the Hashtable,
> I would be happy to create another patch.
>
> (Also, there's some funky stuff in the test cases
> where I try to handle OutOfMemoryError.  It works on
> my environment (Eclipse 3.0, Sun JDK 1.4.2_03), but if
> others have thoughts about this, they would be much
> appreciated).
>
> Best,
> Brian
>
> --- Brian Stansberry <bes_commons_dev@yahoo.com>
> wrote:
>
>> --- robert burrell donkin  wrote:
>>
>>>
>>> On 11 Nov 2004, at 07:40, Brian Stansberry wrote:>
>>
>>>>  A couple things occurred to me as I looked.
>>>>  
>>>> 1)  The instances of Referenced are not cleared
>>> from the underlying
>>>> table if their underlying references are
>> cleared.
>>>> 2)  Passing null keys/values to put() does not
>>> result in a NPE.
>>>>
>>>> One thought on #1 is to make Referenced a
>> subclass
>>> of WeakReference
>>>> instead of a wrapper.  You can then keep a
>>> ReferenceQueue and poll it
>>>> to remove cleared references from the hashtable
>>> whenever get() is
>>>> called.  This is similar to what WeakHashMap
>> does.
>>>
>>> i had a bit of a think about the best way to do
>>> this. i think the
>>> approach outlined would be best if this were a
>>> general implementation.
>>> in this case, though, the majority of calls are
>>> going to be to get with
>>> somewhat less going to put and very few to any
>>> others. i can't think of
>>> any occasions when the symantics of put and get
>> are
>>> influenced by the
>>> presence of extra entries. so i've opted for code
>>> that simply purges
>>> entries that have lost their referants which is
>>> called at the start of
>>> other interrogative methods. the data returned
>> will
>>> be more stale than
>>> using a reference queue but i think that
>> liveliness
>>> for put and get should be improved.
>>>
>> Yep, slowing down the critical get() just to sweep
>> up
>> some dust in the corners makes no sense.
>>
>>> i'd be grateful if people would take a look at the
>>> code and try to find
>>> any holes in this approach or reasons why using a
>>> ReferenceQueue might
>>> improve liveliness (preferably with patches)...
>>
>> I was thinking about this and concluded that the
>> approach of iterating the Hashtable.entrySet() would
>> be faster since you're checking if either the key or
>> the value has been cleared.  Using a ReferenceQueue
>> for values would force you to use a reverse lookup
>> map, which seems inefficient.
>>
>> But then I thought, wait, should the values be held
>> in
>> WeakReferences?  In a typical case where the
>> application just calls LogFactory.getLog(), won't
>> the
>> only reference to the LogFactory instance be the
>> value
>> in the map?  In this case a lot of calls to getLog()
>> will end up going through the getFactory() discovery
>> mechanism as the GC keeps clearing the values from
>> the
>> hashtable.
>>
>>
>> Brian
>>
>>
>> 		
>> __________________________________
>> Do you Yahoo!?
>> Check out the new Yahoo! Front Page.
>> www.yahoo.com
>>
>>
>>
>>
> ---------------------------------------------------------------------
>> To unsubscribe, e-mail:
>> commons-dev-unsubscribe@jakarta.apache.org
>> For additional commands, e-mail:
>> commons-dev-help@jakarta.apache.org
>>
>>
>
>
>
>
> 		
> __________________________________
> Do you Yahoo!?
> Check out the new Yahoo! Front Page.
> www.yahoo.com
>
> Index:  
> optional/src/java/org/apache/commons/logging/impl/WeakHashtable.java
> ===================================================================
> RCS file:  
> /home/cvspublic/jakarta-commons/logging/optional/src/java/org/apache/ 
> commons/logging/impl/WeakHashtable.java,v
> retrieving revision 1.3
> diff -u -r1.3 WeakHashtable.java
> ---  
> optional/src/java/org/apache/commons/logging/impl/WeakHashtable.java	 
> 11 Nov 2004 22:31:05 -0000	1.3
> +++  
> optional/src/java/org/apache/commons/logging/impl/WeakHashtable.java	 
> 15 Nov 2004 01:43:31 -0000
> @@ -17,6 +17,7 @@
>
>  package org.apache.commons.logging.impl;
>
> +import java.lang.ref.ReferenceQueue;
>  import java.lang.ref.WeakReference;
>  import java.util.*;
>
> @@ -37,12 +38,29 @@
>   * running 1.3+ JVMs. Use of this class will allow classloaders to be  
> collected by
>   * the garbage collector without the need to call release.
>   * </p>
> + *
> + * @author Brian Stansberry
>   */
>  public final class WeakHashtable extends Hashtable {
>
>      /** Empty array of <code>Entry</code>'s */
>      private static final Entry[] EMPTY_ENTRY_ARRAY = {};
>
> +    /**
> +     * The maximum number of times put() can be called before
> +     * the map will purged of cleared entries.
> +     */
> +    public static final int MAX_PUTS_BEFORE_PURGE = 100;
> +
> +    /* ReferenceQueue we check for gc'd keys */
> +    private ReferenceQueue queue = new ReferenceQueue();
> +    /* Counter used to control how often we purge gc'd entries */
> +    private int putCount = 0;
> +
> +    /**
> +     * Constructs a WeakHashtable with the Hashtable default
> +     * capacity and load factor.
> +     */
>      public WeakHashtable() {}
>
>      /**
> @@ -120,7 +138,7 @@
>       *@see Hashtable
>       */
>      public Object get(Object key) {
> -        // for performance reasons, no purge
> +        // for performance reasons, no purge
>          Object result = null;
>          Referenced referenceKey = new Referenced(key);
>          Referenced referencedValue = (Referenced)  
> super.get(referenceKey);
> @@ -169,7 +187,6 @@
>       *@see Hashtable
>       */
>      public Object put(Object key, Object value) {
> -        // for performance reasons, no purge
>          // check for nulls, ensuring symantics match superclass
>          if (key == null) {
>              throw new NullPointerException("Null keys are not  
> allowed");
> @@ -177,9 +194,18 @@
>          if (value == null) {
>              throw new NullPointerException("Null values are not  
> allowed");
>          }
> +
> +        // for performance reasons, only purge every
> +        // MAX_PUTS_BEFORE_PURGE times
> +        if (putCount++ > MAX_PUTS_BEFORE_PURGE) {
> +            purge();
> +            putCount = 0;
> +        }
>
>          Object result = null;
> -        Referenced lastValue = (Referenced) super.put(new  
> Referenced(key), new Referenced(value));
> +        Referenced keyRef    = new Referenced(key, value, queue);
> +        Referenced valueRef  = new Referenced(value);
> +        Referenced lastValue = (Referenced) super.put(keyRef,  
> valueRef);
>          if (lastValue != null) {
>              result = lastValue.getValue();
>          }
> @@ -248,22 +274,23 @@
>      }
>
>      /**
> -     * Purges all entries whose wrapped keys or values
> +     * @see Hashtable
> +     */
> +    protected void rehash() {
> +        // purge here to save the effort of rehashing dead entries
> +        purge();
> +        super.rehash();
> +    }
> +
> +    /**
> +     * Purges all entries whose wrapped keys
>       * have been garbage collected.
>       */
>      private synchronized void purge() {
> -        Set entrySet = super.entrySet();
> -        for (Iterator it=entrySet.iterator(); it.hasNext();) {
> -            Map.Entry entry = (Map.Entry) it.next();
> -            Referenced referencedKey = (Referenced) entry.getKey();
> -            Referenced referencedValue = (Referenced)  
> entry.getValue();
> -
> -            // test whether either referant has been collected
> -            if (referencedKey.getValue() == null ||  
> referencedValue.getValue() == null) {
> -                // if so, purge this entry
> -                it.remove();
> -            }
> -        }
> +       WeakKey key;
> +       while ( (key = (WeakKey) queue.poll()) != null) {
> +           super.remove(key.getReferenced());
> +       }
>      }
>
>
> @@ -318,18 +345,32 @@
>      private final static class Referenced {
>
>          private final WeakReference reference;
> +        private final int           hashCode;
>
> +        /**
> +         *
> +         * @throws NullPointerException if referant is  
> <code>null</code>
> +         */
>          private Referenced(Object referant) {
>              reference = new WeakReference(referant);
> +            // Calc a permanent hashCode so calls to  
> Hashtable.remove()
> +            // work if the WeakReference has been cleared
> +            hashCode  = referant.hashCode();
> +        }
> +
> +        /**
> +         *
> +         * @throws NullPointerException if key is <code>null</code>
> +         */
> +        private Referenced(Object key, Object value, ReferenceQueue  
> queue) {
> +            reference = new WeakKey(key, value, queue, this);
> +            // Calc a permanent hashCode so calls to  
> Hashtable.remove()
> +            // work if the WeakReference has been cleared
> +            hashCode  = key.hashCode();
>          }
>
>          public int hashCode() {
> -            int result = 0;
> -            Object keyValue = getValue();
> -            if (keyValue != null) {
> -                result = keyValue.hashCode();
> -            }
> -            return result;
> +            return hashCode;
>          }
>
>          private Object getValue() {
> @@ -342,8 +383,21 @@
>                  Referenced otherKey = (Referenced) o;
>                  Object thisKeyValue = getValue();
>                  Object otherKeyValue = otherKey.getValue();
> -                if (thisKeyValue == null) {
> +                if (thisKeyValue == null) {
>                      result = (otherKeyValue == null);
> +                    // Since our hashcode was calculated from the  
> original
> +                    // non-null referant, the above check breaks the
> +                    // hashcode/equals contract, as two cleared  
> Referenced
> +                    // objects could test equal but have different  
> hashcodes.
> +                    // We can reduce (not eliminate) the chance of  
> this
> +                    // happening by comparing hashcodes.
> +                    if (result == true) {
> +                        result = (this.hashCode() ==  
> otherKey.hashCode());
> +                    }
> +                    // In any case, as our c'tor does not allow null  
> referants
> +                    // and Hashtable does not do equality checks  
> between
> +                    // existing keys, normal hashtable operations  
> should never
> +                    // result in an equals comparison between null  
> referants
>                  }
>                  else
>                  {
> @@ -352,5 +406,47 @@
>              }
>              return result;
>          }
> +    }
> +
> +    /**
> +     * WeakReference subclass that holds a hard reference to an
> +     * associated <code>value</code> and also makes accessible
> +     * the Referenced object holding it.
> +     */
> +    private final static class WeakKey extends WeakReference {
> +
> +        private Object     hardValue;
> +        private Referenced referenced;
> +
> +        private WeakKey(Object key,
> +                        Object value,
> +                        ReferenceQueue queue,
> +                        Referenced referenced) {
> +            super(key, queue);
> +            hardValue = value;
> +            this.referenced = referenced;
> +        }
> +
> +        private Referenced getReferenced() {
> +            return referenced;
> +        }
> +
> +        /* Drop our hard reference to value if we've been cleared
> +         * by the gc.
> +         *
> +         * Testing shows that with key objects like ClassLoader
> +         * that don't override hashCode(), get() is never
> +         * called once the key is in a Hashtable.
> +         * So, this method override is commented out.
> +         */
> +        //public Object get() {
> +        //    Object result = super.get();
> +        //    if (result == null) {
> +        //        // We've been cleared, so drop our hard reference  
> to value
> +        //        hardValue = null;
> +        //    }
> +        //    return result;
> +        //}
> +
>      }
>  }
> Index: optional/src/test/org/apache/commons/logging/LogFactoryTest.java
> ===================================================================
> RCS file:  
> /home/cvspublic/jakarta-commons/logging/optional/src/test/org/apache/ 
> commons/logging/LogFactoryTest.java,v
> retrieving revision 1.1
> diff -u -r1.1 LogFactoryTest.java
> ---  
> optional/src/test/org/apache/commons/logging/LogFactoryTest.java	10  
> Nov 2004 22:59:39 -0000	1.1
> +++  
> optional/src/test/org/apache/commons/logging/LogFactoryTest.java	15  
> Nov 2004 01:43:31 -0000
> @@ -17,8 +17,12 @@
>
>  package org.apache.commons.logging;
>
> -import junit.framework.*;
> -import java.util.*;
> +import java.lang.ref.WeakReference;
> +import java.util.Hashtable;
> +
> +import junit.framework.TestCase;
> +
> +import org.apache.commons.logging.impl.LogFactoryImpl;
>  import org.apache.commons.logging.impl.WeakHashtable;
>
>  public class LogFactoryTest extends TestCase {
> @@ -27,6 +31,8 @@
>      /** Maximum number of iterations before our test fails */
>      private static final int MAX_GC_ITERATIONS = 50;
>
> +    private ClassLoader origLoader          = null;
> +    private String      origFactoryProperty = null;
>
>      public LogFactoryTest(String testName) {
>          super(testName);
> @@ -35,4 +41,170 @@
>      public void testLogFactoryType() {
>          assertTrue(LogFactory.factories instanceof WeakHashtable);
>      }
> +
> +    /**
> +     * Tests that LogFactories are not removed from the map
> +     * if their creating ClassLoader is still alive.
> +     */
> +    public void testHoldFactories()
> +    {
> +        // Get a factory and create a WeakReference to it that
> +        // we can check to see if the factory has been removed
> +        // from LogFactory.properties
> +        LogFactory factory = LogFactory.getFactory();
> +        WeakReference weakFactory = new WeakReference(factory);
> +
> +        // Remove any hard reference to the factory
> +        factory = null;
> +
> +        // Run the gc, confirming that the original factory
> +        // is not dropped from the map even though there are
> +        // no other references to it
> +        int iterations = 0;
> +        int bytz = 2;
> +        while(iterations++ < MAX_GC_ITERATIONS) {
> +            System.gc();
> +
> +            assertNotNull("LogFactory released while ClassLoader  
> still active.",
> +                          weakFactory.get());
> +
> +            // create garbage:
> +            byte[] b;
> +            try {
> +              b  =  new byte[bytz];
> +              bytz = bytz * 2;
> +            }
> +            catch (OutOfMemoryError oom) {
> +                // This error means the test passed, as it means the  
> LogFactory
> +                // was never released.  So, we have to catch and deal  
> with it
> +
> +                // Doing this is probably a no-no, but it seems to  
> work ;-)
> +                b = null;
> +                System.gc();
> +                break;
> +            }
> +        }
> +    }
> +
> +    /**
> +     * Tests that a LogFactory is eventually removed from the map
> +     * after its creating ClassLoader is garbage collected.
> +     */
> +    public void testReleaseFactories()
> +    {
> +        // Create a temporary classloader
> +        ClassLoader childLoader = new ClassLoader() {};
> +        Thread.currentThread().setContextClassLoader(childLoader);
> +
> +        // Get a factory using the child loader.
> +        LogFactory factory        = LogFactory.getFactory();
> +        // Hold a WeakReference to the factory. When this reference
> +        // is cleared we know the factory has been cleared from
> +        // LogFactory.factories as well
> +        WeakReference weakFactory = new WeakReference(factory);
> +
> +        // Get a WeakReference to the child loader so we know when it
> +        // has been gc'ed
> +        WeakReference weakLoader = new WeakReference(childLoader);
> +
> +        // Remove any hard reference to the childLoader and the  
> factory
> +        Thread.currentThread().setContextClassLoader(origLoader);
> +        childLoader = null;
> +        factory     = null;
> +
> +        // Run the gc, confirming that the original childLoader
> +        // is dropped from the map
> +        int iterations = 0;
> +        int bytz = 2;
> +        while(true) {
> +            System.gc();
> +            if(iterations++ > MAX_GC_ITERATIONS){
> +                fail("Max iterations reached before childLoader  
> released.");
> +            }
> +
> +            if(weakLoader.get() == null) {
> +                break;
> +            } else {
> +                // create garbage:
> +                byte[] b;
> +                try {
> +                    b =  new byte[bytz];
> +                    bytz = bytz * 2;
> +                }
> +                catch (OutOfMemoryError oom) {
> +                    // Doing this is probably a no-no, but it seems  
> to work ;-)
> +                    b = null;
> +                    System.gc();
> +                    fail("OutOfMemory before childLoader released.");
> +                }
> +            }
> +        }
> +
> +        // Confirm that the original factory is removed from the map
> +        // within the maximum allowed number of calls to put() +
> +        // the maximum number of subsequent gc iterations
> +        iterations = 0;
> +        while(true) {
> +            System.gc();
> +            if(iterations++ > WeakHashtable.MAX_PUTS_BEFORE_PURGE +  
> MAX_GC_ITERATIONS){
> +                Hashtable table = LogFactory.factories;
> +                fail("Max iterations reached before factory  
> released.");
> +            }
> +
> +            // Create a new child loader and use it to add to the map.
> +            ClassLoader newChildLoader  = new ClassLoader() {};
> +             
> Thread.currentThread().setContextClassLoader(newChildLoader);
> +            LogFactory.getFactory();
> +            Thread.currentThread().setContextClassLoader(origLoader);
> +
> +            if(weakFactory.get() == null) {
> +                break;
> +            } else {
> +                // create garbage:
> +                byte[] b;
> +                try {
> +                    b =  new byte[bytz];
> +                    bytz = bytz * 2;
> +                }
> +                catch (OutOfMemoryError oom) {
> +                    // Doing this is probably a no-no, but it seems  
> to work ;-)
> +                    b = null;
> +                    bytz = 2; // start over
> +                    System.gc();
> +                }
> +            }
> +        }
> +
> +    }
> +
> +    protected void setUp() throws Exception {
> +        // Preserve the original classloader and factory  
> implementation
> +        // class so we can restore them when we are done
> +        origLoader          =  
> Thread.currentThread().getContextClassLoader();
> +        origFactoryProperty =  
> System.getProperty(LogFactory.FACTORY_PROPERTY);
> +
> +        // Ensure we use LogFactoryImpl as our factory
> +        System.setProperty(LogFactory.FACTORY_PROPERTY,
> +                           LogFactoryImpl.class.getName());
> +
> +        super.setUp();
> +    }
> +
> +    protected void tearDown() throws Exception {
> +        // Set the  classloader back to whatever it originally was
> +        Thread.currentThread().setContextClassLoader(origLoader);
> +
> +        // Set the factory implementation class back to
> +        // whatever it originally was
> +        if (origFactoryProperty != null) {
> +            System.setProperty(LogFactory.FACTORY_PROPERTY,
> +                               origFactoryProperty);
> +        }
> +        else {
> +             
> System.getProperties().remove(LogFactory.FACTORY_PROPERTY);
> +        }
> +
> +        super.tearDown();
> +    }
> +
>  }
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: commons-dev-help@jakarta.apache.org

---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org


Mime
View raw message