how to efficiently access 3^20 vectors in a 2^30 bits of memory

Question

I want to store a 20-dimensional array where each coordinate can have 3 values, in a minimal amount of memory (2^30 or 1 Gigabyte). It is not a sparse array, I really need every value. Furthermore I want the values to be integers of arbirary but fixed precision, say 256 bits or 8 words

example;

set_big_array(1,0,0,0,1,2,2,0,0,2,1,1,2,0,0,0,1,1,1,2, some_256_bit_value);

and

get_big_array(1,0,0,0,1,2,2,0,0,2,1,1,2,0,0,0,1,1,1,2, &some_256_bit_value);

Because the value 3 is relative prime of 2. its difficult to implement this using efficient bitwise shift, and and or operators. I want this to be as fast as possible.

any thoughts?

Answer 1

There are 3.48e9 variants of 20-tuple of indexes that are 0,1,2. If you wish to store a 256 bit value at each index, that means you're talking about 8.92e11 bits - about a terabit, or about 100GB.

I'm not sure what you're trying to do, but that sounds computationally expensive. It may be reasonable feasible as a memory-mapped file, and may be reasonably fast as a memory-mapped file on an SSD.

What are you trying to do?

So, a practical solution would be to use a 64-bit OS and a large memory-mapped file (preferably on an SSD) and simply compute the address for a given element in the typical way for arrays, i.e. as sum-of(forall-i(i-th-index * 3^i)) * 32 bytes in pseudeo-math. Or, use a very very expensive machine with that much memory, or another algorithm that doesn't require this array in the first place.

A few notes on platforms: Windows 7 supports just 192GB of memory, so using physical memory for a structure like this is possible but really pushing it (more expensive editions support more). If you can find a machine at all that is. According to microsoft's page on the matter the user-mode virtual address space is 7-8TB, so mmap/virtual memory should be doable. Alex Ionescu explains why there's such a low limit on virtual memory despite an apparently 64-bit architecture. Wikipedia puts linux's addressable limits at 128TB, though probably that's before the kernel/usermode split.

Assuming you want to address such a multidimensional array, you must process each index at least once: that means any algorithm will be O(N) where N is the number of indexes. As mentioned before, you don't need to convert to base-2 addressing or anything else, the only thing that matters is that you can compute the integer offset - and which base the maths happens in is irrelevant. You should use the most compact representation possible and ignore the fact that each dimension is not a multiple of 2.

So, for a 16-dimensional array, that address computation function could be:

int offset = 0;
for(int ii=0;ii<16;ii++)
    offset = offset*3 + indexes[ii];
return &the_array[offset];

As previously said, this is just the common array indexing formula, nothing special about it. Note that even for "just" 16 dimensions, if each item is 32 bytes, you're dealing with a little more than a gigabyte of data.

Answer 2

You can actually use a pointer-to-array²⁰ to have your compiler implement the index calculations for you:

/* Note: there are 19 of the [3]'s below */
my_256bit_type (*foo)[3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3];

foo = allocate_giant_array();

foo[0][1][1][0][2][1][2][2][0][2][1][0][2][1][0][0][2][1][0][0] = some_256bit_value;

Answer 3

I'll start by doing a direct calculation of the address, then see if I can optimize it

address = 0; for(i=15; i>=0; i--) { address = 3*address + array[i];
}

address = address * number_of_bytes_needed_for_array_value

Answer 4

You might want to take a look at something like STXXL, an implementation of the STL designed for handling very large volumes of data

Answer 5

Maybe i understand your question wrong. But can't you just use a normal array?

INT256 bigArray[3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3];
OR
INT256 ********************bigArray = malloc(3^20 * 8);

bigArray[1][0][0][1][2][0][1][1][0][0][0][0][1][1][2][1][1][1][1][1] = some_256_bit_value;

etc.

Edit: Will not work because you would need 3^20 * 8Byte = ca. 25GByte. The malloc variant is wrong.

Answer 6

2^30 bits is 2^27 bytes so not actually a gigabyte, it's an eighth of a gigabyte.

It appears impossible to do because of the mathematics although of course you can create the data size bigger then compress it, which may get you down to the required size although it cannot guarantee. (It must fail to some of the time as the compression is lossless).

If you do not require immediate "random" access your solution may be a "variable sized" two-bit word so your most commonly stored value takes only 1 bit and the other two take 2 bits.

If 0 is your most common value then: 0 = 0 10 = 1 11 = 2

or something like that.

In that case you will be able to store your bits in sequence this way.

It could take up to 2^40 bits this way but probably will not. You could pre-run through your data and see which is the commonly occurring value and use that to indicate your single-bit word. You can also compress your data after you have serialized it in up to 2^40 bits.

My assumption here is that you will be using disk possibly with memory mapping as you are unlikely to have that much memory available.

My assumption is that space is everything and not time.

Answer 7

Seems tricky to me without some compression:

3^20 = 3486784401 values to store
256bits / 8bitsPerByte = 32 bytes per value
3486784401 * 32 = 111577100832 size for values in bytes
111577100832 / (1024^3) = 104 Gb

You're trying to fit 104 Gb in 1 Gb. There'd need to be some pattern to the data that could be used to compress it.

Sorry, I know this isn't much help, but maybe you can rethink your strategy.