Cache Implemented Using an Array - ArrayIndexOutOfBoundsException (Java)

Question

I simulate a web cache replacement algorithm. I have N objects of type Request available for caching and L requests for those objects that arrive to the cache in a serial fashion.

Request objects are distinguished by their int field reqID (a numeric ID from 0 up to N-1). I have override equals to be able to compare Request objects.

I implement a cache using an array - a simple, plain, static array.

The cache is filled with objects of type Request and has a max size M:

/** Max cache size */
private int M;

/** Cache */
private Request[] cache = new Request[M];

I have insertions, evictions and replacements of objects in the cache.

I have also a sliding window of the last K requests implemented as an ArrayDeque:

/** Max window size */
private int K;

/** Window */
private Deque<Request> window = new ArrayDeque<Request>(K);

Values M and K are initialized at the constructor and set at main().

I keep the score (request count in a sliding window of last K requests) of the objects in a HashMap:

/** Map of reqID (K) - Score (V) */
Map<Integer, Integer> score;

I keep the cache ordered in terms of the score of the cached items, with the highest score being at the left end and the lowest score being at the right end.

Due to the fact that when I have a cache hit for an item its score is increased by 1 while when I have a request for an item dropped from the window the score of that item is decreased by 1, in those cases I might have cache reordering with the relevant item exchanging position in the cache with the next item at its left or right, respectively. Therefore, I should be able to know the index of each (random) item in the cache at any given time. For that purpose, I use an integer field called counter and a HashMap called positions:

/** Counter = position in the cache */
private int counter;

/** Map of ReqID (K) - Counter (V) */
private Map<Integer, Integer> positions;

Finally, I use an inCache map in order to avoid the "for loop" in lookup operation:

/** Map with boolean flags to check whether an item (ReqID) is in cache or not */
private Map<Integer, Boolean> inCache;

and an isMoreThanOne flag to avoid calling the getter for the current cache size when this size is large:

/** Flag for more than 1 items in cache */
private boolean isMoreThanOne;

The reason is that, since my cache is a vanilla array and not an ArrayList, it does not have a size() method, and length field is the fixed capacity given, not the current cache size. Therefore, in order to get the current cache size, I should do the following (please take a look since I am not 100% if it is correct):

/**
 * Getter for current cache size
 * @return  Current cache size
 */
public int getCacheSize() {

    // temp counter
int count = 0;

// scan the cache
for(int i = 0; i < this.cache.length; i++) {

    // as long as the items are not null
    if(this.cache[i] != null) {

        // increase the counter by 1
    count += 1;

    }

    // when the first null item found
    else {

        // jump out of the loop
    break;

    }

}

// return the current cache size (counter)
return count;
}

After that long but neccessary introduction, here is the code of cache insertion where I get an ArrayIndexOutOfBoundsException:

/**
 * Cache insertion operation
 * @param request   The requested item that is inserted into the cache
 */
public void doCacheInsert(Request request) {

    // if this is the first item inserted into the cache
if(getCacheSize() == 0) {

    // set counter
    counter = M-1;

    // insert item at index counter
    this.cache[counter] = request;    // HERE I HAVE THE MESSAGE

    // 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(getCacheSize() != this.cacheWindowLFU.length) {

        // decrease counter by 1
    counter -= 1;

    // 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;

    }

    // if the cache has reached its max size
    else {

        // reset counter to M-1
    counter = M-1;

    // insert item at index counter
    this.cache[counter] = request;

    }

}

// activate flag for item in inCache map
this.inCache.put(request.reqID, true);

}

I get the message almost right at the beginning of this method, at the 1st if block at the line:

// insert item at index counter
this.cache[counter] = request;

... and I really don't know why!

EDIT: Here is my constructor:

/**
 * Constructor
 * @param M Max cache size
 * @param K Max window size
 * @param N Number of items
*/
public Algorithm(int M, int K, int N) {

    // initialize max cache size and max window size
this.M = M;
this.K = K;

// initialize counter
counter = 0;

// initialize isMoreThanOne flag
isMoreThanOne = false;

// allocate inCache, winFreqs, and positions maps
inCache     = new HashMap<Integer, Boolean>(N);
scores          = new HashMap<Integer, Integer>(N);
positions   = new HashMap<Integer, Integer>(N);

}

And here is the relevant part of main() which is inside Main class:

// stuff..... (e.g. # of sim runs etc.)

// number of items
int numItems = 20;

// number of requests
int numR = 40;

// maximum cache size
int M = 5;

// maximum window size
int K = 3;

// stuff...... (e.g. generation of requests, start of statistics etc.)

// instantianate object of type Algorithm
Algorithm alg = new Algorithm(M, K, numItems);

// stuff..... (e.g. lookup, insertion, replacement, # of hits, hit rate etc.)    

Answer 1

The following variables are initialized with 0 due to instance variables initialization phase.

/** Max cache size */
private int M; //set to 0 by default

/** Cache */
private Request[] cache = new Request[M]; //set to [] by default (an empty array)

Move cache initialization to the constructor, so that cache is initialized while creating Algorithm instance:

/** Cache */
private Request[] cache;

public Algorithm(int M) { 
    this.M = M; 
    this.cache = new Request[M];  // set to Request[M]
}

---

This is the result of initialization blocks order in Java which is as follows:

1. static instance variables (runs only ONCE while first class load)
2. static init block (runs only ONCE while first class load)
3. super-constructors (if any)
4. instance variables (runs every time a new instance is created) --> M and cache set to 0
5. non-static init block (runs every time a new instance is created)
6. constructor --> M updated according to the parameter

Based on the above rule you can see that M was originally defaulted to 0. Value of M was then passed to cache which was allocated with 0 size (an empty array) thus leading to ArrayIndexOutOfBoundsException (no matter what value was assigned to M within constructor, already initialized cache was of 0 size).

Answer 2

private int M;

is the same as

private int M = 0;

so if you don't assign any value for it

    // set counter
    counter = M-1; //if M == 0, then counter = -1

    // insert item at index counter
    this.cache[counter] = request;    // if counter == -1, then you'll get an exception here

will return to you the message

java.lang.ArrayIndexOutOfBoundsException: -1

notice that

private Request[] cache = new Request[M];

where M == 0, is still a valid Java array initialization, but you can't add anything to it