You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Aaron Smuts <aa...@verizon.net> on 2002/02/01 05:04:03 UTC
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
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:
<ma...@jakarta.apache.org>
For additional commands, e-mail:
<ma...@jakarta.apache.org>
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>