How do I best store a value with multiple keys?

Question

I need to store two 32-bit numbers in a way that is quickly accessible and as storage space efficient as possible. My keys are a combination of the following two

values:
port: 0 - 29
vlan: 1 - 4095

struct Dat_s{
    int id;
    int val;
} Dat_t;

Also I need to pre-allocate all the storage that could be taken up in a worst case.

Is the best way to store it in a two dimensional array like: Dat_t Content[29][4094]? Or is there a better way?

Answer 1

For lots of programming tasks there is often a tradeoff between speed and memory. In your case, you can probably speed things up if one of the array dimensions is rounded up to the next larger power of 2. That becomes clear when you use a one dimensional array for the storage and do the adress calculation on your own.

For the sake of simplicity, lets assume vlan is in the range 0...4094, and look at this example (pseudo code):

Dat_t getContent(port,vlan) 
{
    return Content[port * MAXVLAN + vlan];
    // or
    return Content[vlan * MAXPORT + port];
}

If either MAXVLAN or MAXPORT is a power of two, the multiplication is a just a shift operation, which is typically faster on most contemporary processor architectures than a multiplication with an arbitrary number. So you can pick MAXVLAN=4096 or MAXPORT=32 (and waste some entries in your array), or MAXVLAN=4095 or MAXPORT=30 (which is memory efficient, but wastes some CPU cycles). So pick your choice.

Answer 2

What do you precisely mean by "quickly accessible", in number of instructions for your target machine ? Computing the address of a cell in a two dimensional array implies 2 adds and 1 multiply. A hash much more (and i'm not sure you can preallocate it's memory).

What is your "worst case" ?

If your matrix tends to be sparse in one dimension (for example, most ports are used for a small (let's say 100) number of vlans), you could allocate a [100][29] matrix for the Dat_s and a [4096] array containing indices in the [100][29] matrix, then handle the allocation of the 100 indices to the 4096 vlans.