1

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?

  • 1
    Do you have a view as to how many entries you expect? The best approach depends on scale. If the data is sparse then your 2D array is going to be very wasteful for resources. You may want to consider a hash map implementation if you have more than a 100 with the port and vlan as a compound key. – Jason K. Apr 4 '17 at 5:13
  • Even with the simplest possible implementation (two-dimensional array), the data would occupy about 960 KB, which isn't that much if you're not memory-constrained. – Blrfl Apr 4 '17 at 14:44
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.

1

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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