How to improve performance of a dynamic array implemented with void**?

Question

I need to implemenet a simple dynamic array that can work with any type.

Right now my void** implementation is ~50% slower than using int* directly:

#define N 1000000000

// Takes ~6 seconds
void** a = malloc(sizeof(void*) * N);
for (int i =0; i < N; i++) {
        *(int*)(&a[i]) = i;

}
printf("%d\n", *(int*)&a[N-1]);

// Takes ~3 seconds
int* b = malloc(sizeof(int) * N) ;
for (int i =0; i < N; i++) {
        b[i] = i;
}
printf("%d\n", b[N-1]);

I'm not a C expert. Is there a better way to do this?

Thanks

edit

Look like using void** is a bad idea. Is there a way to implement this with void*?

Here's how it's implemented in Go:

type slice struct {
        array unsafe.Pointer
        len   int
        cap   int
}

I'd like to do something similar.

edit2

I managed to implement this with void*.

The solution was really simple:

 void* a = malloc(sizeof(int) * N);
 for (int i = 0; i < N; i++) {
    ((int*)a)[i] = i;
 }
 printf("%d\n", ((int*)a)[N-1]);

Performance is the same now.

Answer 1

Your two alternatives programs are not analogous. In the second one, which is valid, you allocate space sufficient to hold N integers, and then assign values to the int-size members of that space. In the first one, however, you allocate space large enough to accommodate N pointers to void and then, without initializing those pointers, you try to assign values to the objects to which they point. Even if those pointers had been initialized to point to int objects, there is an extra level of indirection.

Your first code could be corrected, in a sense, like so:

void** a = malloc(sizeof(void*) * N);
for (int i =0; i < N; i++) {
        a[i] = (void *) i;

}
printf("%d\n", (int) a[N-1]);

That relies on the fact that C allows conversions between pointer and integer types (although not necessarily without data loss), and note that there is only a single level of indirection (array indexing), not two.

Inasmuch as the behavior of your implementation of the first alternative is undefined, we can only speculate about why it runs slower in practice. If we assume a straightforward implementation, however, then such a performance penalty as you observe might arise from poor cache locality for all the array writes.

Answer 2

Be aware that sizeof(void *) is the double of sizeof(int) on 64 bits processors (8 bytes address versus 4 bytes signed integer). If that's your case, I bet the difference only is page cache miss. You memory unit is required to load two times more pages, which is slow (link for more information here).

Please also note that C++ vectors aren't "dynamic array that can work with any type". They are bound to a type, for instance: std::vector<int> is a dynamic array but where you can only store int.

A solution to your problem would be to implement some sort of std::vector<void *> in C. But it's not efficient:.

• You need to do 2 allocations for each element (1 for the container and 1 for the element itself)
• You need to do 2 levels of indirection each time you access the data (1 to get the pointer in the container and 1 to get the data in the element)
• You need to store some kind of type information in each element. If not, you don't know what is in your dynamic array

Answer 3

I managed to implement this with void*.

The solution was really simple:

 void* a = malloc(sizeof(int) * N);
 for (int i =0;i<N;i++) {
  ((int*)a)[i] = i;
 }
 printf("%d\n", ((int*)a)[N-1]);

Performance is the same now.

I also came across this great article that explains how to implement a generic data structure in C:

http://jiten-thakkar.com/posts/writing-generic-stack-in-c