[C] realloc 함수

realloc 함수는 malloc 이나 calloc 으로 생성한 메모리블럭의 크기를 늘려주는 함수이다.

C의 엄청난 장점 중에 하나다.

예를들어 vector 를 구현할때 realloc 을 사용하면 새로 할당한 배열에

기존 배열을 복사하는 비용을 절감할수 있다.

라고....이론적인 내용이다 지금까지

간단하게 벡터의 추가 연산에 대해

realloccalloc+memcpy의 성능을 측정해보자

typedef struct VEC{  
 int* base;
 int sz, cp;
}VEC;
void PB(VEC* _this, int value) {  
 if (_this->sz == _this->cp){
  int* temp = _this->base;
  _this->base = (int*)realloc(_this->base, (_this->cp = _this->cp ? _this->cp << 1 : 1)*sizeof(int));
  if (!_this->base){
   _this->base = (int*)calloc(_this->cp, sizeof(int));
   memcpy(_this->base, temp, _this->sz*sizeof(int));
   free(temp);
  }
 }
 _this->base[_this->sz++] = value;
}
void CPB(VEC* _this, int value) {  
 if (_this->sz == _this->cp) {
  int* temp = (int*)calloc(_this->cp = _this->cp ? _this->cp << 1 : 1,sizeof(int));
  memcpy(temp, _this->base, _this->sz*sizeof(int));
  free(_this->base);
  _this->base = temp;
 }
 _this->base[_this->sz++] = value;
}

성능은 10만개부터 10억개까지 PushBack 연산에 대해 시간을 측정 하였다.

데이터가 작을때는 벡터의 추가연산이야 뭐 O(1)로 써 시간차가 거의 나지 않는다.

1억개 이상이 되면 성능차이가 나기 시작하는데, 테스트마다 realloc은 유동적인 시간결과

를 보여주고있다.

좀 심하게 유동적인데, 그래도 1억개의 데이터에선 realloc이 -30% ~ 50%의 성능향상을 보여준다. (재수 없을때는 30%나 느리단 소리임 realloc이)

데이터가 10억개쯤 되면 realloc이 calloc+memcpy와 비슷하거나 더 느린결과가 많이 나왔다.

Debug 에서는 이 차이가 작지만 Release 모드에서는 성능차이가 많이 벌어진다.

(나라면 개선되지않은 quick sort 보단 merge sort를 사용하겠다)

결론을 말하자면 calloc+memcpy 대신 realloc으로 벡터를 구현하는데 성능향상은 없다고 봐도 무방하다.

다만...calloc은 malloc+memset 이다.

calloc 부분을 malloc으로 바꾸면 작지만, realloc보다 90%정도의 확률로 우세한 결과가 나온다.

또한 realloc은 메모리를 늘리는데, 불가능하다면 NULL을 반환한다.

따라서 원래의 메모리블록에 대한 주소를 임시 변수에 가지고 있어야한다.

그렇지 않으면 메모리 누수를 피할수 없다.

만일 힙 메모리에 링크드리스트같은놈이 떡 하니 자리잡고 있으면

realloc의 할당성공률은 0% 에 수렴한다.

따라서 여러가지면을 고려할때 realloc으로 얻는 장점은 없다!