I have implemented a simulation program that runs LRU and another web caching algorithm called Sliding Window LFU. I want to compare them both in terms of the hit rate and their run time. SW-LFU works fine, but it takes FOREVER to run! I really can't figure why, since I used many tricks and ideas to keep the effort low and constant.
NOTE: Ignore the for loops in the printing methods, since when I test the performance of the code I comment out the calls to the these methods in main().
Window LFU:
///////////////////////////////////////////////
// package declaration
package algorithms;
///////////////////////////////////////////////
// import of system classes and utilities
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.logging.Level;
import java.util.logging.Logger;
///////////////////////////////////////////////
// import of user-defined classes
import requests.Request;
/**
* Sliding Window Least Frequently Used (SW-LFU) cache replacement algorithm
* There are N items available for caching
* These items are objects of type Request distinguished by their numeric ID (int), i.e. the field reqID
* Cache is implemented as an array of size M and it is filled with objects of type Request
* Sliding window is implemented as an array of size K and it is filled with requests for objects (again objects of type Request) distinguished by their reqID
* "Sliding window" means actually a FIFO structure - requests inserted from one end and previous requests shifted by one index at each insertion; when max size is
* reached, at every insertion of a request from one end another request is dropped from the other end.
* Of course, a trick is used to accomplish this behaviour with a static array, as explained later
* The replacement algorithm holds in the cache the items with the highest request count in the sliding window of the last K requests (score)
* When a request for an item is inserted into the window, the score of that item is increased by 1
* When a request for an item is dropped from the window, the score of that item is decreased by 1
* The scores are stored in a reqID - score HashMap called scores
* The cache is (partially) ordered regarding the score of the cached items, with the "most-valuable" item at the left end and the "least-valuable" item at the right end
* Replacement takes place only if the requested item has at least equal score with the "least-valuable" cached item (i.e. right-most item in the cache array)
* Otherwise, replacement will not take place (however, the request for that item is inserted into the window, thus the score of the requested item is increased by 1 -
* in other words, at the next or after some requests, might be able to replace the cached item that now could not replace it!)
* Since no ArrayList, LinkedList, or similar structure is used, which after each insertion would "shift" the previous items by one index, an int position counter is used
* for both the cache (counter) and the window (winCounter) in order to achieve the desired behaviour (i.e. a cache ordered w.r.t. the scores of the cached items and a
* window acting as a sliding window)
* In case of a cache hit, the score of that cached item is increased by 1. Therefore, it might have become greater than or equal to the score of the next item at its
* left.If this is the case, the cache is reordered with these two items exchanging position in the cache (and the relevant position counters) in order to maintain an
* ordered cache w.r.t. the score of the cached items
* Similarly, in case of dropping a request from the window, the score of that item is decreased by 1. Therefore, if that item is in the cache, the score of the next
* item at its right might have become greater than its score. If this is the case, the cache is reordered with those two items exchanging position in the cache (and
* the relevant position counters) in order to maintain an ordered cache w.r.t. the score of the cached items
* In order to perform cache reordering in any of these two cases, we have to know the index (int ind) of the relevant item in the cache - then, the index of the next
* item at its left or right is simply ind-1 or ind+1, respectively. In order to know at anytime this index, we store the position counter of the cached objects in a
* reqID - counter HashMap called positions. That way, we avoid the use of a "for loop".
* Moreover, we use a reqID - Boolean flag HashMap called inCache which puts a value true for the reqID of an object when this object is in the cache. That way, we
* avoid using a "for loop" in the cache lookup method (to find whether the requested item is in the cache, i.e. cache hit, or not, i.e. cache miss).
* Also we use a boolean flag isMoreThanOne to signify that the current cache size is >1 (it could be avoided).
* Finally, since we use simple, static, fixed-size arrays which don't have a size() method to get their current size, we use two int fields - a cacheSize and a
* windowSize - which we increase or set appropriately in order to store the current cache or window size. That way, we avoid the use of a "for loop" and the increment
* of a counter until the first null object is found.
* @author The Higgs Boson
* @version 5.0
*/
public class WindowLFU {
///////////////////////////////////////////////
// member attributes
/** Max cache size */
private int M;
/** Max window size */
private int K;
/** Cache position counter */
private int counter;
/** Window position counter */
private int winCounter;
/** Current cache size */
private int cacheSize;
/** Current window size */
private int windowSize;
/** Flag for more than 1 items in cache */
private boolean isMoreThanOne;
/** Cache */
private Request[] cache;
/** Window */
private Request[] window;
/** Map with boolean flags to check whether an item is in cache or not */
private Map<Integer, Boolean> inCache;
/** Map of reqID (K) - Score (V) */
private Map<Integer, Integer> scores;
/** Map of positions in the cache */
private Map<Integer, Integer> positions;
/** Logging Utility */
private Logger logger = Logger.getLogger(WindowLFU.class.getSimpleName());
///////////////////////////////////////////////
// member methods
/**
* Constructor
* @param M Max cache size
* @param K Max request size
* @param N Number of items
*/
public WindowLFU(int M, int K, int N) {
// initialize max cache size and max window size
this.M = M;
this.K = K;
// initialize counter and window counter
counter = 0;
winCounter = 0;
// initialize current cache size and current window size
cacheSize = 0;
windowSize = 0;
// initialize isMoreThanOne flag
isMoreThanOne = false;
// Allocate cache and window
this.cache = new Request[M];
this.window = new Request[K];
// Allocate inCache, scores, and positions maps
inCache = new HashMap<Integer, Boolean>(N);
scores = new HashMap<Integer, Integer>(N);
positions = new HashMap<Integer, Integer>(N);
}
/** Clear cache */
public void clearCache() {
// fill in the cache with null objects
Arrays.fill(cache, null);
}
/** Clear window */
public void clearWindow() {
// clear window
Arrays.fill(window, null);
}
/** Print cache contents */
public void printCache() {
// set logging level
logger.setLevel(Level.OFF);
// string variable for holding textual representation of cache contents
String str = "";
// scan the cache
for(int i = 0; i < this.cache.length; i++) {
// if the item is not null
if(this.cache[i] != null) {
// assign reqID of item to the string variable
str += (this.cache[i].reqID + " | ");
}
}
// print cache contents
logger.info("PRINT: CACHE: ReqID: " + str);
}
/** Print window contents */
public void printWindow() {
// set logging level
logger.setLevel(Level.OFF);
// string variable for holding textual representation of window contents
String str = "";
// scan the window
for(int i = 0; i < this.window.length; i++) {
// if the request is not null
if(this.window[i] != null) {
// assign reqID of items to the string variable
str += (this.window[i].reqID + " | ");
}
}
// print window contents
logger.info("PRINT: WINDOW: ReqID: " + str);
}
/**
* Getter for current cache size
* @return Current cache size
*/
public int getCacheSize() {
// return the current cache size
return cacheSize;
}
/**
* Getter for current window size
* @return Current window size
*/
public int getWindowSize() {
// return the current window size
return windowSize;
}
/**
* Getter for score of item
* @param request The item
* @return The score of the item
*/
public int getScore(Request request) {
// return score of item
return this.scores.get(request.reqID);
}
/** Print score of cached items */
public void printScores() {
// set logging level
logger.setLevel(Level.OFF);
// scan the cache
for(int i = 0; i < this.cache.length; i++) {
// if the item is not null
if(this.cache[i] != null) {
// print reqIDs and scores
logger.info("PRINT: SCORES: ReqID: " + this.cache[i].reqID + " | " + "Score: " + getScore(this.cache[i]));
}
}
}
/**
* Cache insertion operation
* @param request The requested item that is inserted into the cache
*/
public void doCacheInsert(Request request) {
// set logging level
logger.setLevel(Level.OFF);
// logger.info("TEST: CACHE SIZE: " + cacheSize());
// if this is the first item inserted into the cache
if(cacheSize == 0) {
// set counter
counter = M-1;
// test
// logger.info("TEST: INSERTION: ReqID: " + request.reqID + " | " + "Counter: " + counter);
// insert item at index counter
this.cache[counter] = request;
// increase cache size by 1
cacheSize += 1;
// put position index into positions list
this.positions.put(request.reqID, counter);
}
// if this is not the first item inserted into the cache
else {
//if the cache has not reached its max size
if(cacheSize != this.cache.length) {
// decrease counter by 1
counter -= 1;
// test
// logger.info("TEST: INSERTION: ReqID: " + request.reqID + " | " + "Counter: " + counter);
// insert item at index counter
this.cache[counter] = request;
// put position index into positions list
this.positions.put(request.reqID, counter);
// set isMoreThanOne flag
isMoreThanOne = true;
// increase cache size by 1
cacheSize += 1;
}
// if the cache has reached its max size
else {
// set cache size to cache capacity
cacheSize = M;
// reset counter to M-1
counter = M-1;
// test
// logger.info("TEST: INSERTION: ReqID: " + request.reqID + " | " + "Counter: " + counter);
// insert item at index counter
this.cache[counter] = request;
// put position index into positions list
this.positions.put(request.reqID, counter);
}
}
// activate flag for item in inCache map
this.inCache.put(request.reqID, true);
// print message
logger.info("CACHE INSERT: The requested item with ID: " + request.reqID + " has been inserted into the cache at index: " + this.positions.get(request.reqID));
}
/**
* Increase score of item by 1
* @param request The item
*/
public void incScore(Request request) {
// if the item is not in the score map
if(!this.scores.containsKey(request.reqID)) {
// increase its score to 1 and put the reqID-score pair to the scores map
this.scores.put(request.reqID, 1);
}
// else
else {
// temp score value
int reqCount = this.scores.get(request.reqID);
// increase score by 1
reqCount += 1;
// put the reqID-score pair to the winFreqs map
this.scores.put(request.reqID, reqCount);
}
}
/**
* Decrease score of item by 1
* @param request
*/
public void decWinFreq(Request request) {
// temp score value
int reqCount = this.scores.get(request.reqID);
// decrease score by 1
reqCount -= 1;
// put the reqID-score pair to the winFreqs map
this.scores.put(request.reqID, reqCount);
}
/**
* Insertion of request in the window
* Performs cache reordering due to eviction of a request from the cache, if required
* @param request The request
*/
public void doWindowInsert(Request request) {
// set logging level
logger.setLevel(Level.OFF);
// if this is the first request inserted into the window
if(windowSize == 0) {
// set window position counter
winCounter = K-1;
// insert request at index winCounter
this.window[winCounter] = request;
// increase the score of that item by 1
incScore(request);
// increase window size by 1
windowSize += 1;
// print message
logger.info("WINDOW INSERTION: A request for the item with ID: " + request.reqID + " has been inserted into the window and the score of that item has been updated to: " + getScore(request));
}
// if this is not the first request inserted into the window
else {
// if the window has not reached its capacity
if(windowSize != this.window.length) {
// decrease winCounter by 1
winCounter -= 1;
// insert request at index winCounter
this.window[winCounter] = request;
// increase the score of that item by 1
incScore(request);
// increase window size by 1
windowSize += 1;
// print message
logger.info("WINDOW INSERTION: A request for the item with ID: " + request.reqID + " has been inserted into the window and the score of that item has been updated to: " + getScore(request));
}
// if the window has reached its capacity
else {
// set windowSize equal to window max size
windowSize = K;
// request to be removed from the window - right-most request in the window
Request reqToBeRemoved = this.window[this.window.length-1];
// decrease the score of that item by 1
decWinFreq(reqToBeRemoved);
// if winCounter becomes smaller than 0
if(winCounter < 0) {
// reset it to K-1
winCounter = K-1; // i.e. same effect as sliding window
}
// insert request at index winCounter
this.window[winCounter] = request;
// increase the score of that item by 1
incScore(request);
// decrease winCounter by 1
winCounter -= 1;
// print messages
logger.info("WINDOW EVICTION: A request for the item with ID: " + reqToBeRemoved.reqID + " has been evicted from the window and the score of that item has been updated to: " + getScore(reqToBeRemoved));
logger.info("WINDOW INSERTION: A request for the item with ID: " + request.reqID + " has been inserted into the window and the score of that item has been updated to: " + getScore(request));
// check for cache reordering due to the eviction of a request from the window
// if item reqToBeRemoved is in the cache and it is not the only item in the cache and it is not the right-most item
if((this.inCache.get(reqToBeRemoved.reqID) == true) && (isMoreThanOne == true) && (!this.cache[this.cache.length-1].equals(reqToBeRemoved))) {
// index of reqToBeRemoved in the cache
int ind = positions.get(reqToBeRemoved.reqID);
// index of item at its right
int indRight = ind + 1;
// item at its right
Request itemRight = this.cache[indRight];
// if the score of itemRight is now greater than the score of reqToBeRemoved
if(getScore(itemRight) > getScore(reqToBeRemoved)) {
// put reqToBeRemoved at index indRight
this.cache[indRight] = reqToBeRemoved;
// update its counter
this.positions.put(reqToBeRemoved.reqID, indRight);
// put itemRight at index ind
this.cache[ind] = itemRight;
// update its counter
this.positions.put(itemRight.reqID, ind);
// print messages
logger.info("CACHE REORDERING DUE TO EVICTION OF A REQUEST FROM THE WINDOW");
logger.info("The following items with the following scores exchanged position in the cache");
logger.info("ReqID: " + reqToBeRemoved.reqID + " score: " + getScore(reqToBeRemoved));
logger.info("ReqID: " + itemRight.reqID + " score: " + getScore(itemRight));
// print cache
printCache();
}
}
}
}
}
/**
* If the item is not in the inCache map, put it and set its value at false
* @param request The item
*/
public void initInCache(Request request) {
// if the item is not in the inCache map
if(!this.inCache.containsKey(request.reqID)) {
// insert it and set its value at false
this.inCache.put(request.reqID, false);
}
}
/**
* Cache lookup operation - returns true if the requested item is in the cache (cache hit)
* @param request The requested item
* @return true in case of cache hit
*/
public boolean doCacheLookup(Request request) {
// set logging level
logger.setLevel(Level.OFF);
// put the item in the inCache map if it is not there and set its value to false
initInCache(request);
// if the requested item is in the cache (cache hit)
if(this.inCache.get(request.reqID) == true) {
// print message
logger.info("LOOKUP: CACHE HIT: The requested item with ID: " + request.reqID + " is in the cache");
// return true
return true;
}
// else (cache miss)
else {
// print message
logger.info("LOOKUP: CACHE MISS: The requested item with ID: " + request.reqID + " is NOT in the cache");
// return false
return false;
}
}
/**
* Performs replacement if the score of the requested item is at least equal to the score of the least-valuable cached item
* @param request The requested item
*/
public void doCacheReplace(Request request) {
// set logging level
logger.setLevel(Level.OFF);
// item to be removed from the cache - right-most item in the cache array
Request reqToBeRemoved = this.cache[this.cache.length-1];
// if the score of the requested item is at least equal to the score of reqToBeRemoved
if(getScore(request) >= getScore(reqToBeRemoved)) {
// test
// logger.info("TEST: REPLACEMENT: ReqID: " + reqToBeRemoved.reqID + " | " + "Counter: " + positions.get(reqToBeRemoved.reqID));
// replace reqToBeRemoved by the requested item
doCacheInsert(request);
// set the inCache flag of reqToBeRemoved to false
this.inCache.put(reqToBeRemoved.reqID, false);
// print messages
logger.info("REPLACEMENT: Least-valuable cached item has ID: " + reqToBeRemoved.reqID + " and score: " + getScore(reqToBeRemoved));
logger.info("REPLACEMENT: Requested item has ID: " + request.reqID + " and score: " + getScore(request));
logger.info("REPLACEMENT: Requested item replaced least-valuable cached item");
}
// else
else {
// print messages
logger.info("REPLACEMENT: Least-valuable cached item has ID: " + reqToBeRemoved.reqID + " and score: " + getScore(reqToBeRemoved));
logger.info("REPLACEMENT: Requested item has ID: " + request.reqID + " and score: " + getScore(request));
logger.info("REPLACEMENT: No replacement will take place");
}
}
/**
* Performs cache reordering due to cache hit, if required
* @param request The requested item
*/
public void doCacheReorderCacheHit(Request request) {
// set logging level
logger.setLevel(Level.OFF);
// if the cache has more than one items and the requested item is not the left-most cached item
if((isMoreThanOne == true) && (!this.cache[this.cache.length - cacheSize].equals(request))) {
// test
// logger.info("TEST: REORDER DUE TO CACHE HIT: ReqID: " + request.reqID + " | " + "Counter: " + positions.get(request.reqID));
// index of requested item
int ind = this.positions.get(request.reqID);
// index of item at its left
int indLeft = ind-1;
// item at its left
Request itemLeft = this.cache[indLeft];
// if the score of the requested item is at least equal to the score of itemLeft
if(getScore(request) >= getScore(itemLeft)) {
// put requested item at index indLeft
this.cache[indLeft] = request;
// update its counter
this.positions.put(request.reqID, indLeft);
// put itemLeft at index ind
this.cache[ind] = itemLeft;
// update its counter
this.positions.put(itemLeft.reqID, ind);
// print messages
logger.info("CACHE REORDERING DUE TO CACHE HIT");
logger.info("The following items with the following scores exchanged position in the cache");
logger.info("ReqID: " + request.reqID + " score: " + getScore(request));
logger.info("ReqID: " + itemLeft.reqID + " score: " + getScore(itemLeft));
// print cache
printCache();
}
}
}
}
Code for LRU for comparison:
//////////////////////////////////////////////////////
// package declaration
package algorithms;
//////////////////////////////////////////////////////
// import of system classes and utilities
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;
import java.util.logging.Level;
import java.util.logging.Logger;
//////////////////////////////////////////////////////
// import of user-defined classes
import requests.Request;
/**
* Least Recently Used (LRU) cache replacement algorithm
* Cache is as a doubly-ended queueu implemented as an Array (ArrayDeque) of size M
* Insertion of objects from the left of the list, eviction at the right
* When the cache has reached its capacity and upon a cache miss, the right-most cached item
* (LRU item) is evicted from the cache, i.e. the cache holds the most recently requested items
* Upon a cache hit, cache reordering might take place with the relevant item moved at the beginning of
* the cache list if it is not already there
* @author The Higgs Boson
* @version 5.0
*/
public class LRU {
//////////////////////////////////////////////////////
// member attributes
/** Max cache size */
private int M;
/** LRU cache */
private Deque<Request> cacheLRU = new ArrayDeque<Request>(M);
/** Map inCache */
private Map<Integer, Boolean> inCache;
/** Logging utility */
private Logger logger = Logger.getLogger(LRU.class.getSimpleName());
//////////////////////////////////////////////////////
// member methods
/**
* Constructor
* @param M Max cache size
*/
public LRU(int M, int N) {
// initialize max cache size
this.M = M;
// Allocate inCache map
inCache = new HashMap<Integer, Boolean>(N);
}
/** Clear cacheLRU */
public void clearCacheLRU() {
// clear cacheLRU
this.cacheLRU.clear();
}
/**
* Getter for current cacheLRU size
* @return cacheLRU.size() Current cacheLRU size
*/
public int getCacheLRUSize() {
// return current cacheLRU size
return this.cacheLRU.size();
}
/** Print cacheLRU contents */
public void printCacheLRU() {
// set logging level
logger.setLevel(Level.OFF);
// String variable for holding textual representation of cacheLRU contents
String str = "";
// scan cacheLRU
for(Request r : this.cacheLRU) {
// take the reqID of cached items and put them into string variable str
str += (r.reqID + " | ");
}
// print cacheLRU contents
logger.info("PRINT: Cache contents: " + str);
}
/**
* If the item is not in inCache map, insert it and put its value at false
* @param request The item
*/
public void initInCache(Request request) {
// if the item is not in the inCache map
if(!this.inCache.containsKey(request.reqID)) {
// insert it and set its value at false
this.inCache.put(request.reqID, false);
}
}
/**
* Cache lookup operation
* @param request The requested item
* @return true If the requested item is found in the cache (cache hit)
*/
public boolean doLookupCacheLRU(Request request) {
// set logging level
logger.setLevel(Level.OFF);
// init inCache
initInCache(request);
// if the requested item is in cache (cache hit)
if(this.inCache.get(request.reqID) == true) {
// cache reordering due to cache hit in two steps
// 1. remove relevant cached item from the cache
cacheLRU.remove(request);
// 2. add this item to the end of the cache
cacheLRU.add(request);
// print message
logger.info("LOOKUP: CACHE HIT: The requested item with reqID: " + request.reqID + " is already stored in the cache");
// return true
return true;
}
// else (cache miss)
else {
// print message
logger.info("LOOKUP: CACHE MISS: The requested item with reqID: " + request.reqID + " is not stored in the cache");
// return false
return false;
}
}
/**
* Cache insertion operation
* @param request The requested item
*/
public void doInsertCacheLRU(Request request) {
// set logging level
logger.setLevel(Level.OFF);
// add the requested item at the end of the cache list
this.cacheLRU.add(request);
// set its flag to true
this.inCache.put(request.reqID, true);
// print message
logger.info("INSERTION: The requested item with reqID: " + request.reqID + " has been inserted into the cache");
}
/**
* Cache replacement operation
* @param request The requested item
*/
public void doReplacementCacheLRU(Request request) {
// set logging level
logger.setLevel(Level.OFF);
// print message
logger.info("The cache has reached its capacity");
// item to be evicted
Request reqToBeRemoved = this.cacheLRU.getFirst();
// evict the left-most cached item from the cache
this.cacheLRU.removeFirst();
// set its flag to false
this.inCache.put(reqToBeRemoved.reqID, false);
// insert new requested item at the end of the cache list
this.cacheLRU.add(request);
// set its flag to true
this.inCache.put(request.reqID, true);
// print message
logger.info("REPLACEMENT: The requested item with reqID: " + request.reqID + " replaced the LRU item with reqID: " + reqToBeRemoved.reqID);
}
}
Just for the sake of comparison, with this configuration, i.e.:
Number of items: N = 1,000,000 Number of requests: numR = 2,000,000 Cache size: M = 10,000
LRU takes about 15 seconds.
WindowLFU, on the other hand, with the same configuration and a window size K = 2,000,000, after 15 seconds has only processed about 3,000 out of the 2,000,000 requests! This doesn't seem to change when I use a smaller window size (e.g. K = 100,000).
