3
\$\begingroup\$

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).

\$\endgroup\$

2 Answers 2

4
\$\begingroup\$

I appreciate that this is non-trivial code and I can see why you would like to have lots of comments, but code like below is probably taking it a bit too far:

// else
else {

// increase score by 1
reqCount += 1;

Especially in the second example, if you need to tell an observer that reqCount is in fact a score, call the variable "score".

Instead of your inCache Map, I think a Set<Integer> is a better fit. Doing this will also have the benefit of not being a memory leak. (Currently you can end up adding an arbitrary number of entried into inCache, but you never remove any entries.)

I don't have any complete explanation for why your LFU code is so much slower, but when measuring, you should comment out all your logging statements. Setting log level to "off" is a good start, but the argument to the log statement is still evalued, so you concatenate strings and do method calls there.

Also, your LFU code relies on Request.equals(Object). If this is an expensive operation it will naturally slow thing down. You didn't supply the code for Request, so I can't tell if this is a problem or not.

Edit: When there are significant performance hits, like the one you've run into, it is fairly uncommon that the problem is that you do a HashMap lookup too much, or instantiate an extra object, or similar things. Instead, keep a look out for excessive concatenation of Strings, IO operations, looping, or the use of the wrong datastructures (such as doing list.get(int) on a LinkedList). To be honest, when looking at your code, my best guess was that the Request.equals method was the culprit, so now I'm a bit at a loss.

\$\endgroup\$
6
  • \$\begingroup\$ Regarding the Set<Integer>, I need a mapping between reqID and inCache flag, therefore I don't understand how I can use a set instead of a map. Regarding commecting out the logging statements, I was not aware of that! Finally, the overriding of the equals method was really simple: public boolean equals(Object obj) { Request req = (Request) obj; if(this.reqID == req.reqID) { return true; } return false; } \$\endgroup\$
    – PeterHiggs
    Commented Feb 26, 2014 at 22:33
  • \$\begingroup\$ Sorry about the formatting, I could not find how to add code blocks in comments. \$\endgroup\$
    – PeterHiggs
    Commented Feb 26, 2014 at 22:35
  • \$\begingroup\$ My idea regarding the Set is that reqId in cache is also in the Set. Then you can use inCache.contains(int) to get information on if the request is in cache or not. \$\endgroup\$
    – Buhb
    Commented Feb 26, 2014 at 22:45
  • \$\begingroup\$ Oh, I see, yes that makes perfect sense! Thank you! \$\endgroup\$
    – PeterHiggs
    Commented Feb 26, 2014 at 22:49
  • \$\begingroup\$ I have one idea to get rid of the remaining maps too. If instead of a positions map and a scores map I use somehow a position field and a score field in the Request class, as I use a reqID field, then there will be no need to have these maps with N key-value pairs, right? This might give a significant performance boost. Do you find this idea reasonable? What's your thoughts about it? EDIT: And similarly an inCache boolean field to get rid of the Set too! \$\endgroup\$
    – PeterHiggs
    Commented Feb 26, 2014 at 23:07
3
\$\begingroup\$

You didn't provide much information about how you conducted your comparative stress tests wrt. LFU vs. LRU, so I'll assume you simply forced random access requests over the possible set of keys (i.e., your request.reqID, as I understand it).

If so, what I observed with my own implementation is that the LRU eviction and replacement strategy will typically outperforms LFU for such requests that map equiprobable frequencies over the set of accessed keys.

Conversely, LFU starts to perform better when there is more disparity / imbalance in the distribution of the access frequencies of the keys, e.g., say, when some requested keys have high use counts, and other requested keys are accessed less (or much less) frequently. Heuristically, this is for instance the case when your domain model has, e.g., say, keys mapping onto "very popular vs. little popular" categories, etc.

As I found out, LFU's bookkeeping of the use counts (or frequencies, or whatever we call it) incurs a significant overhead compared to that of the more straightforward LRU/MRU algorithm and data structure, better suited to cope with equiprobable access scenarios.

Although my implementation of LRU is essentially equivalent to yours, AFAICT, my LFU isn't, however. Instead of SW-LFU, I baked my own, where I keep track of the use counts (or frequencies) in dictionaries indexed by the logarithm base 2 of the use counts.

I did so in order to minimize the use count bookkeeping overhead / fragmentation, in the pathological case for LFU where key1 is accessed once, key2 twice, key3 three times, key4 four times, etc (which would make the evictable frequency collection grow as large as the set of distinct keys, up to the cache capacity M).

Here are the relevant bits, you may find interesting

(just the helper class used internally by the LFU cache implementation for the bookkeeping of the keys use counts)

public class LfuEvictableCollection<TKey> : IUseTrackingCollection<TKey>
{
    internal sealed class KeyUse
    {
        internal const int None = -1;

        private long value;

        private int msb = None;

        internal int Increment()
        {
            var mask = 1L << (msb + 1);
            if ((++value & mask) == mask)
            {
                msb++;
            }
            return msb;
        }

        internal long Count { get { return value; } }

        // Reflects the logarithm base 2 of the use count
        internal int Msb { get { return msb; } }
    }

    private IDictionary<TKey, KeyUse> uses;

    // We dispatch used keys in use counts partitions, indexed by
    // the logarithm base 2 of the keys' use counts; thus,
    // the single set of keys which have been accessed only once will be in keys[0];
    // the (up to) 2 sets of keys which have been accessed 2 to 3 times, in keys[1];
    // the (up to) 4 sets of keys which have been accessed 4 to 7 times, in keys[2];
    // the (up to) 8 sets of keys which have been accessed 8 to 15 times, in keys[3];
    // the (up to) 16 sets of keys which have been accessed 16 to 31 times, in keys[4];
    // etc, etc.
    private IDictionary<int, HashSet<TKey>> keys;

    public LfuEvictableCollection()
        : this(0)
    {
    }

    public LfuEvictableCollection(int capacity)
    {
        uses = new Dictionary<TKey, KeyUse>(capacity);
        keys = new Dictionary<int, HashSet<TKey>>(Msb(long.MaxValue) + 1);
        Initialize();
    }

    // Get the most significant bit (index) of n, assumed positive
    // (for long.MaxValue, signed 64-bit integer maximum, this is 62)
    // or -1, if n is zero
    private static int Msb(long n)
    {
        if (n > 0)
        {
            var max = long.MaxValue;
            var msb = 0;
            while (n <= max) max /= 2;
            max += 1;
            while (0 < (max /= 2)) msb++;
            return msb;
        }
        return KeyUse.None;
    }

    // Get the logarithm base 2 of the least often used keys' use count,
    // or -1 if no keys have ever been used
    private int Min()
    {
        var msb = 0;
        while (msb < keys.Count && keys[msb].Count < 1)
        {
            msb++;
        }
        return msb < keys.Count ? msb : KeyUse.None;
    }

    protected virtual void Initialize()
    {
        TotalUseCount = 0;
        keys.Clear();
        uses.Clear();
    }

    #region IUseTrackingCollection<TKey> implementation
    public void Use(TKey key)
    {
        var use = uses[key];
        var last = use.Msb;
        var next = use.Increment();
        TotalUseCount++;
        if (last < next)
        {
            if (last > KeyUse.None)
            {
                keys[last].Remove(key);
            }
            if (!keys.ContainsKey(next))
            {
                keys.Add(next, new HashSet<TKey>());
            }
            keys[next].Add(key);
        }
    }

    public IEnumerable<TKey> GetLeastFrequentlyUsed(int maxCount)
    {
        if (maxCount <= 0)
        {
            throw new ArgumentOutOfRangeException("maxCount", "must be strictly greater than zero");
        }
        var msb = Min();
        if (msb > KeyUse.None)
        {
            while (maxCount > 0 && msb < this.keys.Count)
            {
                var keys = this.keys[msb];
                foreach (var key in keys)
                {
                    maxCount--;
                    yield return key;
                }
                msb++;
            }
        }
        if (maxCount > 0)
        {
            foreach (var key in this.uses.Keys)
            {
                if (maxCount > 0)
                {
                    maxCount--;
                    yield return key;
                }
                else
                {
                    break;
                }
            }
        }
    }

    public long TotalUseCount { get; private set; }
    #endregion

    #region ICollection<TKey> implementation
    public void Add(TKey key)
    {
        var use = new KeyUse();
        uses.Add(key, use);
    }

    public void Clear()
    {
        Initialize();
    }

    public bool Contains(TKey key)
    {
        return uses.ContainsKey(key);
    }

    public void CopyTo(TKey[] array, int index)
    {
        var keys = uses.Keys.ToArray();
        keys.CopyTo(array, index);
    }

    public bool Remove(TKey key)
    {
        KeyUse use;
        if (uses.TryGetValue(key, out use))
        {
            var msb = use.Msb;
            TotalUseCount -= use.Count;
            if (keys.ContainsKey(msb))
            {
                keys[msb].Remove(key);
            }
            uses.Remove(key);
            return true;
        }
        return false;
    }

    public int Count
    {
        get
        {
            return uses.Count;
        }
    }

    public bool IsReadOnly
    {
        get
        {
            return false;
        }
    }
    #endregion

    #region IEnumerable<TKey> implementation
    public IEnumerator<TKey> GetEnumerator()
    {
        return ((IEnumerable<TKey>)uses.Keys).GetEnumerator();
    }
    #endregion

    #region IEnumerable implementation
    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
    #endregion
}

(Yes, I know this is C# and not Java but I believe it is relatively straightforward, and shouldn't be too difficult to port to Java, if you so wish)

Performance figures-wise, on an Intel Duo Core 2 @ 2.9 Ghz desktop box running Windows 7 64bit + .NET 4.0, and after I adapt my test to the cache size (10,000 slots) and working set (1,000,000 items) that you mentioned

-- only with a greater number of requests, 5 times fold (i.e., 10 millions, instead of 2 millions) --

I observe:

For LRU:
Cache size = 10,000
Number of items = 1,000,000
Number of requests = 10,000,000
Time elapsed: ~ 10 seconds

For LFU:
Cache size = 10,000
Number of items = 1,000,000
Number of requests = 10,000,000
Time elapsed: ~ 14 seconds

(again, in the test case I assumed of an equiprobable distribution of frequencies over the set of accessed keys, more LRU-friendly than it is to LFU)

Because my generic cache library is quite involved and opinionated, I can't post the full source code here for obvious readability reasons, but it is browsable here.

Hope this helps,

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.