Index: PropertyCache.java =================================================================== --- PropertyCache.java (revision 687337) +++ PropertyCache.java (working copy) @@ -36,6 +36,7 @@ /** bitmask to apply to the hash to get to the * corresponding cache segment */ private static final int SEGMENT_MASK = 0x1F; + /** * Indicates whether the cache should be used at all * Can be controlled by the system property: @@ -71,8 +72,11 @@ return (p == q || (p != null && p.equals(q))); } - /* Class modeling a cached entry */ - private final class CacheEntry extends WeakReference { + /** + * Class modeling a cached entry. It extends WeakReference because SoftReference would + * be more heavy-weight and slower (>5% performance loss). + */ + private static final class CacheEntry extends WeakReference { volatile CacheEntry nextEntry; final int hash; @@ -88,12 +92,116 @@ /* Wrapper objects to synchronize on */ private final class CacheSegment { private int count = 0; + private long cleanings = 0; + private long lastCleaning = 0; private volatile ReferenceQueue staleEntries = new ReferenceQueue(); } + private long lastDump = System.currentTimeMillis(); + private long[] segmentPuts = new long[segments.length]; + + private void debugDumpStats() { + if (runtimeType == StringProperty.class) { + System.out.println("Segment Stats:"); + for (int i = 0; i < segments.length - 1; i++) { + System.out.println(" " + i + ": count=" + segments[i].count + + ", put=" + segmentPuts[i] + + ", cleanings=" + segments[i].cleanings + + ", last: " + new java.util.Date(segments[i].lastCleaning)); + } + } + } + + private void dumpBuckets() { + if (true || runtimeType == StringProperty.class) { + StringBuffer stats = new StringBuffer(); + int allCountSum = 0; + int staleCountSum = 0; + System.out.println("Bucket contents for " + this.runtimeType.getName()); + for (int i = 0; i < table.length; i++) { + //System.out.println("Bucket " + i); + int allCount = 0; + int staleCount = 0; + CacheEntry root = table[i]; + CacheEntry entry = root; + while (entry != null) { + Object o = entry.get(); + if (o != null) { + //System.out.println(" " + o.toString()); + } else { + staleCount++; + } + allCount++; + entry = entry.nextEntry; + } + int perc = (allCount != 0 ? 100 * staleCount / allCount : 0); + if (perc == 0) { + stats.append(' '); + } else if (perc > 0 && perc <= 10) { + stats.append('_'); + } else if (perc > 10 && perc <= 50) { + stats.append('x'); + } else { + stats.append('X'); + } + allCountSum += allCount; + staleCountSum += staleCount; + //System.out.println("Bucket " + i + ": stale=" + staleCount + " of " + allCount); + } + int perc = (allCountSum != 0 ? 100 * staleCountSum / allCountSum : 0); + stats.append(" -> ").append(perc).append("%"); + System.out.println(stats.toString()); + } + } + + private int debugDumpBucketStats(int index) { + CacheEntry root = table[index]; + CacheEntry entry = root; + int allCount = 0; + int clearedCount = 0; + while (entry != null) { + allCount++; + if (entry.get() == null) { + clearedCount++; + } + entry = entry.nextEntry; + } + int perc = Math.round(100f * clearedCount / allCount); + if (true && allCount > 0) { + System.out.println(" Bucket " + index + " contains " + allCount + " entries. Stale: " + + clearedCount + ", " + perc + "%"); + } + return perc; + } + + private void debugDumpBucketStats() { + if (false && runtimeType == StringProperty.class) { + System.out.println("Bucket stats for " + this.toString()); + int av = 0; + for (int i = 0; i < table.length; i++) { + av += debugDumpBucketStats(i); + } + av /= table.length; + System.out.println("Percentage cleared: " + av + "%"); + } + } + private void cleanSegment(int segmentIndex) { + long now = System.currentTimeMillis(); + boolean dump = false; + if (now > lastDump + 5000) { + lastDump = now; + dump = true; + System.out.println("----before"); + debugDumpBucketStats(); + } CacheEntry entry; CacheSegment segment = segments[segmentIndex]; + //This segment must be locked when cleanSegment is called! + + segment.cleanings++; + segment.lastCleaning = System.currentTimeMillis(); + int bucketIndex; int oldCount = segment.count; @@ -105,7 +213,8 @@ CacheEntry e = table[bucketIndex]; while (e != null && e.nextEntry != null - && e.hash != entry.hash) { + //&& e.hash != entry.hash) { + && e != entry) { prev = e; e = e.nextEntry; } @@ -117,13 +226,23 @@ prev.nextEntry = e.nextEntry; } segment.count--; + } else { + System.out.println("Stale Entry not found: " + entry.hash); } } + + if (dump) { + //debugDumpStats(); + System.out.println("----after"); + debugDumpBucketStats(); + } + synchronized (votesForRehash) { if (oldCount > segment.count) { votesForRehash[segmentIndex] = false; return; } + /* cleanup had no effect */ if (!votesForRehash[segmentIndex]) { /* first time for this segment */ @@ -154,9 +273,9 @@ * entries. */ private void put(Object o) { - int hash = hash(o); - CacheSegment segment = segments[hash & SEGMENT_MASK]; + int segmentIndex = hash & SEGMENT_MASK; + CacheSegment segment = segments[segmentIndex]; synchronized (segment) { int index = hash & (table.length - 1); @@ -174,11 +293,12 @@ CacheEntry newEntry = new CacheEntry(o, entry, segment.staleEntries); table[index] = newEntry; segment.count++; + segmentPuts[segmentIndex]++; } } if (segment.count > (2 * table.length)) { - cleanSegment(hash & SEGMENT_MASK); + cleanSegment(segmentIndex); } } } @@ -186,6 +306,14 @@ /* Gets a cached instance. Returns null if not found */ private Object get(Object o) { + long now = System.currentTimeMillis(); + if (now > lastDump + 5000) { + lastDump = now; + //debugDumpBucketStats(); + //debugDumpStats(); + dumpBuckets(); + //clean(); + } int hash = hash(o); int index = hash & (table.length - 1); @@ -225,7 +353,6 @@ * */ private void rehash(int index) { - CacheSegment seg = segments[index]; synchronized (seg) { if (index > 0) { @@ -234,6 +361,7 @@ } else { /* double the amount of buckets */ int newLength = table.length << 1; + System.out.println("---=== rehash " + table.length + " -> " + newLength + "! ===---"); if (newLength > 0) { //no overflow? /* reset segmentcounts */ for (int i = segments.length; --i >= 0;) { @@ -262,6 +390,42 @@ } } + private void clean() { + clean(SEGMENT_MASK); + } + + private void clean(int index) { + CacheSegment seg = segments[index]; + synchronized (seg) { + if (index > 0) { + /* need to recursively acquire locks on all segments */ + clean(index - 1); + } else { + System.out.println("---=== clean! ===---"); + System.out.println("----before"); + debugDumpBucketStats(); + + CacheEntry prev = null; + for (int i = table.length - 1; i >= 0; i--) { + for (CacheEntry c = table[i]; c != null; c = c.nextEntry) { + if (c.get() == null) { + if (prev == null) { + table[i] = c.nextEntry; + } else { + prev.nextEntry = c.nextEntry; + } + segments[c.hash & SEGMENT_MASK].count--; + } else { + prev = c; + } + } + } + System.out.println("----after"); + debugDumpBucketStats(); + } + } + } + /** * Default constructor. * @@ -313,7 +477,7 @@ * @param prop the Property instance to check for * @return the cached instance */ - public final Property fetch(Property prop) { + public Property fetch(Property prop) { return (Property) fetch((Object) prop); } @@ -326,7 +490,7 @@ * @param chy the CommonHyphenation instance to check for * @return the cached instance */ - public final CommonHyphenation fetch(CommonHyphenation chy) { + public CommonHyphenation fetch(CommonHyphenation chy) { return (CommonHyphenation) fetch((Object) chy); } @@ -339,7 +503,7 @@ * @param cf the CommonFont instance to check for * @return the cached instance */ - public final CommonFont fetch(CommonFont cf) { + public CommonFont fetch(CommonFont cf) { return (CommonFont) fetch((Object) cf); } @@ -352,21 +516,21 @@ * @param cbpb the CommonBorderPaddingBackground instance to check for * @return the cached instance */ - public final CommonBorderPaddingBackground fetch(CommonBorderPaddingBackground cbpb) { + public CommonBorderPaddingBackground fetch(CommonBorderPaddingBackground cbpb) { return (CommonBorderPaddingBackground) fetch((Object) cbpb); } /** - * Checks if the given {@link CommonBorderPaddingBackground.BorderInfo} is present in the cache - - * if so, returns a reference to the cached instance. + * Checks if the given {@link CommonBorderPaddingBackground.BorderInfo} is present in the + * cache - if so, returns a reference to the cached instance. * Otherwise the given object is added to the cache and returned. * * @param bi the BorderInfo instance to check for * @return the cached instance */ - public final CommonBorderPaddingBackground.BorderInfo fetch(CommonBorderPaddingBackground.BorderInfo bi) { - + public CommonBorderPaddingBackground.BorderInfo fetch( + CommonBorderPaddingBackground.BorderInfo bi) { return (CommonBorderPaddingBackground.BorderInfo) fetch((Object) bi); }