diff --git a/simulator/build.gradle.kts b/simulator/build.gradle.kts index 2b43da67..78ecace8 100644 --- a/simulator/build.gradle.kts +++ b/simulator/build.gradle.kts @@ -39,6 +39,7 @@ dependencies { implementation(libs.bundles.coherence) implementation(libs.bundles.slf4j.jdk) implementation(libs.univocity.parsers) + implementation("net.openhft:zero-allocation-hashing:0.16") } application { diff --git a/simulator/src/main/java/com/github/benmanes/caffeine/cache/simulator/parser/TraceFormat.java b/simulator/src/main/java/com/github/benmanes/caffeine/cache/simulator/parser/TraceFormat.java index cf41cc28..0b9ed845 100644 --- a/simulator/src/main/java/com/github/benmanes/caffeine/cache/simulator/parser/TraceFormat.java +++ b/simulator/src/main/java/com/github/benmanes/caffeine/cache/simulator/parser/TraceFormat.java @@ -35,6 +35,8 @@ import com.github.benmanes.caffeine.cache.simulator.parser.corda.CordaTraceReade import com.github.benmanes.caffeine.cache.simulator.parser.glcache.GLCacheTraceReader; import com.github.benmanes.caffeine.cache.simulator.parser.gradle.GradleTraceReader; import com.github.benmanes.caffeine.cache.simulator.parser.kaggle.OutbrainTraceReader; +import com.github.benmanes.caffeine.cache.simulator.parser.libcachesim.TraceCsvTraceReader; +import com.github.benmanes.caffeine.cache.simulator.parser.libcachesim.TwitterCsvTraceReader; import com.github.benmanes.caffeine.cache.simulator.parser.lirs.LirsTraceReader; import com.github.benmanes.caffeine.cache.simulator.parser.lrb.LrbTraceReader; import com.github.benmanes.caffeine.cache.simulator.parser.scarab.ScarabTraceReader; @@ -74,6 +76,8 @@ public enum TraceFormat { CORDA(CordaTraceReader::new), GL_CACHE(GLCacheTraceReader::new), GRADLE(GradleTraceReader::new), + LCS_TWITTER(TwitterCsvTraceReader::new), + LCS_TRACE(TraceCsvTraceReader::new), LIRS(LirsTraceReader::new), LRB(LrbTraceReader::new), OUTBRAIN(OutbrainTraceReader::new), diff --git a/simulator/src/main/java/com/github/benmanes/caffeine/cache/simulator/parser/libcachesim/TraceCsvTraceReader.java b/simulator/src/main/java/com/github/benmanes/caffeine/cache/simulator/parser/libcachesim/TraceCsvTraceReader.java new file mode 100644 index 00000000..36585546 --- /dev/null +++ b/simulator/src/main/java/com/github/benmanes/caffeine/cache/simulator/parser/libcachesim/TraceCsvTraceReader.java @@ -0,0 +1,54 @@ +/* + * Copyright 2023 Ben Manes. All Rights Reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package com.github.benmanes.caffeine.cache.simulator.parser.libcachesim; + +import static com.github.benmanes.caffeine.cache.simulator.policy.Policy.Characteristic.WEIGHTED; + +import java.util.Set; +import java.util.stream.Stream; + +import com.github.benmanes.caffeine.cache.simulator.parser.TextTraceReader; +import com.github.benmanes.caffeine.cache.simulator.policy.AccessEvent; +import com.github.benmanes.caffeine.cache.simulator.policy.Policy.Characteristic; + +/** + * A reader for the LibCacheSim trace.csv file. + * + * @author ben.manes@gmail.com (Ben Manes) + */ +public final class TraceCsvTraceReader extends TextTraceReader { + + public TraceCsvTraceReader(String filePath) { + super(filePath); + } + + @Override + public Set characteristics() { + return Set.of(WEIGHTED); + } + + @Override + public Stream events() { + return lines() + .skip(1) + .map(line -> line.split(",")) + .map(array -> { + long key = Long.parseLong(array[4]); + int weight = Integer.parseInt(array[3]); + return AccessEvent.forKeyAndWeight(key, weight); + }); + } +} diff --git a/simulator/src/main/java/com/github/benmanes/caffeine/cache/simulator/parser/libcachesim/TwitterCsvTraceReader.java b/simulator/src/main/java/com/github/benmanes/caffeine/cache/simulator/parser/libcachesim/TwitterCsvTraceReader.java new file mode 100644 index 00000000..27f95f08 --- /dev/null +++ b/simulator/src/main/java/com/github/benmanes/caffeine/cache/simulator/parser/libcachesim/TwitterCsvTraceReader.java @@ -0,0 +1,57 @@ +/* + * Copyright 2023 Ben Manes. All Rights Reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package com.github.benmanes.caffeine.cache.simulator.parser.libcachesim; + +import static com.github.benmanes.caffeine.cache.simulator.policy.Policy.Characteristic.WEIGHTED; + +import java.util.Set; +import java.util.stream.Stream; + +import com.github.benmanes.caffeine.cache.simulator.parser.TextTraceReader; +import com.github.benmanes.caffeine.cache.simulator.policy.AccessEvent; +import com.github.benmanes.caffeine.cache.simulator.policy.Policy.Characteristic; + +import net.openhft.hashing.LongHashFunction; + +/** + * A reader for the LibCacheSim twitter_cluster52.csv file. + * + * @author ben.manes@gmail.com (Ben Manes) + */ +public final class TwitterCsvTraceReader extends TextTraceReader { + + public TwitterCsvTraceReader(String filePath) { + super(filePath); + } + + @Override + public Set characteristics() { + return Set.of(WEIGHTED); + } + + @Override + public Stream events() { + var hasher = LongHashFunction.xx3(); + return lines() + .skip(1) + .map(line -> line.split(", ")) + .map(array -> { + long key = hasher.hashChars(array[1]); + int weight = Integer.parseInt(array[2]); + return AccessEvent.forKeyAndWeight(key, weight); + }); + } +} diff --git a/simulator/src/main/java/com/github/benmanes/caffeine/cache/simulator/policy/PolicyStats.java b/simulator/src/main/java/com/github/benmanes/caffeine/cache/simulator/policy/PolicyStats.java index ff52f2f6..06f1005b 100644 --- a/simulator/src/main/java/com/github/benmanes/caffeine/cache/simulator/policy/PolicyStats.java +++ b/simulator/src/main/java/com/github/benmanes/caffeine/cache/simulator/policy/PolicyStats.java @@ -69,6 +69,7 @@ public class PolicyStats { addMetric(Metric.of("Policy", (Supplier) this::name, OBJECT, true)); addMetric(Metric.of("Hit Rate", (DoubleSupplier) this::hitRate, PERCENT, true)); + addMetric(Metric.of("Miss Rate", (DoubleSupplier) this::missRate, PERCENT, true)); addMetric(Metric.of("Hits", (LongSupplier) this::hitCount, NUMBER, true)); addMetric(Metric.of("Misses", (LongSupplier) this::missCount, NUMBER, true)); addMetric(Metric.of("Requests", (LongSupplier) this::requestCount, NUMBER, true)); @@ -87,6 +88,12 @@ public class PolicyStats { .name("Weighted Hit Rate") .type(PERCENT) .build()); + addMetric(Metric.builder() + .value((DoubleSupplier) this::weightedMissRate) + .addCharacteristic(WEIGHTED) + .name("Weighted Miss Rate") + .type(PERCENT) + .build()); addPercentMetric("Adaption", this::percentAdaption); addMetric("Average Miss Penalty", this::averageMissPenalty); addMetric("Average Penalty", this::avergePenalty); diff --git a/simulator/src/main/java/com/github/benmanes/caffeine/cache/simulator/policy/linked/LinkedPolicy.java b/simulator/src/main/java/com/github/benmanes/caffeine/cache/simulator/policy/linked/LinkedPolicy.java index d9391d86..63235f1c 100644 --- a/simulator/src/main/java/com/github/benmanes/caffeine/cache/simulator/policy/linked/LinkedPolicy.java +++ b/simulator/src/main/java/com/github/benmanes/caffeine/cache/simulator/policy/linked/LinkedPolicy.java @@ -100,8 +100,8 @@ public final class LinkedPolicy implements Policy { evict(node); } else { policyStats.recordWeightedHit(weight); - currentSize += (weight - old.weight); - old.weight = weight; +// currentSize += (weight - old.weight); +// old.weight = weight; policy.onAccess(old, policyStats); evict(old); diff --git a/simulator/src/main/resources/reference.conf b/simulator/src/main/resources/reference.conf index 201d7cb8..ea885cbe 100644 --- a/simulator/src/main/resources/reference.conf +++ b/simulator/src/main/resources/reference.conf @@ -31,88 +31,17 @@ caffeine.simulator { random-seed = 1033096058 # The maximum number of entries in the cache - maximum-size = 512 + maximum-size = 1073741824 policies = [ - # Policies that provide an optimal upper bound - opt.Unbounded, - opt.Clairvoyant, - - # Policies based on maintaining a linked-list cross-cutting the hash table linked.Lru, - linked.Mru, - linked.Lfu, - linked.Mfu, linked.Fifo, - linked.Clock, - linked.S4Lru, - linked.MultiQueue, - linked.SegmentedLru, - - # Policies based on obtaining a random sampling from the hash table - sampled.Lru, - sampled.Mru, - sampled.Lfu, - sampled.Mfu, - sampled.Fifo, - sampled.Random, - sampled.Hyperbolic, - - # Policies based on the Greedy-Dual algorithm - greedy-dual.Camp, - greedy-dual.Gdsf, - greedy-dual.GDWheel, - - # Policies based on the 2Q algorithm - two-queue.TwoQueue, - two-queue.TuQueue, - two-queue.Qdlp, - - # Policies based on a sketch algorithm - sketch.WindowTinyLfu, - sketch.S4WindowTinyLfu, - sketch.LruWindowTinyLfu, - sketch.RandomWindowTinyLfu, - sketch.FullySegmentedWindowTinyLfu, - - sketch.HillClimberWindowTinyLfu, - - sketch.FeedbackTinyLfu, - sketch.FeedbackWindowTinyLfu, - - sketch.TinyCache, - sketch.TinyCache_GhostCache, - sketch.WindowTinyCache, - - # Policies based on the LIRS algorithm - irr.Frd, - irr.Lirs, - irr.DClock, - irr.ClockPro, - irr.ClockProPlus, - irr.ClockProSimple, - - # Policies based on the ARC algorithm - adaptive.Arc, - adaptive.Car, - adaptive.Cart, - - # Caching products - product.OHC, - product.Guava, - product.TCache, - product.Cache2k, product.Caffeine, - product.Ehcache3, - product.Coherence, - product.Hazelcast, - product.ExpiringMap, ] # The admission policy (opposite of eviction policy) admission = [ Always, - TinyLfu, ] # The membership filter @@ -489,7 +418,9 @@ caffeine.simulator { files { # The paths to the trace files or the file names if in the format's package. To use a mix of # formats, specify the entry in the form "{format}:{path}", e.g. "lirs:loop.trace.gz". - paths = [ multi1.trace.gz ] + paths = [ "lcs_trace:/Users/ben/projects/libCacheSim/data/trace.csv" ] + paths = [ "lcs_twitter:/Users/ben/projects/libCacheSim/data/twitter_cluster52.csv" ] + paths = [ "snia-cambridge:/Users/ben/Downloads/hm_0.csv.gz" ] # arc: format from the authors of the ARC algorithm # adapt-size: format from the authors of the AdaptSize algorithm