优化（C 语言）：多次函数调用 vs 一次函数调用

Question

例如，我想创建一个将节点添加到列表的函数 (insertNode)。每次我想添加一个节点时调用 insertNode 还是将所有节点存储在一个数组中，然后调用 insertNode 一次，通过将数组作为参数传递并让函数完成剩下的工作？

代码示例：

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];
}

而在main中的两个选项是：

许多函数调用

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

一个函数调用

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

Answer 1

这取决于您程序中的许多因素。具体来说，节点是按某种算法排序还是顺序不重要？如果是这样，传递数组节点或单独插入不会有太大区别（排序块或信息和将节点插入排序位置应该是等效的。）

您可能还会考虑在程序中的什么位置需要将节点插入您的列表中。如果您的列表使用动态内存，则有必要在需要时沿线的某个时间插入一个节点。

Answer 2

这取决于底层列表实现的结构。如果这是一个数组并且 insertNode 追加它，它会被复制到内存中的一个新位置，那里有更多 space 可用，以便新元素也适合。新元素也会得到 memcpyd。这很快，因为它发生在内核中而不是在您的用户 space 程序中。

另一方面，如果你有类似链表的东西，其中存储了指向数组形式的其他列表的指针。你甚至不必复制列表中的所有元素，而只需插入一个指向链表的新指针，该指针指向包含新元素的数组。那将是非常快的。

据我所知，最佳答案是：视情况而定。

Answer 3

这取决于调用代码的样子，但一般来说，如果可以内联，一个简短的函数调用将具有零开销。创建一个临时数组只是为了避免函数调用开销几乎肯定是一个错误 - 但在某些情况下 "batching" 这样的东西可以避免大量的每次插入开销并且可能有意义。

同时尝试和基准测试。

Answer 4

函数调用比迭代要花费一些时间。如果您通过调用 insertNode 函数插入一个节点，则需要进行一些迭代（取决于您要插入的位置）将该节点插入列表中，但是如果您要插入大量节点，则需要每次都调用该函数。这可能很费时间。

如果通过将某个节点放入数组中来插入节点，最后调用insertNode将数组的节点复制到列表中。这次 insertNode 的调用时间会减少，但交互次数会增加。这不会花费时间，就像函数调用一样。

这里有一点需要注意，您需要为数组提供额外的内存。

Answer 5

您的代码有问题：

您对函数定义使用了过时的语法。现代 C 代码不再支持隐式 return 类型，您应该将其指定为 void.
您使用了无关的括号，使代码看起来很别扭。
函数insertNode不检查myArray指向的数组是否足够大。如果需要，您应该检查并重新分配数组。
函数 alt_insertNode 不检查可用空间，也不更新 firstAvailablePos。

根据您的重新分配方案以及您的编译器允许优化的积极程度，批量插入值可能比一个一个地插入它们更有效，特别是如果您不分配中间数组malloc()。对您的特定测试用例进行基准测试将告诉您哪个更有效。但是请注意，使代码尽可能简单具有重要价值。

这是一个更完整的实现，可用于运行测试：

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;
}

优化（C 语言）：多次函数调用 vs 一次函数调用

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

c

optimization

function-calls