Sampled Hill Climber - Reusing arrays on ghosts to avoid GC errors

NadavKeren · Jun 18, 2024 · 427b0be · 427b0be
1 parent 41232dd
commit 427b0be
Show file tree

Hide file tree

Showing 11 changed files with 242 additions and 83 deletions.
diff --git a/...enmanes/caffeine/cache/simulator/policy/latency_aware/pipeline/AdaptivePipelineCache.java b/...enmanes/caffeine/cache/simulator/policy/latency_aware/pipeline/AdaptivePipelineCache.java
@@ -144,6 +144,7 @@ private PipelineBlock createBlock(String type, int quota, Config generalConfig,
                 break;
             case "BC":
                 block = new BurstCache(new UneditableLatencyEstimatorProxy<>(burstEstimator),
+                                       cacheCapacity,
                                        quantumSize,
                                        quota);
                 break;

diff --git a/...om/github/benmanes/caffeine/cache/simulator/policy/latency_aware/pipeline/BurstCache.java b/...om/github/benmanes/caffeine/cache/simulator/policy/latency_aware/pipeline/BurstCache.java
@@ -1,5 +1,6 @@
 package com.github.benmanes.caffeine.cache.simulator.policy.latency_aware.pipeline;
 
+import com.github.benmanes.caffeine.cache.simulator.DebugHelpers.Assert;
 import com.github.benmanes.caffeine.cache.simulator.policy.EntryData;
 import com.github.benmanes.caffeine.cache.simulator.policy.LatencyEstimator;
 import com.github.benmanes.caffeine.cache.simulator.policy.sketch.BurstBlock;
@@ -11,10 +12,10 @@ public class BurstCache implements PipelineBlock {
     final private int quantumSize;
     final private BurstBlock block;
 
-    public BurstCache(LatencyEstimator<Long> burstEstimator, int quantumSize, int initialQuota) {
+    public BurstCache(LatencyEstimator<Long> burstEstimator, int maximalCapacity, int quantumSize, int initialQuota) {
         this.quantumSize = quantumSize;
 
-        block = new BurstBlock(initialQuota * quantumSize, burstEstimator);
+        block = new BurstBlock(maximalCapacity, initialQuota * quantumSize, burstEstimator);
     }
 
     private BurstCache(BurstCache other) {
@@ -27,6 +28,11 @@ public void clear() {
         this.block.clear();
     }
 
+    @Override
+    public void setSize(int size) {
+        this.block.setSize(size);
+    }
+
     @Override
     public void increaseSize(List<EntryData> items) {
         block.increaseSize(quantumSize, items);
@@ -59,6 +65,19 @@ public PipelineBlock createCopy() {
         return evicted;
     }
 
+    @Override
+    public void copyInto(PipelineBlock other) {
+        Assert.assertCondition(other instanceof BurstCache,
+                               () -> String.format("Got wrong block type: expected: %s\tgot: %s",
+                                                   this.getClass().getSimpleName(),
+                                                   other.getClass().getSimpleName()));
+
+        BurstCache casted = (BurstCache) other;
+
+        Assert.assertCondition(casted.quantumSize == this.quantumSize, "copy fail: quantum size mismatch");
+        this.block.copyInto(casted.block);
+    }
+
     @Override
     public EntryData getEntry(long key) {
         return this.block.get(key);

diff --git a/.../com/github/benmanes/caffeine/cache/simulator/policy/latency_aware/pipeline/LfuBlock.java b/.../com/github/benmanes/caffeine/cache/simulator/policy/latency_aware/pipeline/LfuBlock.java
@@ -70,6 +70,8 @@ public void increaseSize(List<EntryData> items) {
             protectedBlock.increaseCapacity(quantumSize);
             probationBlock.appendItems(items);
         }
+
+        this.validate();
     }
 
     @Override
@@ -96,6 +98,8 @@ public List<EntryData> decreaseSize() {
             probationBlock.decreaseCapacity(quantumSize);
         }
 
+        this.validate();
+
         return items;
     }
 
@@ -109,12 +113,42 @@ private LfuBlock(LfuBlock other) {
         this.protectedBlock = other.protectedBlock.createGhostCopy("Protected Copy");
     }
 
+    @Override
+    public void copyInto(PipelineBlock other) {
+        Assert.assertCondition(other instanceof LfuBlock,
+                               () -> String.format("Got wrong block type: expected: %s\tgot: %s",
+                                                   this.getClass().getSimpleName(),
+                                                   other.getClass().getSimpleName()));
+        LfuBlock casted = (LfuBlock) other;
+
+        this.protectedBlock.copyInto(casted.protectedBlock);
+        this.probationBlock.copyInto(casted.probationBlock);
+
+        Assert.assertCondition(this.protectedBlock.capacity() == casted.protectedBlock.capacity(), "protected size mismatch");
+        Assert.assertCondition(this.probationBlock.capacity() == casted.probationBlock.capacity(), "probation size mismatch");
+        casted.capacity = this.capacity;
+
+        casted.normalizationBias = this.normalizationBias;
+        casted.normalizationFactor = this.normalizationFactor;
+        casted.maxDelta = this.maxDelta;
+        casted.maxDeltaCounts = this.maxDeltaCounts;
+        casted.samplesCount = this.samplesCount;
+    }
+
+
+
     @Override
     public void clear() {
         this.probationBlock.clear();
         this.protectedBlock.clear();
     }
 
+    @Override
+    public void setSize(int size) {
+        this.probationBlock.setSize(size);
+        this.protectedBlock.setSize(size);
+    }
+
     @Override
     public PipelineBlock createCopy() {
         return new LfuBlock(this);

diff --git a/.../com/github/benmanes/caffeine/cache/simulator/policy/latency_aware/pipeline/LruBlock.java b/.../com/github/benmanes/caffeine/cache/simulator/policy/latency_aware/pipeline/LruBlock.java
@@ -58,6 +58,28 @@ public void clear() {
         this.block.clear();
     }
 
+    @Override
+    public void setSize(int size) {
+        this.block.setSize(size);
+    }
+
+    @Override
+    public void copyInto(PipelineBlock other) {
+        Assert.assertCondition(other instanceof LruBlock,
+                               () -> String.format("Got wrong block type: expected: %s\tgot: %s",
+                                                   this.getClass().getSimpleName(),
+                                                   other.getClass().getSimpleName()));
+        LruBlock casted = (LruBlock) other;
+
+        this.block.copyInto(casted.block);
+
+        casted.normalizationBias = this.normalizationBias;
+        casted.normalizationFactor = this.normalizationFactor;
+        casted.maxDelta = this.maxDelta;
+        casted.maxDeltaCounts = this.maxDeltaCounts;
+        casted.samplesCount = this.samplesCount;
+    }
+
     @Override
     public PipelineBlock createCopy() {
         return new LruBlock(this);

diff --git a/...github/benmanes/caffeine/cache/simulator/policy/latency_aware/pipeline/PipelineBlock.java b/...github/benmanes/caffeine/cache/simulator/policy/latency_aware/pipeline/PipelineBlock.java
@@ -29,4 +29,16 @@ default void onMiss(long key) {}
     default void bookkeeping(long key) {}
 
     void clear();
+
+    void copyInto(PipelineBlock other);
+
+    /***
+     * Resizes the block in anticipation that it will be filled as part of a copy process.
+     * This is a destructive operation available only on sections that where cleared.
+     * This isn't intended as a way to increase/decrease the size of the block as part of the pipeline change.
+     * Use with caution.
+     *
+     * @param size - a non-negative number smaller or equal to the total cache size.
+     */
+    void setSize(int size);
 }
diff --git a/...ithub/benmanes/caffeine/cache/simulator/policy/latency_aware/pipeline/PipelinePolicy.java b/...ithub/benmanes/caffeine/cache/simulator/policy/latency_aware/pipeline/PipelinePolicy.java
@@ -37,7 +37,7 @@ public class PipelinePolicy implements Policy {
 
     final public static PipelinePolicy DUMMY = new DummyPipeline();
 
-    final private PolicyStats stats;
+    private PolicyStats stats;
     final private PipelineBlock[] blocks;
     final private int[] quota;
     final private BlockType[] types;
@@ -46,6 +46,8 @@ public class PipelinePolicy implements Policy {
     final private int quantumSize;
     final private int cacheCapacity;
 
+    private boolean isDummy = false;
+
     private double timeframePenalty = 0;
     private int timeframeOpCount = 0;
 
@@ -162,6 +164,26 @@ public void clear() {
         for (int i = 0; i < blockCount; ++i) {
             this.blocks[i].clear();
         }
+
+        isDummy = false;
+        stats = new PolicyStats(generatePipelineName());
+    }
+
+    public void makeDummy() {
+        isDummy = true;
+    }
+
+    public void copyInto(PipelinePolicy other) {
+        Assert.assertCondition(this.blockCount == other.blockCount,
+                               () -> String.format("pipeline size mismatch: this: %d\tother: %d",
+                                                   this.blockCount,
+                                                   other.blockCount));
+        int blockIdx = 0;
+        for (var block: this.blocks) {
+            block.copyInto(other.blocks[blockIdx]);
+            other.quota[blockIdx] = this.quota[blockIdx];
+            ++blockIdx;
+        }
     }
 
     public String generatePipelineName() {
@@ -199,6 +221,7 @@ private PipelineBlock createBlock(String type,
                 break;
             case "BC":
                 block = new BurstCache(new UneditableLatencyEstimatorProxy<>(burstEstimator),
+                                       cacheCapacity,
                                        quantumSize,
                                        quota);
                 break;
@@ -257,6 +280,10 @@ public PipelinePolicy createCopy() {
 
     @Override
     public void record(AccessEvent event) {
+        if (isDummy) {
+            return;
+        }
+
         EntryData entry = null;
 
         if (opDumpWriter != null) {
@@ -407,6 +434,10 @@ private void recordAccordingToAvailability(EntryData entry, AccessEvent currEven
     }
 
     public double getTimeframeAveragePenalty() {
+        if (isDummy) {
+            return Double.MAX_VALUE;
+        }
+
         final double res = this.timeframePenalty / this.timeframeOpCount;
         this.timeframePenalty = 0;
         this.timeframeOpCount = 0;

diff --git a/...b/benmanes/caffeine/cache/simulator/policy/latency_aware/pipeline/SampledHillClimber.java b/...b/benmanes/caffeine/cache/simulator/policy/latency_aware/pipeline/SampledHillClimber.java
@@ -82,6 +82,24 @@ private void createGhostCaches() {
         }
     }
 
+    private void copyGhostCaches() {
+        for (var pair : ghostCaches) {
+            PipelinePolicy ghost = pair.first();
+            CacheDiff diff = pair.second();
+
+            ghost.clear();
+
+            sampledMainCache.copyInto(ghost);
+
+            if (ghost.canExtend(diff.incIdx) && ghost.canShrink(diff.decIdx)) {
+                ghost.moveQuantum(diff.incIdx, diff.decIdx);
+            } else {
+                ghost.makeDummy();
+            }
+        }
+
+    }
+
     @Override
     public void record(AccessEvent event) {
         this.mainPipeline.record(event);
@@ -156,7 +174,7 @@ private void adapt(int eventNum) {
                 writer.flush();
             }
 
-            createGhostCaches();
+            copyGhostCaches();
         }
     }
 

diff --git a/...or/src/main/java/com/github/benmanes/caffeine/cache/simulator/policy/linked/CraBlock.java b/...or/src/main/java/com/github/benmanes/caffeine/cache/simulator/policy/linked/CraBlock.java
@@ -107,15 +107,18 @@ public void clear() {
             while (sentinel.size > 0) {
                 releaseToNodePool(sentinel.next);
             }
-
-            sentinel.next = null;
-            sentinel.prev = null;
-            sentinel.sentinel = null;
-            this.lists[i] = null;
         }
 
         data.clear();
         activeLists.clear();
+        this.size = 0;
+    }
+
+    public void copyInto(CraBlock other) {
+        other.maximumSize = this.maximumSize;
+        other.size = 0;
+        other.currOp = this.currOp;
+        other.copyLists(this);
     }
 
     private void copyLists(CraBlock other) {
@@ -399,6 +402,12 @@ private void validateBlock() {
                                  data.size()));
     }
 
+    public void setSize(int size) {
+        Assert.assertCondition(this.data.size() == 0 && size == 0,
+                               () -> String.format("CRA Block - Resetting size while there are items in the block: data.size() = %d, size = %d",
+                                                   this.data.size(), size));
+    }
+
     /**
      * A node on the double-linked list.
      */