Author: shawkins
Date: 2011-10-26 13:38:18 -0400 (Wed, 26 Oct 2011)
New Revision: 3585
Modified:
trunk/engine/src/main/java/org/teiid/common/buffer/CacheKey.java
trunk/engine/src/main/java/org/teiid/common/buffer/impl/BufferManagerImpl.java
trunk/engine/src/main/java/org/teiid/common/buffer/impl/LrfuEvictionQueue.java
trunk/engine/src/main/java/org/teiid/common/buffer/impl/MemoryStorageManager.java
trunk/engine/src/test/java/org/teiid/common/buffer/impl/TestLrfuEvictionQueue.java
Log:
TEIID-1750 correcting memorystoragemanager and switching to a lower cost crf function
Modified: trunk/engine/src/main/java/org/teiid/common/buffer/CacheKey.java
===================================================================
--- trunk/engine/src/main/java/org/teiid/common/buffer/CacheKey.java 2011-10-25 21:41:08
UTC (rev 3584)
+++ trunk/engine/src/main/java/org/teiid/common/buffer/CacheKey.java 2011-10-26 17:38:18
UTC (rev 3585)
@@ -26,9 +26,9 @@
private Long id;
protected long lastAccess;
- protected double orderingValue;
+ protected long orderingValue;
- public CacheKey(Long id, long lastAccess, double orderingValue) {
+ public CacheKey(Long id, long lastAccess, long orderingValue) {
this.id = id;
this.lastAccess = lastAccess;
this.orderingValue = orderingValue;
@@ -63,7 +63,7 @@
return lastAccess;
}
- public double getOrderingValue() {
+ public long getOrderingValue() {
return orderingValue;
}
Modified: trunk/engine/src/main/java/org/teiid/common/buffer/impl/BufferManagerImpl.java
===================================================================
---
trunk/engine/src/main/java/org/teiid/common/buffer/impl/BufferManagerImpl.java 2011-10-25
21:41:08 UTC (rev 3584)
+++
trunk/engine/src/main/java/org/teiid/common/buffer/impl/BufferManagerImpl.java 2011-10-26
17:38:18 UTC (rev 3585)
@@ -139,7 +139,7 @@
/**
* This estimate is based upon adding the value to 2/3 maps and having
CacheEntry/PhysicalInfo keys
*/
- private static final int BATCH_OVERHEAD = 128;
+ private static final long BATCH_OVERHEAD = 128;
final class BatchManagerImpl implements BatchManager, Serializer<List<? extends
List<?>>> {
final Long id;
@@ -200,9 +200,6 @@
throws TeiidComponentException {
int sizeEstimate = getSizeEstimate(batch);
Long oid = batchAdded.getAndIncrement();
- if (oid.longValue() == 56) {
- this.toString();
- }
CacheEntry old = null;
if (previous != null) {
if (removeOld) {
@@ -875,7 +872,7 @@
void removeCacheGroup(Long id, boolean prefersMemory) {
cleanSoftReferences();
Collection<Long> vals = cache.removeCacheGroup(id);
- int overhead = vals.size() * BATCH_OVERHEAD;
+ long overhead = vals.size() * BATCH_OVERHEAD;
maxReserveBytes.addAndGet(overhead);
reserveBatchBytes.addAndGet(overhead);
for (Long val : vals) {
Modified: trunk/engine/src/main/java/org/teiid/common/buffer/impl/LrfuEvictionQueue.java
===================================================================
---
trunk/engine/src/main/java/org/teiid/common/buffer/impl/LrfuEvictionQueue.java 2011-10-25
21:41:08 UTC (rev 3584)
+++
trunk/engine/src/main/java/org/teiid/common/buffer/impl/LrfuEvictionQueue.java 2011-10-26
17:38:18 UTC (rev 3585)
@@ -44,17 +44,12 @@
//just with more CPU overhead vs. wait time.
protected NavigableMap<CacheKey, V> evictionQueue = new
ConcurrentSkipListMap<CacheKey, V>();
protected AtomicLong clock;
- //combined recency/frequency lamda value between 0 and 1 lower -> LFU, higher
-> LRU
- //TODO: adaptively adjust this value. more hits should move closer to lru
- protected double crfLamda;
- protected double inverseCrfLamda = 1 - crfLamda;
- protected int maxInterval; //don't consider the old ordering value after the
maxInterval
- protected int minInterval; //cap the frequency gain under this interval (we can make
some values too hot otherwise)
- private float minVal;
+ protected long maxInterval;
+ protected long halfLife;
public LrfuEvictionQueue(AtomicLong clock) {
this.clock = clock;
- setCrfLamda(.00005); //smaller values tend to work better since we're using
interval bounds
+ setHalfLife(1<<17);
}
public boolean remove(V value) {
@@ -95,41 +90,38 @@
CacheKey key = value.getKey();
long lastAccess = key.getLastAccess();
long currentClock = clock.get();
- double orderingValue = key.getOrderingValue();
+ long orderingValue = key.getOrderingValue();
orderingValue = computeNextOrderingValue(currentClock, lastAccess,
orderingValue);
- value.setKey(new CacheKey(key.getId(), (int)currentClock, orderingValue));
+ value.setKey(new CacheKey(key.getId(), currentClock, orderingValue));
}
-
- double computeNextOrderingValue(long currentTime,
- long lastAccess, double orderingValue) {
- long delta = currentTime - lastAccess;
- orderingValue =
- (delta<maxInterval?(delta<minInterval?minVal:Math.pow(inverseCrfLamda,
delta)):0)*orderingValue
- //recency component
- + Math.pow(currentTime, crfLamda);
- return orderingValue;
- }
- public double getCrfLamda() {
- return crfLamda;
- }
-
- public void setCrfLamda(double crfLamda) {
- this.crfLamda = crfLamda;
- this.inverseCrfLamda = 1 - crfLamda;
- int i = 0;
- for (; i < 30; i++) {
- float val = (float)Math.pow(inverseCrfLamda, 1<<i);
- if (val == 0) {
- break;
+ long computeNextOrderingValue(long currentTime,
+ long lastAccess, long orderingValue) {
+ long delta = currentTime - lastAccess;
+ if (delta > maxInterval) {
+ return currentTime;
+ }
+ long increase = Math.min(orderingValue, currentTime);
+
+ //scale the increase based upon how hot we previously were
+ increase>>=1;
+ increase *= orderingValue/(double)lastAccess;
+
+ if (delta > halfLife) {
+ while ((delta-=halfLife) > halfLife && (increase>>=1) > 0) {
}
- if (val > .8) {
- minInterval = 1<<i;
- this.minVal = val;
- }
}
- this.maxInterval = 1<<(i-1);
+ if (delta > 0 && increase > 0) {
+ //linear interpolate the rest of the delta (between 1 and 1/2)
+ increase = (long) (increase*(halfLife/((double)halfLife + delta)));
+ }
+ return currentTime + increase;
}
+ public void setHalfLife(long halfLife) {
+ this.halfLife = halfLife;
+ this.maxInterval = 62*this.halfLife;
+ }
+
}
Modified:
trunk/engine/src/main/java/org/teiid/common/buffer/impl/MemoryStorageManager.java
===================================================================
---
trunk/engine/src/main/java/org/teiid/common/buffer/impl/MemoryStorageManager.java 2011-10-25
21:41:08 UTC (rev 3584)
+++
trunk/engine/src/main/java/org/teiid/common/buffer/impl/MemoryStorageManager.java 2011-10-26
17:38:18 UTC (rev 3585)
@@ -158,7 +158,11 @@
public boolean remove(Long gid, Long id) {
Map<Long, CacheEntry> group = groups.get(gid);
if (group != null) {
- return group.remove(id) != null;
+ synchronized (group) {
+ int size = group.size();
+ group.remove(id);
+ return group.size() != size;
+ }
}
return false;
}
Modified:
trunk/engine/src/test/java/org/teiid/common/buffer/impl/TestLrfuEvictionQueue.java
===================================================================
---
trunk/engine/src/test/java/org/teiid/common/buffer/impl/TestLrfuEvictionQueue.java 2011-10-25
21:41:08 UTC (rev 3584)
+++
trunk/engine/src/test/java/org/teiid/common/buffer/impl/TestLrfuEvictionQueue.java 2011-10-26
17:38:18 UTC (rev 3585)
@@ -33,9 +33,9 @@
@Test public void testPrecision() {
LrfuEvictionQueue<?> q = new LrfuEvictionQueue<BaseCacheEntry>(new
AtomicLong());
- double value = 0;
+ long value = 0;
for (long i = Integer.MAX_VALUE; i < 10l + Integer.MAX_VALUE; i++) {
- double valueNext = q.computeNextOrderingValue(i, i-1, value);
+ long valueNext = q.computeNextOrderingValue(i, i-1, value);
assertTrue(valueNext > value);
value = valueNext;
}