How to make a giant matrix in C

Question

I'm trying to define a matrix in C with 100,000 columns and 100,000 lines of boolean type (bool matrix[100000][100000]), how I do that?

Answer 1

Dynamic allocation is needed here. So you need 100000*100000 = 10 billion bits. That's a lot.

10,000,000,000 bits == 1,250,000,000 bytes == 1.164 gigabytes.

So a bit over a gigabyte.. It isn't impossible, but you have to be careful. The best way to do it would be to allocate it in a single array, like this:

uint8_t *matrix = malloc(1250000000);
if (matrix == NULL) // This will very likely fail, so be sure to handle it..
     return ENOMEM;

You now only have a single array. To access an element [i][j], you'd do i*10000+j. However, since we have allocated an array of uint8_t, you need to extract the bits you want.

To do that, you could have accessor macros, like these:

// You probably want to add matrix as a param for these macros
#define index(i, j)   (i*10000+j)
#define elem(i,j)   (matrix[index(i,j)/8])
#define get(i, j)   (elem(i,j) & (1 << index(i,j)%8))
#define set(i,j,v)  (v ? elem(i,j) |= (1 << index(i,j)%8) : elem(i,j) &= ~(1 << index(i,j)%8))

set(5000, 5000, TRUE);
if (get(5000, 5000))
   doStuff();

Answer 2

On a technical note, a definition is quite different to a declaration. I figure you're asking for a type synonym.

typedef bool matrix[100000][100000];

The type matrix is now defined as a type synonym for bool[100000][100000].

matrix *m = malloc(sizeof *m);

m is declared to be a pointer to matrix, and initialised to the return value of a suitable malloc call.

static matrix s;

s is declared to be a matrix with static storage duration, as suggested within the comments.

This is really quite inefficient. If you don't plan on using all of those elements, perhaps you could try using an ordered map of some kind. I've written one you could use, called a PATRICIA trie, which you can find here. If you do plan on using all of those elements, then you could save a lot of memory (and time, in the form of cache misses) by making use of all of the bits within the array, rather than typically 1/8th or worse of them, the waste being in the form of padding. This would require some slightly more complex logic.

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef unsigned char matrix[100000][100000 / CHAR_BIT + (100000 % CHAR_BIT > 0)];

int matrix_get(matrix *m, size_t x, size_t y) {
    return ((*m)[x][y / CHAR_BIT] >> (y % CHAR_BIT)) & 1;
}

void matrix_set(matrix *m, size_t x, size_t y, int value) {
    (*m)[x][y / CHAR_BIT] &= ~(1U    << (y % CHAR_BIT));
    (*m)[x][y / CHAR_BIT] |=   value << (y % CHAR_BIT) ;
}

int main(void) {
    matrix *m = malloc(sizeof *m);
    memset(m, 0, sizeof *m);
    matrix_set(m, 0x1337, 0xC0DE, 1);
    printf("%d\n", matrix_get(m, 0x1337, 0xC0DE));
}

Answer 3

If you are willing to do some bit masking, you can allocate int matrix[100000][1000000/(sizeof(int)*CHAR_BIT)+1] words. Your program will be slower, but you would allocate 1/8th the amount of memory. See How do you set, clear, and toggle a single bit? for bit masking.

If the size of memory is too large for the stack or heap, you might consider memory mapped IO.