paging.cs

const int KeysMax = 1024 * 1024; // 1MB
const int ValueLength = 4096; // 4KB

// using a jagged array. Note that the same arguments apply to algebraic arrays, though they are not as severe
byte[][] goodLut = new byte[KeysMax][];
for(int i = 0; i < KeysMax; i++) {
    goodLut[i] = new int[ValueLength];
}

byte[][] badLut = new byte[ValueLength][];
for(int i = 0; i < ValueLength; i++) {
    badLut[i] = new int[KeysMax];
}

// let's say we want to initialize the chunk with index 2568 to 0xFF
{
    int key = 2568;

    //// using the GOOD layout option..
    for(int i = 0; i < ValueLength; i++) {
        goodLut[key][i] = 0xFF;
    }
    
    //// using the BAD layout option..
    for(int i = 0; i < ValueLength; i++) {
        badLut[i][key] = 0xFF;
    }

    //// Notice that we can optimize the good option..
    byte[] value = goodLut[key];
    for(int i = 0; i < ValueLength; i++) {
        value[i] = 0xFF;
    }
    
    /* But we cannot optimize the bad layout option :(
     * Why does this matter?
     *
     * First off notice how the optimized form of the good option requires 1 + ValueLength accesses to set 
     * all the values of a chunk.
     * The bad option always requires 2 * ValueLength accesses to set all the values of the chunk.
     * 
     * But what's worse is that the bad option always has to access every array. If they are spreas across 
     * multiple memory pages, which will force to operation system to always swap all the lookup table's 
     * pages in, even if you read a single chunk. 
     * 
     * The good option on the other hand only requires only the pages with the accessed chunk to be swapped
     * in, which is especially good if the chunk can fit into a single page.
     *
     * Depending on how the data is accessed, the good option may not result in fewer page swaps, however
     * the bad option will always result in the worst amount of page swaps.
     */
}