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 declarationpackage algorithms;///////////////////////////////////////////////// import of system classes and utilitiesimport 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 classesimport 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 declarationpackage algorithms;//////////////////////////////////////////////////////// import of system classes and utilitiesimport 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 classesimport 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,000Number of requests: numR = 2,000,000Cache size: M = 10,000LRU 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).  
LFU-like web caching replacement algorithm
java;performance;hash table;cache;complexity