Allocating Memory for Sparsely Populated Arrays/Matrices

I'm using a program to allocate a good chunk of memory, upwards of a gig (1 GB) of ram for a 3 dimensional array. I'm looking for a way to make my allocation more efficient, if possible, because some of the indexes will contain 0 or null. I'd like to be able to discard the 0/null values and not allocate the space for them.

I've done some research and the only option I can find is linked lists. From what I gather, unless 50% or more of the indexes are 0, the linked list will allocate more space than originally allocated.

Any ideas would be greatly appreciated! Thanks!

this seems to go over the possible implementations pretty well Sparse matrix - Wikipedia, the free encyclopedia

You're looking for a sparse array. You don't need a linked list (though that is one option). If you normally have a 3-d array of Foo objects, like so:

Code:

---

Foo foo_array[100][200][300]

---

You have 6 million Foo objects. If most of them are 0/null, you can simply store the indices of each non-null element, along with the element itself, in an array. For example:

Code:

---

struct sparse_element {
    int x; // first dimension
    int y; // second dimension
    int z; // third dimension
    Foo f;  // the foo object that would be at foo_array[x][y][z]
};

---

Then, you have an array of sparse_elements:

Code:

---

struct sparse_element sparse_array[500];

---

That's much smaller, but the savings in space are often offset by extra computation time to find/access members*. Just pick an appropriate number of elements**. Also, you will probably want to malloc this array in your code.

* There are other ways to speed up access to these sparse elements, perhaps keeping the array sorted for a binary search, or by using a balanced binary tree to store them instead of a fixed array, so looking for the Foo object that would be at (x,y,z) = (75,42,19). Not as quick as simply indexing an array, but better than a linear search.

** As for the appropriate number of elements, that depends on your application, since there is a little extra overhead. You may find that this method is only effective if your original array was less than 10% full, or maybe 25%, 50% or even 75%.

One thing I did forget to mention is that 2 of the dimensions are known before the program runs (The file has a GUI to run the script) but a third dimension is dynamically allocated, that is it allocates as it runs and see how many slots it needs to assign. A graphical interpretation below shows what I'm trying to accomplish:

Code:

---

      ________________
    /              /|
  n /              / |
  /_______________/  |
  |              |  |
  |              |  |
y  |              |  |
  |              |  /
  |              | /
  |_______________|/
          x

---

(Plain Text Seems to Work Better)

I'm using a structure to assign a height (y), width (x), and a depth (n). x and y are known before the program is run, but the depth n is not known. Currently I have a script to reduce n down to the point where there are no null characters in the block. Meaning, if n ends up being 148 after the program is run, but the last 100 blocks are null or there are 100 blocks in the middle null, n is reduced to 48 and everything is moved up. But, there are still some null indexes within the x, y part all the way back to n being 48.

I hope I made some sense there...

There are a number of different ways to represent sparse matrices and arrays. The best method depends on the patterns the stored elements have, whether it is for storing (randomly populated, then saved to say a file), read-only access, or both; and if modified, whether existing stored elements are modified or if typically new ones are added. It is all about the patterns.

What is the expected distribution of the stored elements? Do you expect to have many consecutive samples along the n dimension? Are the elements completely random, or do they exhibit clustering patterns? It does not need to be any hard rule, but knowing the patterns would help in picking the best approach.

If a 3D array tends to have large 3D voids, a recursive approach may work best. You may for example use a 8x8x8 cube as the unit. You start with one unit, each element pointing to a sub-unit, unless the sub-unit is empty. Access is very fast, but the smaller the unit cube, the larger the storage overhead. The larger the unit cube, more memory is wasted by having many partially filled units. You basically use two types of unit cubes: ones where the cells point to other cubes, and ones where the cells have values. There is no need to store the coordinates, as long as you know how many cells the original unit cube holds, since you can always count how many cells each cube cell covers. (You can even use that to pick the cube type: if the cube cells cover more than one array cell, the cells are references to cubes. If they cover exactly one cell, then they are cells.) Also, the actual dimensions of the array covered basically have to be a power of the cube dimensions. For a 2x2x2 cube, each dimension is a power of two. For a 8x8x8 cube, each dimension is a power of eight. You can obviously just use the desired part closest to origin only; it only matters when you consider the overheads.

If a 3D array tends to have sequential runs along a specific direction, then a linked list of consecutive runs along that dimension is likely to work well. If that also happens to be the dimension the data is usually traversed along, then it may be faster than a raw array!

If the 3D array is likely to be very sparse -- large but predominantly empty --, you might use a hash table approach, computing a hash of each set of coordinates, and store the cell coordinates and values under that hash. (Each hash table entry would contain an array of cell coordinates and values, plus the number of cells under that hash.)

Compressed sparse row/column approach is very often used for 2D arrays (since they mesh in well with the mathematical algorithms), but the extension to 3D is not that simple. Usually you pick one 2D plane (say x-y), and store offset and number of elements along that plane into the data, which contains both third axis coordinates and cell values. In your case the array will be very large, so inserting new elements (except at fill order; at the end) tends to be slow because normally all existing data must be moved. To avoid that, one can use an array-based linked list approach, but that uses an additional pointer-sized index per used element, and anyway tends to kill cache locality. (It works fine if you access the array randomly, but sequential access is going to be just as slow as random access. In many other approaches certain types of sequential accesses are very fast.)

With the current project I am working on now, I've run a few tests to see how sparse the matrix is. The x, y, and n all happen to correspond to coordinates of pixels on the project. Thus, (0, 0, 0) would correspond to the first storage location, and also the pixel on the bottom left, first depth. The numbers I've come up with depend on what I choose to run the program with, but the percent of null pixels or storage locations is around 96%. Basically, there is a ton of space being allocated for only a relative few pixels that are usable. The x and y are both set at 256 pixels and the n ranges from 50 to 700 (can be more if I up the settings) so the actual size can be upwards of 40 million pixels or storage locations. So I've got about 1 million good pixels and 39 million useless pixels. A hash table may be the best approach.

Thanks for the advice, Nominal Animal.