Optimization (in C language): Many function calls vs One function call

Question

For example, I want to create a function (insertNode) that adds nodes to a list. Is it faster to call insertNode every time I want to add a node, or to store all the nodes in an array, and call the insertNode just one time, by passing the array as the argument and let the function do the rest?

Code example:

typedef struct Data {
    int *myArray;             //the array where all integers are stored
    int firstAvailablePos;    //the first free position of myArray
} Data;

insertNode(Data *data, int newNum) {
    (data->myArray)[data->firstAvailablePos] = newNum;
    (data->firstAvailablePos)++;
}

alt_insertNode(Data *data, int *array, int arraySize) {
    int i;
    for(i = 0; i < arraySize; i++)
         (data->myarray)[i] = array[i];
}

And in main the two options are:

1. Many function calls

   while (...) {
       ...
       insertNode(data, newNum);
   }
   

2. One function call

   anArraySize = 0;
   while (...) {
       ...
       anArray[i] = newNum;
       anArraySize++;
       ...
   }
   alt_insertNode(data, anArray, anArraySize);
   

Answer 1

Your code has problems:

• You use an obsolete syntax for function definitions. The implicit return type is no longer supported in modern C code, you should specify it as void.

• You use extraneous parentheses that make the code look awkward.

• function insertNode does not check if the array pointed to by myArray is large enough. You should check and reallocate the array if needed.

• function alt_insertNode does not check for available room, and does not update firstAvailablePos either.

Depending on your reallocation scheme and depending on how aggressive your compiler is allowed to optimize, it might be more efficient to insert values in batches than to insert them one by one, especially if you don't allocate the intermediary array with malloc(). Benchmarking your specific test cases will tell you which is more efficient. Note however that there is substantial value in making the code as simple as possible.

Here is a more complete implementation you can use to run tests:

typedef struct Data {
    int *myArray;             // the array where all integers are stored
    size_t size;              // the number of int that can be stored
    size_t firstAvailablePos; // the first free position of myArray
} Data;

/* reallocating the array with a simple exponential growth */
int insertNode(Data *data, int newNum) {
    if (data->firstAvailablePos == data->size) {
        size_t newSize = (data->size < 32) ? 32 : data->size + data->size / 2;
        int *array = realloc(myArray, newSize * sizeof(*array));
        if (array == NULL)
            return -1;
        data->myArray = array;
        data->size = newSize;
    }
    data->myArray[data->firstAvailablePos++] = newNum;
    return 0;
}

int alt_insertNode(Data *data, int *array, size_t arraySize) {
    if (data->firstAvailablePos + arraySize > data->size) {
        size_t newSize = (data->size < 32) ? 32 : data->size + data->size / 2;
        while (newSize < data->firstAvailablePos + arraySize) {
            newSize += newSize / 2;
        }
        int *array = realloc(myArray, newSize * sizeof(*array));
        if (array == NULL)
            return -1;
        data->myArray = array;
        data->size = newSize;
    }
    memcpy(data->myArray + data->firstAvailablePos, array, arraySize * sizeof(*array));
    data->firstAvailablePos += arraySize;
    return 0;
}