commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Aaron Smuts" <aaron.smu...@verizon.net>
Subject RE: Serious problem with MRUMap -- JCS LRU and MRUMap -- FW: cvs commit: jakarta-turbine-stratum/src/java/org/apache/stratum/util/lru LRUStore.java LRUElementDescriptor.java LRUElement.java ILRUElement.java
Date Fri, 01 Feb 2002 04:04:03 GMT
I added a better map storage to stratum.

-----Original Message-----
From: asmuts@apache.org [mailto:asmuts@apache.org] 
Sent: Thursday, January 31, 2002 10:56 PM
To: jakarta-turbine-stratum-cvs@apache.org
Subject: cvs commit:
jakarta-turbine-stratum/src/java/org/apache/stratum/util/lru
LRUStore.java LRUElementDescriptor.java LRUElement.java ILRUElement.java

asmuts      02/01/31 19:55:54

  Added:       src/java/org/apache/stratum/util/lru LRUStore.java
                        LRUElementDescriptor.java LRUElement.java
                        ILRUElement.java
  Log:
  Added this LRUStore pulled form JCS so it can be used by other
programs.
  Not sure this is where it belongs, but it can be moved.  It has O(1)
performance degredation and doesn't suffer from the O(N) limitations of
the LinkedList LRU implementations.
  
  It comes with a partial removal and a waterfall method.  it can be
overridden and so can the element wrapper, so the system is extendable.
you could extend the wrapper, override the put and use the
get(key,container) to get the wrapper if it had more info.
  
  Revision  Changes    Path
  1.1
