최적화 (C 언어) : 많은 함수 호출과 하나의 함수 호출

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. 하나의 함수 호출

   를 호출

Answer 1

코드는 문제가있다 :

• 당신은 함수 정의를 위해 사용되지 않는 구문을 사용합니다. 암시 적 반환 유형은 최신 C 코드에서 더 이상 지원되지 않으므로 void으로 지정해야합니다.

• 코드를 어색하게 만드는 불필요한 괄호를 사용합니다.

• function insertNodemyArray이 가리키는 배열이 충분히 큰지 확인하지 않습니다. 필요한 경우 배열을 확인하고 다시 할당해야합니다.

• 기능 alt_insertNodealt_insertNode 기능 alt_insertNode은 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의 호출 시간은 짧지 만 인터 럽션 수가 증가합니다. 함수 호출만큼 시간이 많이 걸리지 않습니다.

배열에 대한 추가 메모리가 필요하다는 점을주의해야합니다.