Author: mrogers
Date: 2008-05-23 21:53:30 +0000 (Fri, 23 May 2008)
New Revision: 20082
Added:
trunk/apps/CachingSim.java
trunk/apps/FifoNode.java
trunk/apps/LruNode.java
trunk/apps/Node.java
trunk/apps/RandomNode.java
trunk/apps/RequestGenerator.java
trunk/apps/UTest.java
trunk/apps/UniformRequestGenerator.java
trunk/apps/ZipfRequestGenerator.java
Log:
Caching simulations (LRU vs FIFO vs random replacement)
Added: trunk/apps/CachingSim.java
===================================================================
--- trunk/apps/CachingSim.java (rev 0)
+++ trunk/apps/CachingSim.java 2008-05-23 21:53:30 UTC (rev 20082)
@@ -0,0 +1,141 @@
+// This software has been placed in the public domain by its author
+
+import java.lang.reflect.Field;
+import java.util.ArrayList;
+import java.util.HashSet;
+
+class CachingSim
+{
+ public static int NODES = 1000, DEGREE = 20, KEYS = 200000;
+
+ ArrayList<Node> nodes;
+ RequestGenerator requests;
+
+ CachingSim()
+ {
+ nodes = new ArrayList<Node> (NODES);
+ for (int i = 0; i < NODES; i++) nodes.add (Node.create());
+ makeKleinbergNetwork();
+ ArrayList<Double> keys = new ArrayList<Double> (KEYS);
+ for (int i = 0; i < KEYS; i++) keys.add (Math.random());
+ requests = RequestGenerator.create();
+ requests.init (keys);
+ storeKeys (keys);
+ }
+
+ void run()
+ {
+ double success = 0.0, depth = 0.0, cost = 0.0;
+ // Request each key 100 times
+ for (int i = 0; i < KEYS * 100; i++) {
+ // Reset the counters halfway through the simulation
+ if (i == KEYS * 50) success = depth = cost = 0.0;
+ int random = (int) (Math.random() * nodes.size());
+ Node node = nodes.get (random);
+ double key = requests.generateRequest();
+ HashSet<Node> visited = new HashSet<Node>();
+ int d = node.request (key, 0, visited);
+ if (d != -1) {
+ success++; // Success rate should be close to 1
+ depth += d; // Depth of successful searches
+ cost += visited.size() - 1; // Bandwidth cost
+ }
+ }
+ System.out.println (
+ success / (KEYS * 50) + " " +
+ depth / success + " " +
+ cost / success
+ );
+ }
+
+ void makeKleinbergNetwork()
+ {
+ for (Node a : nodes) {
+ // Normalise the probabilities
+ double norm = 0.0;
+ for (Node b : nodes) {
+ if (a.loc == b.loc) continue;
+ norm += 1.0 / distance (a.loc, b.loc);
+ }
+ // Create DEGREE/2 outgoing connections
+ for (Node b : nodes) {
+ if (a.loc == b.loc) continue;
+ double p = 1.0 / distance (a.loc, b.loc) / norm;
+ for (int i = 0; i < DEGREE / 2; i++) {
+ if (Math.random() < p) {
+ a.neighbours.add (b);
+ b.neighbours.add (a);
+ break;
+ }
+ }
+ }
+ }
+ }
+
+ static double distance (double x, double y)
+ {
+ if (x > y) return Math.min (x - y, y - x + 1.0);
+ else return Math.min (y - x, x - y + 1.0);
+ }
+
+ // Store each key permanently on the node nearest its location
+ void storeKeys (ArrayList<Double> keys)
+ {
+ for (double key : keys) {
+ double bestDistance = Double.POSITIVE_INFINITY;
+ Node bestNode = null;
+ for (Node node : nodes) {
+ double distance = distance (node.loc, key);
+ if (distance < bestDistance) {
+ bestDistance = distance;
+ bestNode = node;
+ }
+ }
+ bestNode.store.add (key);
+ }
+ }
+
+ public static void main (String[] args)
+ {
+ // Command line args are used to set static values by reflection
+ try {
+ for (String arg : args) {
+ // Arguments are in the form class.field=value
+ String[] cfv = arg.split ("=");
+ String[] cf = cfv[0].split ("\\.");
+ Class c = Class.forName (cf[0]);
+ Field f = c.getField (cf[1]);
+ String v = cfv[1];
+ // Determine the type and parse the value
+ Class type = f.getType();
+ if (type == Boolean.TYPE) {
+ boolean b = Boolean.parseBoolean (v);
+ f.setBoolean (null, b);
+ }
+ else if (type == Double.TYPE) {
+ double d = Double.parseDouble (v);
+ f.setDouble (null, d);
+ }
+ else if (type == Integer.TYPE) {
+ int i = Integer.parseInt (v);
+ f.setInt (null, i);
+ }
+ else if (type == Class.class) {
+ ClassLoader cl
+ = ClassLoader.getSystemClassLoader();
+ f.set (null, cl.loadClass (v));
+ }
+ }
+ }
+ catch (Exception e) {
+ System.err.println (e);
+ System.exit (1);
+ }
+ // Print the arguments so we can tell the output files apart
+ System.out.print ("# args:");
+ for (String arg : args) System.out.print (" " + arg);
+ System.out.println();
+ // Run the simulation
+ new CachingSim().run();
+ }
+}
Added: trunk/apps/FifoNode.java
===================================================================
--- trunk/apps/FifoNode.java (rev 0)
+++ trunk/apps/FifoNode.java 2008-05-23 21:53:30 UTC (rev 20082)
@@ -0,0 +1,32 @@
+// This software has been placed in the public domain by its author
+
+import java.util.LinkedHashMap;
+import java.util.Map;
+
+class FifoNode extends Node
+{
+ FifoMap<Double,Double> cache = new FifoMap<Double,Double>();
+
+ boolean cacheGet (double key)
+ {
+ return cache.containsKey (key);
+ }
+
+ void cachePut (double key)
+ {
+ cache.put (key, null);
+ }
+
+ class FifoMap<Key,Value> extends LinkedHashMap<Key,Value>
+ {
+ FifoMap()
+ {
+ super (CACHE_SIZE, 0.75f, false);
+ }
+
+ protected boolean removeEldestEntry (Map.Entry<Key,Value> entry)
+ {
+ return size() > CACHE_SIZE;
+ }
+ }
+}
Added: trunk/apps/LruNode.java
===================================================================
--- trunk/apps/LruNode.java (rev 0)
+++ trunk/apps/LruNode.java 2008-05-23 21:53:30 UTC (rev 20082)
@@ -0,0 +1,33 @@
+// This software has been placed in the public domain by its author
+
+import java.util.LinkedHashMap;
+import java.util.Map;
+
+class LruNode extends Node
+{
+ LruMap<Double,Double> cache = new LruMap<Double,Double>();
+
+ boolean cacheGet (double key)
+ {
+ // Use get() rather than containsKey() to update the LRU order
+ return cache.get (key) != null;
+ }
+
+ void cachePut (double key)
+ {
+ cache.put (key, key);
+ }
+
+ class LruMap<Key,Value> extends LinkedHashMap<Key,Value>
+ {
+ LruMap()
+ {
+ super (CACHE_SIZE, 0.75f, true);
+ }
+
+ protected boolean removeEldestEntry (Map.Entry<Key,Value> entry)
+ {
+ return size() > CACHE_SIZE;
+ }
+ }
+}
Added: trunk/apps/Node.java
===================================================================
--- trunk/apps/Node.java (rev 0)
+++ trunk/apps/Node.java 2008-05-23 21:53:30 UTC (rev 20082)
@@ -0,0 +1,65 @@
+// This software has been placed in the public domain by its author
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.HashSet;
+
+abstract class Node implements Comparator<Node>
+{
+ public static int CACHE_SIZE = 1000, MAX_DEPTH = 10;
+ public static Class CLASS = null; // Factory class
+
+ // Factory method
+ static Node create()
+ {
+ try {
+ return (Node) CLASS.newInstance();
+ }
+ catch (Exception e) {
+ System.err.println (e);
+ System.exit (2);
+ return null;
+ }
+ }
+
+ double loc = Math.random(), target = 0.0;
+ HashSet<Node> neighbours = new HashSet<Node>();
+ HashSet<Double> store = new HashSet<Double>();
+
+ abstract boolean cacheGet (double key);
+ abstract void cachePut (double key);
+
+ // Return the depth at which the request succeeded, or -1 if it failed
+ int request (double key, int depth, HashSet<Node> visited)
+ {
+ if (!visited.add (this)) return -1; // Loop
+ if (cacheGet (key) || store.contains (key)) return depth;
+ if (depth == MAX_DEPTH) return -1; // DNF
+ target = key; // Sort neighbours by closeness to requested key
+ ArrayList<Node> nbrs = new ArrayList<Node> (neighbours);
+ Collections.sort (nbrs, this);
+ for (Node n : nbrs) {
+ int d = n.request (key, depth + 1, visited);
+ if (d != -1) {
+ cachePut (key);
+ return d;
+ }
+ }
+ return -1; // RNF
+ }
+
+ public int compare (Node n1, Node n2)
+ {
+ double d1 = CachingSim.distance (n1.loc, target);
+ double d2 = CachingSim.distance (n2.loc, target);
+ if (d1 < d2) return -1;
+ if (d1 > d2) return 1;
+ return 0;
+ }
+
+ public boolean equals (Node n1, Node n2)
+ {
+ return compare (n1, n2) == 0;
+ }
+}
Added: trunk/apps/RandomNode.java
===================================================================
--- trunk/apps/RandomNode.java (rev 0)
+++ trunk/apps/RandomNode.java 2008-05-23 21:53:30 UTC (rev 20082)
@@ -0,0 +1,24 @@
+// This software has been placed in the public domain by its author
+
+class RandomNode extends Node
+{
+ double[] cache = new double[CACHE_SIZE];
+ double salt = Math.random();
+
+ boolean cacheGet (double key)
+ {
+ return cache[hash (key)] == key;
+ }
+
+ void cachePut (double key)
+ {
+ cache[hash (key)] = key;
+ }
+
+ int hash (double key)
+ {
+ // Throw away the low-order bits because Math.random() sucks
+ long bits = Double.doubleToLongBits (key + salt) >> 8;
+ return (int) (bits & 0x7FFFFFFF) % CACHE_SIZE;
+ }
+}
Added: trunk/apps/RequestGenerator.java
===================================================================
--- trunk/apps/RequestGenerator.java (rev 0)
+++ trunk/apps/RequestGenerator.java 2008-05-23 21:53:30 UTC (rev 20082)
@@ -0,0 +1,80 @@
+// This software has been placed in the public domain by its author
+
+import java.util.ArrayList;
+import java.util.TreeSet;
+
+abstract class RequestGenerator
+{
+ public static Class CLASS = null; // Factory class
+
+ TreeSet<Request> queue = new TreeSet<Request>();
+ double now = 0.0;
+
+ // Factory method
+ static RequestGenerator create()
+ {
+ try {
+ return (RequestGenerator) CLASS.newInstance();
+ }
+ catch (Exception e) {
+ System.err.println (e);
+ System.exit (2);
+ return null;
+ }
+ }
+
+ // Schedule the first request for each key
+ void init (ArrayList<Double> keys)
+ {
+ for (int i = 0, size = keys.size(); i < size; i++) {
+ double rate = requestRate();
+ double time = now - Math.log (Math.random()) / rate;
+ queue.add (new Request (keys.get (i), rate, time));
+ }
+ }
+
+ // Return the rate at which a given key will be requested
+ abstract double requestRate();
+
+ // Return a key and schedule the next request for that key
+ double generateRequest()
+ {
+ Request r = queue.first();
+ queue.remove (r);
+ now = r.time;
+ double time = now - Math.log (Math.random()) / r.rate;
+ queue.add (new Request (r.key, r.rate, time));
+ return r.key;
+ }
+
+ class Request implements Comparable<Request>
+ {
+ final double key, rate, time;
+
+ Request (double key, double rate, double time)
+ {
+ this.key = key;
+ this.rate = rate;
+ this.time = time;
+ }
+
+ // Must be consistent with compareTo()
+ public boolean equals (Request r)
+ {
+ return key == r.key && rate == r.rate && time == r.time;
+ }
+
+ // Must be consistent with equals()
+ public int compareTo (Request r)
+ {
+ if (time < r.time) return -1;
+ if (time > r.time) return 1;
+ // Arbitrarily break ties using rate, then key
+ if (rate < r.rate) return -1;
+ if (rate > r.rate) return 1;
+ if (key < r.key) return -1;
+ if (key > r.key) return 1;
+ return 0;
+ }
+ }
+}
Added: trunk/apps/UTest.java
===================================================================
--- trunk/apps/UTest.java (rev 0)
+++ trunk/apps/UTest.java 2008-05-23 21:53:30 UTC (rev 20082)
@@ -0,0 +1,184 @@
+// This software has been placed in the public domain by its author
+
+import java.io.*;
+import java.util.ArrayList;
+import java.util.Collections;
+
+class UTest
+{
+ static final double zCritical = 2.576; // P = 0.01, two-tailed
+ // static final double zCritical = 1.96; // P = 0.05, two-tailed
+
+
+ static final int SMALLER = -1, INCONCLUSIVE = 0, LARGER = 1;
+
+ static void die (String message)
+ {
+ System.err.println (message);
+ System.exit (1);
+ }
+
+ static ArrayList <Double> readFile (String filename)
+ {
+ ArrayList <Double> arr = new ArrayList <Double> ();
+ try {
+ BufferedReader in;
+ in = new BufferedReader (new FileReader (filename));
+ while (true) {
+ String s = in.readLine();
+ if (s == null) break;
+ arr.add (new Double (s));
+ }
+ in.close();
+ }
+ catch (FileNotFoundException fnf) {
+ die (filename + " not found");
+ }
+ catch (IOException io) {
+ die ("Error reading from " + filename);
+ }
+ catch (NumberFormatException nf) {
+ die ("Invalid data in " + filename);
+ }
+ return arr;
+ }
+
+ // The method used here is explained at
+ // http://faculty.vassar.edu/lowry/ch11a.html
+ static int test (String f1, String f2)
+ {
+ ArrayList <Double> a = readFile (f1);
+ ArrayList <Double> b = readFile (f2);
+ int nA = a.size(), nB = b.size();
+ if (nA < 5 || nB < 5) {
+ System.err.println ("Too few samples for U test\n");
+ return INCONCLUSIVE;
+ }
+
+ /*
+ // Calculate the total rank of each set (old method, O(n^2))
+ ArrayList <Double> merged = new ArrayList <Double> (nA + nB);
+ merged.addAll (a);
+ merged.addAll (b);
+ Collections.sort (merged);
+ double tA = 0.0, tB = 0.0;
+ for (double x : a) {
+ int lessThan = 0, equalTo = 0;
+ for (double y : merged) {
+ if (y < x) lessThan++;
+ else if (y == x) equalTo++;
+ else break;
+ }
+ tA += lessThan + (equalTo + 1) / 2.0;
+ }
+ for (double x : b) {
+ int lessThan = 0, equalTo = 0;
+ for (double y : merged) {
+ if (y < x) lessThan++;
+ else if (y == x) equalTo++;
+ else break;
+ }
+ tB += lessThan + (equalTo + 1) / 2.0;
+ }
+ System.out.println ("Old method: " + tA + " " + tB);
+ */
+
+ // Calculate the total rank of each set (new method, O(n log n))
+ double tA = 0.0, tB = 0.0;
+ Collections.sort (a);
+ Collections.sort (b);
+ int iA = 0, iB = 0, lessThan = 0;
+ while (iA < nA || iB < nB) {
+ int ties = 0, tieRanks = 0;
+ double currA, currB;
+ if (iA < nA) currA = a.get (iA);
+ else currA = Double.POSITIVE_INFINITY;
+ if (iB < nB) currB = b.get (iB);
+ else currB = Double.POSITIVE_INFINITY;
+ // If there are no more bs or next a is less than next b
+ if (currA < currB) {
+ // Count ties in a
+ while (iA + ties < nA &&
+ a.get (iA + ties) == currA) {
+ ties++;
+ tieRanks += ties;
+ }
+ // Increase a's total rank and update the index
+ tA += tieRanks + ties * lessThan;
+ iA += ties;
+ }
+ // Same the other way round
+ else if (currA > currB) {
+ // Count ties in b
+ while (iB + ties < nB &&
+ b.get (iB + ties) == currB) {
+ ties++;
+ tieRanks += ties;
+ }
+ // Increase b's total rank and update the index
+ tB += tieRanks + ties * lessThan;
+ iB += ties;
+ }
+ // Next a equal to next b: this is the tricky one
+ else {
+ int tiesA = 0, tiesB = 0;
+ // Count ties in a
+ while (iA + tiesA < nA &&
+ a.get (iA + tiesA) == currA) {
+ tiesA++;
+ ties++;
+ tieRanks += ties;
+ }
+ // Count ties in b
+ while (iB + tiesB < nB &&
+ b.get (iB + tiesB) == currB) {
+ tiesB++;
+ ties++;
+ tieRanks += ties;
+ }
+ double mean = tieRanks / (double) ties;
+ // Increase a's total rank and update the index
+ tA += tiesA * (mean + lessThan);
+ iA += tiesA;
+ // Increase b's total rank and update the index
+ tB += tiesB * (mean + lessThan);
+ iB += tiesB;
+ }
+ lessThan += ties;
+ }
+
+ // The standard deviation of both total ranks is the same
+ double sigma = Math.sqrt (nA * nB * (nA + nB + 1.0) / 12.0);
+ // Means of the distributions of the total ranks
+ double muA = nA * (nA + nB + 1.0) / 2.0;
+ double muB = nB * (nA + nB + 1.0) / 2.0;
+ // Z scores
+ double zA, zB;
+ if (tA > muA) zA = (tA - muA - 0.5) / sigma;
+ else zA = (tA - muA + 0.5) / sigma;
+ if (tB > muB) zB = (tB - muB - 0.5) / sigma;
+ else zB = (tB - muB + 0.5) / sigma;
+
+ if (zA > zCritical) return LARGER;
+ else if (zB > zCritical) return SMALLER;
+ else return INCONCLUSIVE;
+ }
+
+ public static void main (String[] args)
+ {
+ if (args.length != 2) die ("usage: UTest <file1> <file2>");
+ switch (test (args[0], args[1])) {
+ case SMALLER:
+ System.out.println (args[0] + " is smaller");
+ break;
+
+ case INCONCLUSIVE:
+ System.out.println ("No significant difference");
+ break;
+
+ case LARGER:
+ System.out.println (args[0] + " is larger");
+ break;
+ }
+ }
+}
Added: trunk/apps/UniformRequestGenerator.java
===================================================================
--- trunk/apps/UniformRequestGenerator.java (rev 0)
+++ trunk/apps/UniformRequestGenerator.java 2008-05-23 21:53:30 UTC (rev
20082)
@@ -0,0 +1,9 @@
+// This software has been placed in the public domain by its author
+
+class UniformRequestGenerator extends RequestGenerator
+{
+ double requestRate()
+ {
+ return 1.0; // All keys are requested at the same rate
+ }
+}
Added: trunk/apps/ZipfRequestGenerator.java
===================================================================
--- trunk/apps/ZipfRequestGenerator.java (rev 0)
+++ trunk/apps/ZipfRequestGenerator.java 2008-05-23 21:53:30 UTC (rev
20082)
@@ -0,0 +1,9 @@
+// This software has been placed in the public domain by its author
+
+class ZipfRequestGenerator extends RequestGenerator
+{
+ double requestRate()
+ {
+ return 1.0 / Math.random(); // Zipf distribution
+ }
+}
