Trick to avoid needing to initialize an array

Question

Normally if I want to allocate a zero initialized array I would do something like this:

int size = 1000;
int* i = (int*)calloc(sizeof int, size));

And later my code can do this to check if an element in the array has been initialized:

if(!i[10]) {
  // i[10] has not been initialized
}

However in this case I don't want to pay the upfront cost of zero initializing the array because the array may be quite large (i.e. gigs). But in this case I can afford to use as much memory as I want memory.

I think I remember that there is a technique to keep track of the elements in the array that have been initialed, without paying any up front cost, that also allows O(1) cost (not amortized with a hash table). My recollection is that the technique requires an extra array of the same size.

I think it was something like this:

int size = 1000;
int* i = (int*)malloc(size*sizeof int));
int* i_markers = (int*)malloc(size*sizeof int));

If an entry in the array is used it is recorded like this:

i_markers[10] = &i[10];

And then it's use can be checked later like this:

if(i_markers[10] != &i[10]) {
  // i[10] has not been initialized
}

Of course this isn't quite right because i_markers[10] could have been randomly set to &i[10].

Can anyone out there remind me of the technique?

Thank you!

---

I think I remembered it. Is this right? Is there a better way or are there variations on this? Thanks again. (This was updated to be the right answer)

struct lazy_array {
    int size;
    int* values;
    int* used;
    int* back_references;
    int num_used;
};

struct lazy_array* create_lazy_array(int size) {
    struct lazy_array* lazy = (struct lazy_array*)malloc(sizeof(lazy_array));
    lazy->size = 1000;
    lazy->values = (int*)malloc(size*sizeof int));
    lazy->used = (int*)malloc(size*sizeof int));
    lazy->back_references = (int*)malloc(size*sizeof int));
    lazy->num_used = 0;
    return lazy;
}

void use_index(struct lazy_array* lazy, int index, int value) {
    lazy->values[index] = value;
    if(is_index_used(lazy, index))
      return;
    lazy->used[index] = lazy->used;
    lazy->back_references[lazy->used[index]] = index;
    ++lazy->used;
}

int is_index_used(struct lazy_array* lazy, int index) {
    return lazy->used[index] < lazy->num_used &&
        lazy->back_references[lazy->used[index]] == index);
}

Answer 1

On most compilers/standard libraries I know of, large calloc requests (and malloc for that matter) are implemented in terms of the OS's bulk memory request logic. On Linux, that means a copy-on-write mmap-ing of the zero page, and on Windows it means VirtualAlloc. In both cases, the OS gives you memory that is already zero, and calloc recognizes this; it only explicitly zeroes the memory if it was doing a small calloc from the small allocation heap. So until you write to any given page in the allocation, it's zero "for free". No need to be explicitly lazy; the allocator is being lazy for you.

For small allocations it does need to memset to clear the memory, but then, it's fairly cheap to memset a few thousand bytes (or tens of thousands) of bytes. For the really large allocations where zeroing would be costly, you're getting OS provided memory that's zero-ed for free (separate from the rest of the heap); e.g. for dlmalloc in typical configuration, allocations beyond 256 KB will always be freshly mmap-ed and munmap-ed, which means you're getting freshly mapped copy-on-write mappings of the zero page (the cost to zero them being deferred until you perform a write somewhere in the page, and paid whether you got the 256 KB via malloc or calloc).

If you want better guarantees about zeroing, or to get free zeroing on smaller allocations (though it's more wasteful the closer to one page you get), you can just explicitly do what malloc/calloc do implicitly and use the OS provided zero-ed memory, e.g. replace:

sometype *x = calloc(num, sizeof(*x)); // Or the similar malloc(num * sizeof(*x));
if (!x) { ... do error handling stuff ... }
...
free(x);

with either:

sometype *x = mmap(NULL, num * sizeof(*x), PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
if (x == MAP_FAILED) {  ... do error handling stuff ... }
...
munmap(x, num * sizeof(*x));

or on Windows:

sometype *x = VirtualAlloc(NULL, num * sizeof(*x),  MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
if (!x) { ... do error handling stuff ... }
...
VirtualFree(x, 0, MEM_RELEASE); // VirtualFree with MEM_RELEASE only takes size of 0

It gets you the same lazy initialization (though on Windows, this may mean that the pages have simply been lazily zero-ed in the background between requests, so they'd be "real" zeroes when you got them, vs. *NIX where they'd be CoW-ed from the zero page, so the get zero-ed live when you write to them).

Answer 2

This can be done, although it relies on undefined behavior. It is called a lazy array.

The trick is to use a reverse lookup table. Every time you store a value, you store its index in the lazy array:

void store(int value)
{
   if (is_stored(value)) return;
   lazy_array[value] = next_index;
   table[next_index] = value;
   ++next_index;
}

int is_stored(int value)
{
  if (lazy_array[value]<0) return 0;
  if (lazy_array[value]>=next_index) return 0;
  if (table[lazy_array[value]]!=value) return 0;
  return 1;
}

The idea is that if the value has not been stored in the lazy array, then the lazy_array[value] will be garbage. Its value will either be an invalid index or a valid index into your reverse lookup table. If it is an invalid index, then you immediately know nothing has been stored there. If it is a valid index, then you check your table. If you have a match then the value was stored, otherwise it wasn't.

The downside is that reading from uninitialized memory is undefined behavior. Based on my experience, it will probably work, but there are no guarantees.

Answer 3

There are many possible techniques. Everything depends on your task. For instance, you can remember maximal number of initialized element max of your array. I.e. if your algorithm can garantee, that all elements from 0 to max ara initialized, you can use simple check if (0 <= i && i <= max) or something like this.

But if your algorithms need to initialize arbitrary elements (i.e. random access), you need general solution. For instance, more effective data structure (not simple array, but sparse array or something like this).

So, add more details about your task. I expect we'll find the best solution for it.