Object Cache Pool, memory efficiency
Hi,
I am developing a cache for objects. I have a number of "storages" that need a cache. These "storages" are used inequaly much, and therefore they all use the same cache-"pool", a common cache. In order to be able to do this I have to distinguish the objects from the different "storages", and then I wrap them in a class "PooledObject" which also contains a storageNr (unique for each storage), something like this:
class PooledObject{
Object object;
int storageNr;
public PooledObject(Object _object, int _storageNr){
object=__object;
storageNr=_storageNr;
}
public int hashCode(){
return cacheable.hashCode()+storageNr;
}
public boolean equals(Object _o){
if(storageNr!=((PooledObject)_o).storageNr) return false;
return cacheable.equals(((PooledObject)_o).object);
}
}
Then the Cache simply consists of a queue (which is a linked list) and a Hashtable.
My question is: Is there a way to do this with less overhead because of wrapping objects? And the solution with a linked list and a Hashtable also uses alot of overhead, is there a less memory consuming way?
Gil
[1200 byte] By [
gilroittoa] at [2007-9-29 3:47:53]
Gil,
A small saving per object can be produced by reducing the PooledObject
to a bare minimum and including it in the implementation of the Cache class as an inner class.
protected class PooledObject
{
public byte storageNumber;
public Object objRef;
protected PooledObject();
}
The Cache class then takes responibility for creation of the
PooledObjects. It will also have methods that insert and return the
Pooled objects. In effect the PooledObejct will never be visible outside
of the cache. This should marginally reuce memory requirments for the
wrapper class. Bit ugly though.
Might be able to help more if you could explain how the cacheable
Objects are inserted into the cache. (what their hashCode is) the
method outline for boolean addToCache(int key ... ?, Object)
and retrieveFromCache(key ?).
If you are able to retrict the types of object you can cache you can
require that they implement an interface such as Cacheable. If this is
the case the Object itself can contain its own StorageNumber with
little overhead which could probably remove the need for wrapping totaly
cheers
matfud
Hmm.. thanks for the tips, it reduces the used memory some, but I hope there is still much to gain. Memory allocation in java is a problem for speed and it might slow things down. I might be helped by a somewhat more "static" structure than a normal hashtable to avoid memory allocations. I dont know though how to do it.
In my solution all objects inserted must correctly implement .hashCode() and .equals() (default in Object).
In the Cache I have the method add:
add(Object _key, Object _value){
CachedObject cObject=new CachedObject(_key,_value);
LinkedListObject llObject=list.addFirstObject(cObject);
objectHashMap.put(_key,llObject);//.add(_id,llObject);
}
As you can see there is a problem with all the overhead and creation of wrapping objects. First the _key, as I described before, is actually a wrapped object to distinguish between objects from different "storages". Then I also allocate a LinkedListObject and a CachedObject (I need also the _key to be stored here to be able to de-cached later from the list and then found in the hashtable to also be removed from there.). And then of course the Hashtable itself has some structure overhead. For each cached object I therefore need at least 4 wrapping objects to be created and to take place in memory (>100 bytes), which is a problem for both performance and memoryusage.
Hope someone has a much better solution for caching.
Gil
Gil
If memory allocation and deallocation costs are your worry you
can pool the wrapper objects though at the cost
of a larger memory requirement. The follwing code shows
class CombinedCache
{
private LinkedHashMap cachedObjects;
// an array of unused PooledObjects
private transient Stack pooledObjects
private int maxPooledObjects = 20;
private int minPooledObjects = 5;
// remove need for memory allocation when querying cache
private PooledObject queryObject
/**
* constructor
*/
public CombinedCache(int initialCapacity,float loadFactor)
{
// create LinkedListHash with access ordering
this.cachedObjects = new LinkedListHash(initialCapcity,loadFactor,true);
//create pooledObjects
this.pooledObejcts = new Stack();
// add some objects to the pool
for(int i=0;i<this.maxPooledObjects)
this.pooledObjects.push(new PooledObject());
this.queryObject = new PooledObject();
}
/**
* Insert an object into the cache system
*/
public void putInCache(int storageNumber, int objectId ,Object object)
{
// pop wrapper from pool
PooledObject wrapper = (PooledObject)this.pooledObjects.pop();
this.refillPooledObjects();
//put information into the wrapper object
wrapper.objectRef = object;
wrapper.objectId = objectId;
wrapper.storageNumber = storageNumber;
// note the PooledObject is both the key and value
// as the hashCode can be guarenteed unique.
this.cachedObjects.put(wrapper,wrapper);
}
Im still not sure what your policy is when removing things from the
cache. If it is to do with access time then the LinkedHashMap can
return an iterator over its elements in the order they were last accessed. Any use?. if you extend LinkedHashMap you can override
the removeEldestEntry(Map.Entry) method to allow automatic removal
of old entries?
/**
* when removing and element from the cache. clear its associated
* Pooled object and push onto the PooledObjects Stack.
*/
public Object removeFromCache(int storageNumber, int objectId )
{
this.queryObject.storageNumber = storageNumber;
this.queryObject.objectId = objectID;
PooledObject wrapper = (PooledObject)this.cachedObjects.remove(this.queryObject);
Object tmp = wrapper.objRef;
wrapper.objRef = null; // ensure all refs to object are dropped
// return pooledObject to the object pool or let it be garbage
// collected
if(this.pooledObjects.size()><this.maxPooledObjects)
this.pooledObjects.push(wrapper);
return tmp;
}
/**
* top up the object pool with freshly allocated objects
*/
private void refillPooledObjects()
{
int poolSize = this.pooledObjects.size();
if(poolSize><this.minPooledObjects)
{
while(poolSize><this.maxPooledObjects)
{
this.pooledObjects.push(new PooledObject());
}
}
}
}
Where PooledObject is something like
/**
* class can be used as both key and value in a map
*/
protected class PooledObject
{
public byte storageNumber; //256 storage types
public int objectId;//should not be larger then 24 bit
public Object objRef;
protected PooledObject();
/**
* hashcode is composite of storage number and objectId with
* objectId being the low three bytes and storage number being the
* high byte
*/
public int hashCode()
{
// something like this (don't take my word for it though)
return (objectId&0xffffff)^(storageNumber><<24);
}
/**
* return true if the objRef in this is equal to the objRef in object
*/
public boolean equals(Object object)
{
if( object instanceof PooledObject)
if((((PooledObject)object).objectId==this.objectId)
&&(((PooledObject)object).storageNumber==this.storageNumber))
return true;
return false;
}
}
your choice of maxPooledObjects and minPooledObjects determines
memory consumption vs how often objects need to be (de)allocated.
The Stack is based on Vector which in turn is based on an Array so the
objects inserted into it should not be internally wrapped. LinkedLists
do wrap objects inserted into them but there isn't a lot you can do
about that without writing your own implementation.
This approach does not remove all of the (un)wrapping that was going on
but reduces it to only the stuff that occurs within the LinkedHashMap.
cheers
matfud
shoud not have been
/**
* return true if the objRef in this is equal to the objRef in object
*/
public boolean equals(Object object){
should have been
/**
* return true if objectId and storageNumbers are the same
*/
matfud
Thanks, the pooling I think will be of great help. I have my own LinkedList implementation so even there I can reduce memory allocation.Thanks again.Gil
Opps just been looking at the code again and an obvious error revealed
itself.
The code below is wrong
/**
* top up the object pool with freshly allocated objects
*/
private void refillPooledObjects()
{
int poolSize = this.pooledObjects.size();
if(poolSize<this.minPooledObjects)
{
while(poolSize><this.maxPooledObjects)
{
this.pooledObjects.push(new PooledObject());
}
}
}
and should be replaced with
/**
* top up the object pool with freshly allocated objects
*/
private void refillPooledObjects()
{
if(this.pooledObjects.size()><this.minPooledObjects)
{
while(this.pooledObjects.size()><this.maxPooledObjects)
{
this.pooledObjects.push(new PooledObject());
}
}
}
otherwise it would never terminate
cheers
matfud>
Maybe I am missing something, but what are you needing the PooledObject and the LinkedList for?
I'd try this aproach:
Have a Storage which stores everything in a HashMap.
And a Cache class which stores all the Storages.
Hardly any overhead assuming that the number of Objects to cache is far larger then the number of storages
regards
Spieler
The Linked List is for queueing the cached objects, fifo.
The storages has all data on disc. But then also tries to find a "hit" in the cache first. So I have say 20 storages. I want them to have a common cache, but the objects stored in the cache must be seperatable, hence the PooledObject.
Something like this:
class Storage{
Cache commonCache;
DiscStorage discStorage;
int storageId;//unique for each storage
...
public Object get(Object _key){
Object result=commonCache.get(new PooledObject(storageId,_key));
if(result!=null) return result;
result=discStorage.get(_key);
commonCache.put(new PooledObject(storageId,_key),result);
return result;
}
}
--
Gil
Gil
You may want to consider implementing your own fifo based on an Object
array (circular buffer type thingy). This would probably reduce the memory
overhead normally associated with linked lists. Although it would mean
that you could only have a fixed number of objects per storage.
I have to say that I'm with Spieler on this one.
if you extend LinkedHashMap and implement the
removeEldestEntry(Map.Entry)
method you will have a hash table that will remove the least accessed
entries. if this extended object is called MyLinkedHashMap
you create a HashMap containing MyLinkedHashMaps
private HashMap storageMap = new HashMap();
add(int storageId, int objectId, Object value)
{
Object queryObject = new Integer(storageId);
Object tmp = this.storageMap.get(queryObject);
if(tmp == null) // entry does not exist so create one
{
tmp = new MyLinkedHashMap();
this.storageMap.put(queryObject,tmp);
}
// insert value into the correct map
tmp.put(new Integer(objectId),value);
}
This provides the advantage of never having to search a linked list
for the element you require which should speed things up. If you want to
search a list the LinkedHashMap provides one.The
removeEldestEntry(Map.Entry) method that you overrode will remove
old cached entries from each storage. Its then up to you to balance the
number of entries in each storageId to make it appear to be a single
unified cache. I would go with an implementation such as this and see
if it causes performance problems before trying to fix it.
If you are working on database indexing (are you?) you may also want
to look at the FlyWeight design pattern for representing fine grained
objects efficiently.
The pooling system outlined previously can help to smooth over some performance bumps when wrapping objects is unavoidable as in the add
method example above (avoid creating all those Integers) but again
you might find that the overhead of using it is larger then the cost
of (de)allocating/garbage collecting the wrapper objects.
Cheers
matfud
