Оптимизация (на языке 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 два варианта:

1. Многие вызовы функций

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

2. Один вызов функции

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

Answer 1

Ваш код имеет проблемы:

• Вы используете устаревший синтаксис для определения функций. Неявный тип возврата больше не поддерживается в современном коде C, вы должны указать его как 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; 
} 

Answer 2

Это будет зависеть от множества вещей в вашей программе. В частности, являются ли узлы отсортированными по некоторому алгоритму или порядок неважен? Если это так, то передача узлов массива или вставка отдельно не будет иметь большого значения (поскольку сортировка фрагментов или информации и вставка узла в отсортированную позицию должны быть эквивалентными.)

Вы также можете рассмотреть, в какой момент программы узлы должны быть вставлены в ваш список. Если в вашем списке используется динамическая память, необходимо будет иметь функцию для вставки узла, когда нужно когда-нибудь вдоль линии.

Answer 3

Это зависит от структуры реализации списка подкладок. Если это массив и insertNode добавляет его, он копируется в новое место в памяти, где есть больше свободного места, так что новые элементы также вписываются. Новые элементы также получают memcpyd. Это быстро, потому что это происходит в ядре, а не в вашей программе пользовательского пространства.

С другой стороны, если у вас есть что-то вроде связанного списка, в котором хранятся указатели на другие списки в виде массивов. Тогда вам даже не придется копировать все элементы из списка, а просто вставить один новый указатель на связанный список, который указывает на массив с новыми элементами в нем. Это было бы очень быстро.

Лучший ответ от того, что я знаю сейчас: это зависит.

Answer 4

Это зависит от того, как выглядит код вызова, но в целом короткий вызов функции будет иметь нулевые служебные данные, если он может быть встроен. Создание временного массива просто избегает накладных расходов на функциональные вызовы - это почти наверняка ошибка, но в некоторых случаях такие «дозирующие» вещи, как это, могут избежать накладных расходов на каждую вставку и могут иметь смысл.

Попробуйте оба теста.

Answer 5

Функция вызова в несколько раз дороже, чем итерация. Если вы вставляете узел, вызывая функцию insertNode, ему требуется некоторая итерация (в зависимости от того, где вы хотите вставить), чтобы вставить этот узел в список, но если вы хотите вставить большой объем узла, ему нужно каждый раз вызывать функцию. которая может быть дорогостоящей.

Если вы вставляете узел, помещая некоторый узел в массив и при последнем вызове insertNode, чтобы скопировать узел массива в список. На этот раз insertNode будет меньше времени на вызов, но количество interation будет увеличиваться. который не будет дорогостоящим, так как вызов функции будет.

Здесь нужно отметить, что для массива требуется дополнительная память.