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; }