fill_array_out_of_order.c does not fill array, and it can also write past the end of the array

[kosak]

There are a few bugs in fill_array_out_of_order.c

1. When NUMBER is a power of 2, it can write past the end of the array.
2. When NUMBER is (many values), the code does not actually "fill the array"
3. The comment in the code says it is filling the array with 5s but it actually fills each byte with (the low byte of) j.

I have modified your program to add printf statements and to store '5'. This is the code:

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

// Number to guess: How big of an array (in bytes)
// can we allocate and fill with 5s in a second?
// The catch: We do it out of order instead of in order.
int main(int argc, char **argv) {
    int NUMBER, i;
    NUMBER = atoi(argv[1]);

    char* array = malloc(NUMBER);
    int j = 1;
    for (i = 0; i < NUMBER; ++i) {
        j = j * 2;
        if (j > NUMBER) {
            j = j - NUMBER;
        }
        if (j == NUMBER) {
           printf("Array index out of range!\n");
           exit(1);
        }
        array[j] = 5;
    }
    for (i = 0; i < NUMBER; ++i) {
      printf("%d: %d\n", i, array[i]);
    }
    return 0;
}

And here are some (buggy) results:

# shows that the code can write off the end of the array
$ ./a.exe 16
Array index out of range!

# shows that the array is not actually being filled
$ ./a.exe 10   
0: 0
1: 0
2: 5
3: 0
4: 5
5: 0
6: 5
7: 0
8: 5
9: 0

[kamalmarhubi]

Thanks for this report! That isn't great, and it looks like we were unlucky enough to not end up with that being a segmentation fault. valgrind does indeed catch it though:

$ valgrind --leak-check=no ./a.out 16 
==11000== Memcheck, a memory error detector
==11000== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==11000== Using Valgrind-3.10.0 and LibVEX; rerun with -h for copyright info
==11000== Command: ./a.out 16
==11000== 
==11000== Invalid write of size 1
==11000==    at 0x4005FD: main (in /home/kamal/projects/one-second/benchmarks/a.out)
==11000==  Address 0x51de050 is 0 bytes after a block of size 16 alloc'd
==11000==    at 0x4C28C20: malloc (vg_replace_malloc.c:296)
==11000==    by 0x4005C7: main (in /home/kamal/projects/one-second/benchmarks/a.out)
==11000== 
2==11000== 
==11000== HEAP SUMMARY:
==11000==     in use at exit: 16 bytes in 1 blocks
==11000==   total heap usage: 1 allocs, 0 frees, 16 bytes allocated
==11000== 
==11000== For a detailed leak analysis, rerun with: --leak-check=full
==11000== 
==11000== For counts of detected and suppressed errors, rerun with: -v
==11000== ERROR SUMMARY: 13 errors from 1 contexts (suppressed: 0 from 0)

/cc @jvns

[kosak]

Yeah. Not filling every entry is not great either, since it's not really a fair comparison if you're not touching every byte.