jakarta-turbine-stratum/src/java/org/apache/stratum/util/lru/LRUStore.ja
va
  
  Index: LRUStore.java
  ===================================================================
  package org.apache.stratum.util.lru;
  
  import java.io.IOException;
  import java.io.Serializable;
  
  import java.util.HashMap;
  import java.util.Hashtable;
  import java.util.Iterator;
  import java.util.Map;
  import java.util.Set;
  
  import java.util.Map.Entry;
  
  import org.apache.stratum.util.lru.LRUElementDescriptor;
  
  /////////////////////////////////////////////////////
  /**
   *  Example LRU program with O(1) performance degredation. Partial
removal has
   *  O(N) performance. A fast reference management system. The least
recently
   *  used items move to the end of the list and get waterfalled.
   *
   *  Pulled from JCS project.  Based on several generic algorithm book
examples.
   *
   *@author     asmuts
   *@created    January 31, 2002
   */
  public class LRUStore implements Serializable
  {
  
      private final static boolean debugcmd = false;
      // removal
      private final static boolean debugR = false;
      //true;
  
      private final static String NAME_COMPONENT_DELIMITER = ":";
  
      /**
       *  Description of the Field
       */
      protected Map map = new Hashtable();
  
      // LRU double linked list
      private LRUElementDescriptor first;
      private LRUElementDescriptor last;
  
      private int max = 1000;
  
      // make configurable
      private int chunkSize = 5;
  
  
 
////////////////////////////////////////////////////////////////////
      // for reflection
      /**
       *  Constructor for the LRUStore object
       */
      public LRUStore()
      {
          // might want to consider this an error state
          //status = this.STATUS_ERROR;
      }
  
      // should use this method
  
      /**
       *  Constructor for the LRUStore object
       *
       *@param  max  Description of the Parameter
       */
      public LRUStore( int max )
      {
          initialize( max );
      }
  
  
      // for post reflection creation initialization
      /**
       *  Description of the Method
       *
       *@param  max  Maximum number of elements in LRUStore
       */
      public void initialize( int max )
      {
          this.max = max;
      }
  
      /**
       *  Puts an item to the LRUStore.
       *
       *@param  ce               Description of the Parameter
       */
      public void update( ILRUElement ce )
      {
  
          addFirst( ce );
          LRUElementDescriptor old = ( LRUElementDescriptor ) map.put(
ce.getKey(), first );
  
          if ( first.equals( old ) )
          {
              // the same as an existing item.
              removeNode( old );
          }
  
          // save a microsecond on the second call.
          int size = map.size();
          // need to spool at a certain percentage synchronously
          if ( size < max )
          {
              return;
          }
          else
          {
  
              // SPOOL LAST -- need to make this a grouping in a queue
              if ( debugcmd )
              {
                  p( "IN RAM overflow" );
              }
  
              // write the last item to disk.
              try
              {
  
                  // PUSH 5 TO DISK TO MINIMIZE THE TYPICAL
                  int chunkSizeCorrected = Math.min( size, chunkSize );
  
                  if ( debugcmd )
                  {
                      p( "update: About to dump , map.size() = " + size
+ ", max = " + max + ", chunkSizeCorrected = " + chunkSizeCorrected );
                  }
  
                  // The spool will put them in a disk event queue, so
there is no
                  // need to pre-queue the queuing.  This would be a bit
wasteful
                  // and wouldn't save much time in this synchronous
call.
                  for ( int i = 0; i < chunkSizeCorrected; i++ )
                  {
                      // Might want to rename this "overflow" incase the
hub
                      // wants to do something else.
                      waterfall( last.ce );
                      map.remove( last.ce.getKey() );
                      removeNode( last );
                  }
  
                  if ( debugcmd )
                  {
                      p( "update: After spool, put " + last.ce.getKey()
+ " on disk cache, map.size() = " + size + ", max) = " + this.max + ",
chunkSizeCorrected = " + chunkSizeCorrected );
                  }
  
              }
              catch ( Exception ex )
              {
                  // impossible case.
                  ex.printStackTrace();
                  throw new IllegalStateException( ex.getMessage() );
              }
  
          }
  
      }
      // end update
  
      // TODO: Implement or modify interface, just implement
      // may need insert if we want to distinguish b/wn put and replace
      /**
       *  Description of the Method
       *
       *@param  key              Description of the Parameter
       *@param  val              Description of the Parameter
       */
      public void put( Serializable key, Serializable val )
      {
          LRUElement le = new LRUElement( key, val );
          update( le );
      }
  
  
      /**
       *  Gets an item from the cache.
       *
       *@param  key              Description of the Parameter
       *@return                  Description of the Return Value
       */
      public Serializable get( Serializable key )
      {
          return get( key, false );
      }
  
  
      /**
       *  Description of the Method
       *
       *@param  key              Description of the Parameter
       *@param  container        Description of the Parameter
       *@return                  Description of the Return Value
       */
      public Serializable get( Serializable key, boolean container )
      {
  
          LRUElementDescriptor me = null;
          ILRUElement ce = null;
          boolean found = false;
  
          try
          {
  
              me = ( LRUElementDescriptor ) map.get( key );
  
              if ( me == null )
              {
  
              }
              else
              {
                  found = true;
                  ce = me.ce;
              }
  
          }
          catch ( Exception e )
          {
              //log.error( e );
          }
  
          try
          {
  
              if ( !found )
              {
                  return null;
              }
          }
          catch ( Exception e )
          {
              //log.error( e, "Error handling miss" );
              return null;
          }
  
          try
          {
              makeFirst( me );
          }
          catch ( Exception e )
          {
              //log.error( e, "Error making first" );
              return null;
          }
  
          if ( container )
          {
              return ce;
          }
          else
          {
              return ce.getVal();
          }
  
      }
      // end get
  
      /**
       *  Removes an item from the cache.
       *
       *@param  key              Description of the Parameter
       *@return                  Description of the Return Value
       *@exception  IOException  Description of the Exception
       */
      public boolean remove( Serializable key )
          throws IOException
      {
  
          //p("remove> key="+key+", nonLocal="+nonLocal);
          boolean removed = false;
  
          // handle partial removal
          if ( key instanceof String && key.toString().endsWith(
NAME_COMPONENT_DELIMITER ) )
          {
              // remove all keys of the same name hierarchy.
              synchronized ( map )
              {
                  for ( Iterator itr = map.entrySet().iterator();
itr.hasNext();  )
                  {
                      Map.Entry entry = ( Map.Entry ) itr.next();
                      Object k = entry.getKey();
                      if ( k instanceof String &&
k.toString().startsWith( key.toString() ) )
                      {
                          itr.remove();
                          removeNode( ( LRUElementDescriptor )
entry.getValue() );
                          removed = true;
                      }
                  }
              }
          }
          else
          {
              // remove single item.
              LRUElementDescriptor ce = ( LRUElementDescriptor )
map.remove( key );
              if ( ce != null )
              {
                  removeNode( ce );
                  removed = true;
              }
          }
          // end else not hierarchical removal
          return removed;
      }
  
  
      /**
       *  Removes all cached items from the cache.
       *
       *@exception  IOException  Description of the Exception
       */
      public void removeAll()
          throws IOException
      {
          map = new HashMap();
      }
  
  
      /**
       *  Prepares for shutdown.
       *
       *@exception  IOException  Description of the Exception
       */
      public void dispose()
          throws IOException
      {
      }
  
  
      /**
       *  Returns the cache statistics.
       *
       *@return    The stats value
       */
      public String getStats()
      {
          return "";
      }
  
  
      /**
       *  Returns the current cache size.
       *
       *@return    The size value
       */
      public int getSize()
      {
          return this.map.size();
      }
  
  
      /**
       *  Returns the cache status.
       *
       *@return    The status value
       */
      public int getStatus()
      {
          //return this.status;
          return 0;
      }
  
  
      ///////////////////////////////////////////////
      /**
       *  Gets the iterator attribute of the LRUStore object
       *
       *@return    The iterator value
       */
      public Iterator getIterator()
      {
          //return Collections.enumeration(map.entrySet());
          return map.entrySet().iterator();
      }
  
 
/////////////////////////////////////////////////////////////////////
      // internal mehods
      /**
       *  Removes the specified node from the link list.
       *
       *@param  me  Description of the Parameter
       */
      private void removeNode( LRUElementDescriptor me )
      {
          if ( debugR )
          {
              p( "removing node " + me.ce.getKey() );
          }
  
          if ( me.next == null )
          {
              if ( me.prev == null )
              {
                  // the only node.
                  first = last = null;
              }
              else
              {
                  // last but not the first.
                  last = me.prev;
                  last.next = null;
                  me.prev = null;
              }
          }
          else if ( me.prev == null )
          {
              // first but not the last.
              first = me.next;
              first.prev = null;
              me.next = null;
          }
          else
          {
              // neither the first nor the last.
              me.prev.next = me.next;
              me.next.prev = me.prev;
              me.prev = me.next = null;
          }
      }
  
  
      /**
       *  Adds a new node to the end of the link list. Currently not
used.
       *
       *@param  ce  The feature to be added to the Last attribute
       */
      private void addLast( ILRUElement ce )
      {
  
          LRUElementDescriptor me = new LRUElementDescriptor( ce );
  
          if ( first == null )
          {
              // empty list.
              first = me;
          }
          else
          {
              last.next = me;
              me.prev = last;
          }
          last = me;
          return;
      }
  
  
      /**
       *  Adds a new node to the start of the link list.
       *
       *@param  ce  The feature to be added to the First attribute
       */
      private void addFirst( ILRUElement ce )
      {
  
          LRUElementDescriptor me = new LRUElementDescriptor( ce );
  
          if ( last == null )
          {
              // empty list.
              last = me;
          }
          else
          {
              first.prev = me;
              me.next = first;
          }
          first = me;
          return;
      }
  
  
      /**
       *  Moves an existing node to the start of the link list.
       *
       *@param  ce  Description of the Parameter
       */
      public synchronized void makeFirst( ILRUElement ce )
      {
          makeFirst( new LRUElementDescriptor( ce ) );
      }
  
  
      /**
       *  Moves an existing node to the start of the link list.
       *
       *@param  me  Description of the Parameter
       */
      public synchronized void makeFirst( LRUElementDescriptor me )
      {
  
          try
          {
              if ( me.prev == null )
              {
                  // already the first node.
                  return;
              }
              me.prev.next = me.next;
  
              if ( me.next == null )
              {
                  // last but not the first.
                  last = me.prev;
                  last.next = null;
              }
              else
              {
                  // neither the last nor the first.
                  me.next.prev = me.prev;
              }
              first.prev = me;
              me.next = first;
              me.prev = null;
              first = me;
          }
          catch ( Exception e )
          {
              //log.error( e, "Couldn't make first" );
          }
          return;
      }
  
  
      /**
       *  By overridding this method you can do something with the run
off.
       *
       *@param  obj  Description of the Parameter
       */
      public void waterfall( Object obj )
      {
          // an implementation should handle this if it wants to
      }
  
  
      /**
       *  Dump the cache map for debugging.
       */
      public void dumpMap()
      {
          p( "dumpingMap" );
          for ( Iterator itr = map.entrySet().iterator(); itr.hasNext();
)
          {
              //for ( Iterator itr = memCache.getIterator();
itr.hasNext();) {
              Map.Entry e = ( Map.Entry ) itr.next();
              LRUElementDescriptor me = ( LRUElementDescriptor )
e.getValue();
              p( "dumpMap> key=" + e.getKey() + ", val=" +
me.ce.getVal() );
          }
      }
  
  
      /**
       *  Dump the cache entries from first to list for debugging.
       */
      public void dumpEntries()
      {
          p( "dumpingEntries" );
          for ( LRUElementDescriptor me = first; me != null; me =
me.next )
          {
              p( "dumpEntries> key=" + me.ce.getKey() + ", val=" +
me.ce.getVal() );
          }
      }
  
  
      ///////////////////////////////////////////////////
      /**
       *  Description of the Method
       *
       *@param  s  Description of the Parameter
       */
      public static void p( String s )
      {
          System.out.println( "LRUStore: " + s );
      }
  
  
      /**
       *  The main program for the LRUStore class. For testing.
       *
       *@param  args  The command line arguments
       */
      public static void main( String[] args )
      {
  
          int size = 1000;
          if ( args.length > 0 )
          {
              try
              {
                  size = Integer.parseInt( args[0] );
              }
              catch ( NumberFormatException e )
              {
                  System.out.println( "arg 1 (size) should be a number"
);
              }
          }
  
          int cycles = 2;
          if ( args.length > 1 )
          {
              try
              {
                  cycles = Integer.parseInt( args[1] );
              }
              catch ( NumberFormatException e )
              {
                  System.out.println( "arg 2 (cycles) should be a
number" );
              }
          }
  
          LRUStore map = new LRUStore( size );
  
          boolean show = false;
          if ( args.length > 2 )
          {
              try
              {
                  show = Boolean.valueOf( args[2] ).booleanValue();
                  ;
              }
              catch ( Exception e )
              {
                  System.out.println( "arg 3 (show) should be true or
false" );
              }
          }
  
          for ( int i = 0; i < cycles; i++ )
          {
              long startP = System.currentTimeMillis();
              for ( int j = 0; j <= size; j++ )
              {
                  map.put( "key" + j, "value" + j );
              }
              long endP = System.currentTimeMillis();
              long deltaP = endP - startP;
              System.out.println( "took " + deltaP + " ms. to put " +
size );
  
              long startG = System.currentTimeMillis();
              for ( int j = 0; j <= size; j++ )
              {
                  String val = ( String ) map.get( "key" + j );
                  if ( show )
                  {
                      System.out.println( val );
                  }
              }
              long endG = System.currentTimeMillis();
              long deltaG = endG - startG;
              System.out.println( "took " + deltaG + " ms. to get " +
size );
  
          }
  
      }// end main
  
  }
  // end LRUStore
  
  
  
  1.1
jakarta-turbine-stratum/src/java/org/apache/stratum/util/lru/LRUElementD
escriptor.java
  
  Index: LRUElementDescriptor.java
  ===================================================================
  package org.apache.stratum.util.lru;
  
  import java.io.Serializable;
  
  //////////////////////////////////////////////////////////////
  /**
   *  Wraper to maintaint he double linked list
   *
   *  Pulled from JCS project for ease of use.
   *
   *@author     asmuts
   *@created    January 31, 2002
   */
  public class LRUElementDescriptor implements Serializable
  {
  
      /**
       *  needed for memory cache element LRU linked lisk
       */
      public LRUElementDescriptor prev, next;
  
      /**
       *  Description of the Field
       */
      public ILRUElement ce;
  
  
      /////////////////////////////////////
      /**
       *  Constructor for the LRUElementDescriptor object
       *
       *@param  ce  Description of the Parameter
       */
      public LRUElementDescriptor( ILRUElement ce )
      {
          this.ce = ce;
      }
  
  }
  
  
  
  1.1
jakarta-turbine-stratum/src/java/org/apache/stratum/util/lru/LRUElement.
java
  
  Index: LRUElement.java
  ===================================================================
  package org.apache.stratum.util.lru;
  
  import java.io.Serializable;
  
  import org.apache.stratum.jcs.engine.Attributes;
  
  import org.apache.stratum.util.lru.ILRUElement;
  
  /**
   *  Generic element wrapper. Often stuffed inside another.
   *  Can extend and use the LRUStore put method.  Can get out
   *  of the LRUStore with the wrapper on as well.
   *
   *  Pulled from JCS project for ease of use.
   *
   *@author     asmuts
   *@created    January 15, 2002
   */
  public class LRUElement implements ILRUElement, Serializable
  {
  
      /**
       *  Description of the Field
       */
      public final Serializable key;
      /**
       *  Description of the Field
       */
      public final Serializable val;
      /**
       *  Description of the Field
       */
      public final long createTime;
  
  
      //////////////////////////////////////////////////////////////////
      /**
       *  Constructor for the LRUElement object
       *
       *@param  cacheName  Description of the Parameter
       *@param  key        Description of the Parameter
       *@param  val        Description of the Parameter
       */
      public LRUElement(Serializable key, Serializable val )
      {
          this.key = key;
          this.val = val;
          createTime = System.currentTimeMillis();
      }
  
  
      //////////////////////////////////////////
      /**
       *  Constructor for the LRUElement object
       *
       *@param  cacheName  Description of the Parameter
       *@param  key        Description of the Parameter
       *@param  val        Description of the Parameter
       */
      public LRUElement( Serializable key, Object val )
      {
          this( key, ( Serializable ) val );
      }
  
  
      /////////////////////////////////////
      /**
       *  Gets the key attribute of the LRUElement object
       *
       *@return    The key value
       */
      public Serializable getKey()
      {
          return this.key;
      }
  
  
      //////////////////////////////////////
      /**
       *  Gets the val attribute of the LRUElement object
       *
       *@return    The val value
       */
      public Serializable getVal()
      {
          return this.val;
      }
  
  
  
      //////////////////////////////////////
      /**
       *  Gets the createTime attribute of the LRUElement object
       *
       *@return    The createTime value
       */
      public long getCreateTime()
      {
          return this.createTime;
      }
  
      ///////////////////////////////////////////////////////////
      public int hashCode()
      {
          return key.hashCode();
      }
  
  
      ///////////////////////////////////////////////////
      /**
       *  Description of the Method
       *
       *@return    Description of the Return Value
       */
      public String toString()
      {
          return "[key=" + key + ", val=" + val + "]";
      }
  
  }
  // end class
  
  
  
  
  
  1.1
jakarta-turbine-stratum/src/java/org/apache/stratum/util/lru/ILRUElement
.java
  
  Index: ILRUElement.java
  ===================================================================
  package org.apache.stratum.util.lru;
  
  import java.io.Serializable;
  
  /**
   *  Allows the element to be overriden and customized.
   *
   *  Pulled from JCS project for ease of use.
   *
   *@author     asmuts
   *@created    January 15, 2002
   */
  public interface ILRUElement extends Serializable
  {
      /**
       *  Gets the key attribute of the ILRUElement object
       *
       *@return    The key value
       */
      public Serializable getKey();
  
  
      /**
       *  Gets the val attribute of the ILRUElement object
       *
       *@return    The val value
       */
      public Serializable getVal();
  
  
      /**
       *  Gets the createTime attribute of the ILRUElement object
       *
       *@return    The createTime value
       */
      public long getCreateTime();
  
  }
  
  
  

--
To unsubscribe, e-mail:
<mailto:turbine-dev-unsubscribe@jakarta.apache.org>
For additional commands, e-mail:
<mailto:turbine-dev-help@jakarta.apache.org>


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


Mime
View raw message