jakarta-jcs-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From asm...@apache.org
Subject cvs commit: jakarta-turbine-jcs/src/experimental/org/apache/jcs/engine/memory/arc ARCMemoryCache.java
Date Tue, 13 Jul 2004 02:13:12 GMT
asmuts      2004/07/12 19:13:12

  Modified:    src/experimental/org/apache/jcs/engine/memory/arc
                        ARCMemoryCache.java
  Log:
  The ARC is now mostly functional.  I made it use the linked list implementation and saw
tremendous performance gains.  I'm working on algorithm correctness.  I ran 10 million random
puts, gets, and removes against it and it held up.
  
  Revision  Changes    Path
  1.2       +232 -173  jakarta-turbine-jcs/src/experimental/org/apache/jcs/engine/memory/arc/ARCMemoryCache.java
  
  Index: ARCMemoryCache.java
  ===================================================================
  RCS file: /home/cvs/jakarta-turbine-jcs/src/experimental/org/apache/jcs/engine/memory/arc/ARCMemoryCache.java,v
  retrieving revision 1.1
  retrieving revision 1.2
  diff -u -r1.1 -r1.2
  --- ARCMemoryCache.java	10 Jul 2004 03:46:27 -0000	1.1
  +++ ARCMemoryCache.java	13 Jul 2004 02:13:12 -0000	1.2
  @@ -16,7 +16,6 @@
    * limitations under the License.
    */
   
  -import java.util.LinkedList;
   import java.io.IOException;
   import java.io.Serializable;
   
  @@ -29,30 +28,33 @@
   import org.apache.jcs.engine.control.CompositeCache;
   import org.apache.jcs.engine.behavior.ICacheElement;
   import org.apache.jcs.engine.memory.AbstractMemoryCache;
  +import org.apache.jcs.engine.memory.util.DoubleLinkedList;
  +import org.apache.jcs.engine.memory.util.MemoryElementDescriptor;
   
   /**
    *  This is a rough implmentation of an adaptive replacement cache.
    *  ARC is a hybrid LFU / LRU that adapts to user behavior.
    *
  + *  See the ARC method for more detail on how the algorithm works.
  + *
    *  @see  http://www.almaden.ibm.com/StorageSystems/autonomic_storage/ARC/index.shtml
  - *  TODO implement custom linked lists to cut down on removal overhead.
    */
   public class ARCMemoryCache
       extends AbstractMemoryCache
   {
   
     private final static Log log =
  -      LogFactory.getLog( ARCMemoryCache.class );
  +      LogFactory.getLog(ARCMemoryCache.class);
   
     int[] loc = new int[0];
   
     // maximum size
     int c = 0;
   
  -  LinkedList T1 = new LinkedList();
  -  LinkedList T2 = new LinkedList();
  -  LinkedList B1 = new LinkedList();
  -  LinkedList B2 = new LinkedList();
  +  DoubleLinkedList T1 = new DoubleLinkedList();
  +  DoubleLinkedList T2 = new DoubleLinkedList();
  +  DoubleLinkedList B1 = new DoubleLinkedList();
  +  DoubleLinkedList B2 = new DoubleLinkedList();
   
     private static final int _T1_ = 1;
     private static final int _T2_ = 2;
  @@ -72,9 +74,7 @@
   
     public ARCMemoryCache()
     {
  -
  -    log.warn( "test" );
  -    log.debug( "Loading Arc" );
  +    log.debug("Loading Arc");
     }
   
     public Object[] getKeyArray()
  @@ -82,9 +82,9 @@
       return null;
     }
   
  -  public ICacheElement getQuiet( Serializable key ) throws IOException
  +  public ICacheElement getQuiet(Serializable key) throws IOException
     {
  -    return get( key );
  +    return get(key);
     }
   
     /**
  @@ -92,117 +92,150 @@
      *
      *@param  hub
      */
  -  public synchronized void initialize( CompositeCache hub )
  +  public synchronized void initialize(CompositeCache hub)
     {
  -    super.initialize( hub );
  +    super.initialize(hub);
       c = this.cattr.getMaxObjects(); // / 2;
  -    target_T1 = c;
  -    log.info( "initialized LRUMemoryCache for " + cacheName );
  +    target_T1 = c / 2;
  +    log.info("initialized LRUMemoryCache for " + cacheName);
     }
   
  -  public ICacheElement get( Serializable key ) throws IOException
  +  public ICacheElement get(Serializable key) throws IOException
     {
  -    CacheElement ce = new CacheElement( cacheName,
  -                                        ( Serializable ) key,
  -                                        null );
  -    return ARC( ce, true );
  +    CacheElement ce = new CacheElement(cacheName,
  +                                       (Serializable) key,
  +                                       null);
  +
  +    ICacheElement ice = null;
  +    try {
  +      ice = ARC(ce, true);
  +    } catch( Exception e ) {
  +      log.error( e );
  +    }
  +    return ice;
     }
   
  -  public void update( ICacheElement ce )
  +  public void update(ICacheElement ce)
     {
  -    ARC( ce, false );
  +    try {
  +      ARC(ce, false);
  +    } catch( Exception e ) {
  +      log.error( e );
  +    }
     }
   
  -  public ICacheElement ARC( ICacheElement ce, boolean isGet )
  +  /**
  +   * This is the primary method for the ARC.  It handles both puts and gets.
  +   * The ARC has 4 linked lists: T1, T2, B1, and B2.  The 'T' lists are tops
  +   * and the 'B' lists are bottoms.  Bottom lists do not hold object, only keys.
  +   *
  +   * The T1 list is an LRU (Least Recently Used) list.  The T2 list is a near
  +   * LFU (Least Frequently Used) list.
  +   *
  +   * After items are removed from T1 and T2, their keys are stored in B1 and B2.
  +   * The number of keys in B1 and B2 is restricted to the number of max items.
  +   *
  +   * When there is a put or a get for an item whose key exists on one of the
  +   * bottom lists, the maximum number of items in T1 is adjusted.  If the item
  +   * was found on B2 (the bottom LFU list) the maximum allowed in T1 (the top
  +   * LRU list) is reduced.  If the item is found in B1 list (the bottom LRU) the
  +   * maximum allowed in T1 is increased.
  +   *
  +   * The maximum allowed in T1 will not exceed the maxSize.  The maximum in T1
  +   * and T2 combined will not exceed the maxSize.  The maximum number of elements
  +   * and keys allowed in all 4 lists will not exceed twice the maximum size.
  +   *
  +   * @param ce ICacheElement
  +   * @param isGet boolean
  +   * @return ICacheElement
  +   */
  +  public ICacheElement ARC(ICacheElement ce, boolean isGet)
     {
   
       cnt++;
   
  -    if ( cnt % 10000 == 0 )
  +    if (cnt % 10000 == 0)
       //if ( true )
       {
  -      if ( log.isInfoEnabled() )
  +      if (log.isInfoEnabled())
         {
           StringBuffer buf = new StringBuffer();
  -        buf.append( "\n ce.key() = " + ce.getKey() );
  -        buf.append( "\n isGet = " + isGet );
  -        buf.append( getStats() );
  -        log.info( buf.toString() );
  +        buf.append("\n ce.key() = " + ce.getKey());
  +        buf.append("\n isGet = " + isGet);
  +        buf.append(getStats());
  +        log.info(buf.toString());
         }
       }
   
  -    if ( !isGet )
  +    if (!isGet)
       {
         putCnt++;
       }
   
  -    ElementDescriptor temp = ( ElementDescriptor ) map.get( ce.getKey() );
  +    ElementDescriptor temp = (ElementDescriptor) map.get(ce.getKey());
  +    boolean isHit = true;
   
  -    if ( temp != null )
  +    if (temp != null)
       {
   
  -      if ( isGet )
  +      if (isGet)
         {
           hitCnt++;
         }
   
  -      switch ( temp.listNum )
  +      switch (temp.listNum)
         {
           case _T1_:
  -          if ( log.isDebugEnabled() )
  +          if (log.isDebugEnabled())
             {
  -            log.debug( "T1" );
  +            log.debug("T1");
             }
   
  -          log.debug( "T1 before remove = " + T1.size() );
  -          boolean stat1 = T1.remove( temp ); // need to implement our own list
  -          log.debug( "T1 after remove = " + T1.size() + " stat = " + stat1 );
  +          log.debug("T1 to T2, before remove = " + T1.size());
  +          boolean stat1 = T1.remove(temp); // need to implement our own list
  +          log.debug("T1 to T2, after remove = " + T1.size() + " stat = " + stat1);
   
             temp.listNum = _T2_;
  -          T2.addFirst( temp );
  +          T2.addFirst(temp);
             break;
   
           case _T2_:
  -          if ( log.isDebugEnabled() )
  +          if (log.isDebugEnabled())
             {
  -            log.debug( "T2" );
  +            log.debug("T2");
             }
   
  -          log.debug( "T2 before remove = " + T2.size() );
  -          boolean stat2 = T2.remove( temp ); // need to implement our own list
  -          log.debug( "T2 after remove = " + T2.size() + " stat = " + stat2 );
  -
             temp.listNum = _T2_;
  -          T2.addFirst( temp );
  +          T2.makeFirst(temp);
             break;
   
           case _B1_:
   
             // B1 hit: favor recency
  -          if ( log.isDebugEnabled() )
  -          {
  -            log.debug( "B1" );
  -          }
   
             // adapt the target size
  -          target_T1 = Math.min( target_T1 + Math.max( B2.size() / B1.size(), 1 ),
  -                                c );
  +          target_T1 = Math.min(target_T1 + Math.max(B2.size() / B1.size(), 1),
  +                               c);
  +          if (log.isDebugEnabled())
  +          {
  +            log.debug("B1, targetT1 = " + target_T1 );
  +          }
   
  -          if ( !isGet )
  +          if (!isGet)
             {
  -            if ( log.isDebugEnabled() )
  +            if (log.isDebugEnabled())
               {
  -              log.debug( "B1 before remove = " + B1.size() );
  +              log.debug("B1 before remove = " + B1.size());
               }
  -            boolean stat3 = B1.remove( temp ); // need to implement our own list
  -            if ( log.isDebugEnabled() )
  +            boolean stat3 = B1.remove(temp); // need to implement our own list
  +            if (log.isDebugEnabled())
               {
  -              log.debug( "B1 after remove = " + B1.size() + " stat = " + stat3 );
  +              log.debug("B1 after remove = " + B1.size() + " stat = " + stat3);
               }
  -            //replace(temp);
  +            replace(temp);
               temp.listNum = _T2_;
               temp.ce = ce;
  -            T2.addFirst( temp ); // seen twice recently, put on T2
  +            T2.addFirst(temp); // seen twice recently, put on T2
   
             }
             else
  @@ -218,31 +251,33 @@
           case _B2_:
   
             // B2 hit: favor frequency
  -          if ( log.isDebugEnabled() )
  +
  +          // adapt the target size
  +          target_T1 = Math.max(target_T1 - Math.max(B1.size() / B2.size(), 1),
  +                               0);
  +          if (log.isDebugEnabled())
             {
  -            log.debug( "B2" );
  +            log.debug("B2, targetT1 = " + target_T1 );
             }
   
  -          // adapt the target size
  -          target_T1 = Math.max( target_T1 - Math.max( B1.size() / B2.size(), 1 ),
  -                                0 );
  -          if ( !isGet )
  +          if (!isGet)
             {
  -            if ( log.isDebugEnabled() )
  +            if (log.isDebugEnabled())
               {
  -              log.debug( "B2 before remove = " + B2.size() );
  +              log.debug("B2 before remove = " + B2.size());
               }
  -
  -            boolean stat4 = B2.remove( temp ); // need to implement our own list
  -            if ( log.isDebugEnabled() )
  +            boolean stat4 = B2.remove(temp); // need to implement our own list
  +            if (log.isDebugEnabled())
               {
  -              log.debug( "B2 after remove = " + B2.size() + " stat = " + stat4 );
  +              log.debug("B2 after remove = " + B2.size() + " stat = " + stat4);
               }
   
  -            //replace(temp);
  +            replace(temp);
               temp.listNum = _T2_;
               temp.ce = ce;
  -            T2.addFirst( temp ); // seen twice recently, put on T2
  +            T2.addFirst(temp); // seen twice recently, put on T2
  +
  +            replace(temp);
             }
             else
             {
  @@ -255,63 +290,74 @@
             break;
         }
   
  -//////////////////////////////////////////////////////////////////////////////
         // was null
       }
       else
       {
  -    /* page is not in cache  */
  +      /* page is not in cache  */
   
  -      if ( isGet )
  +      isHit = false;
  +      if (isGet)
         {
           missCnt++;
         }
   
  -      if ( log.isDebugEnabled() )
  +      if (log.isDebugEnabled())
         {
  -        log.debug( "Page is not in cache" );
  +        log.debug("Page is not in cache");
         }
   
  -      if ( T1.size() + B1.size() >= c )
  +    } // end if not in cache
  +
  +    //////////////////////////////////////////////////////////////////////////////
  +    // Do some size Checks if this is a put
  +    //if (!isGet)
  +    //{
  +      if (T1.size() + B1.size() >= c)
         {
           /* B1 + T1 full? */
  -        if ( T1.size() < c )
  +        if (T1.size() < c)
           {
             /* Still room in T1? */
  -          temp = ( ElementDescriptor ) B1.removeLast();
  -          map.remove( temp.key );
  +          temp = (ElementDescriptor) B1.removeLast();
  +          if ( temp != null ) {
  +            map.remove(temp.key);
  +          }
             /* yes: take page off B1 */
             //temp->pointer = replace(); /* find new place to put page */
  -          replace( temp );
  +          replace(temp);
           }
           else
           {
             /* no: B1 must be empty */
  -          temp = ( ElementDescriptor ) T1.removeLast(); /* take page off T1 */
  -          map.remove( temp.key );
  +          //temp = (ElementDescriptor) T1.removeLast(); /* take page off T1 */
  +          //map.remove(temp.ce.getKey());
             //if (temp->dirty) destage(temp); /* if dirty, evict before overwrite */
  +          replace(temp);
           }
         }
         else
         {
           /* B1 + T1 have less than c pages */
  -        if ( T1.size() + T2.size() + B1.size() + B2.size() >= c )
  +        if (T1.size() + T2.size() + B1.size() + B2.size() >= c)
           {
             /* cache full? */
             /* Yes, cache full: */
  -          if ( T1.size() + T2.size() + B1.size() + B2.size() >= 2 * c )
  +          if (T1.size() + T2.size() + B1.size() + B2.size() >= 2 * c)
             {
  -            /* directory is full: */
  +            /* cache is full: */
               /* x find and reuse B2’s LRU */
  -            temp = ( ElementDescriptor ) B2.removeLast();
  -            map.remove( temp.key );
  +            temp = (ElementDescriptor) B2.removeLast();
  +            if ( temp != null ) {
  +              map.remove(temp.key);
  +            }
             }
             else
             {
               /* cache directory not full, easy case */
               ; //nop
             }
  -          replace( temp );
  +          replace(temp);
           }
           else
           {
  @@ -320,18 +366,17 @@
           }
         }
   
  -      if ( !isGet )
  +      if (!isGet && !isHit)
         {
  -        temp = new ElementDescriptor( ce.getKey() );
  +        temp = new ElementDescriptor(ce);
           temp.ce = ce;
           temp.listNum = _T1_;
  -        T1.addFirst( temp ); /* seen once recently, put on T1 */
  -        this.map.put( temp.key, temp );
  -      }
  +        T1.addFirst(temp); /* seen once recently, put on T1 */
  +        this.map.put(temp.ce.getKey(), temp);
  +      } // end if put
   
  -    } // end if not in cache
   
  -    if ( temp == null )
  +    if (temp == null)
       {
         return null;
       }
  @@ -346,89 +391,89 @@
      *
      * @param orig ElementDescriptor
      */
  -  public void replace( ElementDescriptor orig )
  +  public void replace(ElementDescriptor orig)
     {
       try
       {
         ElementDescriptor temp;
  -      if ( T1.size() >= Math.max( 1, target_T1 ) )
  +      if (T1.size() >= Math.max(1, target_T1))
         { // T1’s size exceeds target?
           // yes: T1 is too big
  -        temp = ( ElementDescriptor ) T1.getLast();
  -        if ( orig == null || !orig.equals( temp ) )
  +        temp = (ElementDescriptor) T1.getLast();
  +        if (orig == null || !orig.key.equals(temp.key))
           {
  -          if ( log.isDebugEnabled() )
  +          if (log.isDebugEnabled())
             {
  -            log.debug( "replace -- T1 to B1" );
  -            log.debug( getInfo() );
  +            log.debug("replace -- T1 to B1");
  +            log.debug(getInfo());
             }
  -          temp = ( ElementDescriptor ) T1.removeLast(); // grab LRU from T1
  +          temp = (ElementDescriptor) T1.removeLast(); // grab LRU from T1
             // nullify object, temp is now just a dummy container to help
             // adjust the lru size
             try
             {
  -            this.waterfal( temp.ce );
  +            this.waterfal(temp.ce);
             }
  -          catch ( Exception e )
  +          catch (Exception e)
             {
  -            log.error( e );
  +            log.error(e);
             }
             temp.ce = null;
             temp.listNum = _B1_; // note that fact
  -          B1.addFirst( temp ); // put it on B1
  +          B1.addFirst(temp); // put it on B1
             //T1Length—; B1Length++; // bookkeep
           }
           else
           {
  -          if ( log.isDebugEnabled() )
  +          if (log.isDebugEnabled())
             {
  -            log.debug( "orig == temp, t1" );
  +            log.debug("orig == temp, t1");
             }
           }
         }
         else
         // if t2 is greater than or equal to what is left in c after the target
  -      //if (T2.size() >= (c - target_T1) )
  +      if ( ( T2.size() + T1.size() ) > c )
         {
   
           // no: T1 is not too big
  -        temp = ( ElementDescriptor ) T2.getLast();
  -        if ( orig == null || !orig.equals( temp ) )
  +        temp = (ElementDescriptor) T2.getLast();
  +        if (orig == null || !orig.key.equals(temp.key))
           {
  -          if ( log.isDebugEnabled() )
  +          if (log.isDebugEnabled())
             {
  -            log.debug( "replace -- T2 to B2" );
  -            log.debug( getInfo() );
  +            log.debug("replace -- T2 to B2");
  +            log.debug(getInfo());
             }
   
  -          temp = ( ElementDescriptor ) T2.removeLast(); // grab LRU page of T2
  +          temp = (ElementDescriptor) T2.removeLast(); // grab LRU page of T2
             // nullify object, temp is now just a dummy container to help
             // adjust the lru size
             try
             {
  -            this.waterfal( temp.ce );
  +            this.waterfal(temp.ce);
             }
  -          catch ( Exception e )
  +          catch (Exception e)
             {
  -            log.error( e );
  +            log.error(e);
             }
             temp.ce = null;
             temp.listNum = _B2_; // note that fact
  -          B2.addFirst( temp ); // put it on B2
  +          B2.addFirst(temp); // put it on B2
             //T2Length—; B2Length++; // bookkeep
           }
           else
           {
  -          if ( log.isDebugEnabled() )
  +          if (log.isDebugEnabled())
             {
  -            log.debug( "orig == temp, t2" );
  +            log.debug("orig == temp, t2");
             }
           }
         }
       }
  -    catch ( Exception e )
  +    catch (Exception e)
       {
  -      log.error( e );
  +      log.error(e);
       }
     }
   
  @@ -438,48 +483,64 @@
      * @param key Serializable
      * @return boolean
      */
  -  public boolean remove( Serializable key )
  +  public boolean remove(Serializable key)
     {
  -    ElementDescriptor temp = ( ElementDescriptor ) map.remove( key );
  -    int loc = temp.listNum;
  -    if ( loc == _T1_ )
  -    {
  -      T1.remove( temp );
  -    }
  -    else
  -    if ( loc == _T2_ )
  -    {
  -      T2.remove( temp );
  -    }
  -    else
  -    if ( loc == _B1_ )
  -    {
  -      B1.remove( temp );
  -    }
  -    else
  -    if ( loc == _B2_ )
  -    {
  -      B2.remove( temp );
  +    ElementDescriptor temp = (ElementDescriptor) map.remove(key);
  +    if ( temp != null ) {
  +      int loc = temp.listNum;
  +      if (loc == _T1_)
  +      {
  +        T1.remove(temp);
  +      }
  +      else
  +      if (loc == _T2_)
  +      {
  +        T2.remove(temp);
  +      }
  +      else
  +      if (loc == _B1_)
  +      {
  +        B1.remove(temp);
  +      }
  +      else
  +      if (loc == _B2_)
  +      {
  +        B2.remove(temp);
  +      }
       }
       return true;
     }
   
  +  /**
  +   * Remove all of the elements from both the Map and the linked
  +   * list implementation. Overrides base class.
  +   */
  +  public synchronized void removeAll() throws IOException
  +  {
  +    map.clear();
  +    T1.removeAll();
  +    T2.removeAll();
  +    B1.removeAll();
  +    B2.removeAll();
  +  }
  +
     /////////////////////////////////////////////////////////////////////////
     public String getStats()
     {
  -    StringBuffer buf = new StringBuffer( 0 );
  -    buf.append( getInfo() );
  -    buf.append( getCnts() );
  +    StringBuffer buf = new StringBuffer(0);
  +    buf.append(getInfo());
  +    buf.append(getCnts());
       return buf.toString();
     }
   
     public String getCnts()
     {
  -    StringBuffer buf = new StringBuffer( 0 );
  -    buf.append( "\n putCnt = " + putCnt );
  -    buf.append( "\n hitCnt = " + hitCnt );
  -    buf.append( "\n missCnt = " + missCnt );
  -    if ( hitCnt != 0 )
  +    StringBuffer buf = new StringBuffer(0);
  +    buf.append("\n putCnt = " + putCnt);
  +    buf.append("\n hitCnt = " + hitCnt);
  +    buf.append("\n missCnt = " + missCnt);
  +    buf.append("\n -------------------------");
  +    if (hitCnt != 0)
       {
         // int rate = ((hitCnt + missCnt) * 100) / (hitCnt * 100) * 100;
         //buf.append("\n Hit Rate = " + rate + " %" );
  @@ -490,32 +551,30 @@
     public String getInfo()
     {
       StringBuffer buf = new StringBuffer();
  -    buf.append( "\n T1.size() = " + T1.size() );
  -    buf.append( "\n T2.size() = " + T2.size() );
  -    buf.append( "\n B1.size() = " + B1.size() );
  -    buf.append( "\n B2.size() = " + B2.size() );
  -    buf.append( "\n target_T1 = " + target_T1 );
  -    buf.append( "\n map.size() = " + map.size() );
  +    buf.append("\n T1.size() = " + T1.size());
  +    buf.append("\n T2.size() = " + T2.size());
  +    buf.append("\n B1.size() = " + B1.size());
  +    buf.append("\n B2.size() = " + B2.size());
  +    buf.append("\n target_T1 = " + target_T1);
  +    buf.append("\n map.size() = " + map.size());
  +    buf.append("\n -------------------------");
       return buf.toString();
     }
   
   /////////////////////////////////////////////////
     public class ElementDescriptor
  +      extends MemoryElementDescriptor
     {
       public int listNum;
  -    public ICacheElement ce;
  +
       public Serializable key;
   
  -    public ElementDescriptor( Serializable k )
  +    public ElementDescriptor(ICacheElement ce)
       {
  -      key = k;
  +      super(ce);
  +      key = ce.getKey();
       }
   
  -    //public boolean equals(ElementDescriptor ed)
  -    //{
  -    //  //ce.getKey().equals(ed.ce.getKey());
  -    //  return key.equals(ed.ce.getKey());
  -    //}
     }
   
   }
  
  
  

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


Mime
View raw message