LFU-like web caching replacement algorithm

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

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

StackExchange Code Review Q#42898, answer score: 4