insert at end/push_back test on C++ Standard Library containers and ncl::Array

gcc(+stlport) 환경에서 C++ Standard Library container들과 ncl::Array에 대한 성능 측정을 해보았습니다. 다만, int형에 대한 insert at end/push_back operation에 대해서만 측정을 해보았습니다. 참고로, ncl::Array는 C Standard Library의 realloc을 활용하여 copy를 줄이는 container입니다. 즉, C++ Standard Library의 container들과는 semantic이 좀 다른 셈이지요.

1. insert at end

첫번째는 (Sheet 1) container.insert(container.end(), obj) operation을 사용한 테스트입니다. stlport가 들어가있는 결과물은 gcc의 기본 library 구현 대신 stlport를 사용한 결과이고, reserve란 단어가 들어가 있는 결과물은 vector::reserve나 Array::Array(int size)를 사용한 구현의 결과입니다. (deque, list는 reserve를 위한 mechanism이 없습니다.)

결과를 요약해보면, vector (reserving) < vector < deque(stlport) =~ deque < list < list (stlport) 입니다. code는 다음과 유사합니다.

#include 
int main(int argc, char * argv[])
{
if (argc != 3)
{
printf("usage: %s count sizen", argv[0]);
return 0;
}
int count = atoi(argv[1]);
int size = atoi(argv[2]);
for (int i = 0; i != count; ++i)
{
std::vector v;
#ifdef VECTOR_RESERVE
v.reserve(size);
#endif
for (int j = 0; j != size; ++j)
v.insert(v.end(), j);
}
}

2. push_back test

두번째는 (Sheet 2) container.push_back(obj) operation을 사용한 테스트입니다. vector의 경우에 위의 insert(container.end(), …)와 성능 차이가 2배정도 나는 것이 신기하군요.

결과를 요약해보면, Array (reserving) < vector (reserving) < deque < Array =~ vector << list 입니다. container들에 대한 코드는 다음과 유사합니다.

#include 
int main(int argc, char * argv[])
{
if (argc != 3)
{
printf("usage: %s count sizen", argv[0]);
return 0;
}
int count = atoi(argv[1]);
int size = atoi(argv[2]);
for (int i = 0; i != count; ++i)
{
#ifndef VECTOR_RESERVE
std::vector v;
#else
std::vector v;
v.reserve(size);
#endif
for (int j = 0; j != size; ++j)
v.push_back(j);
}
}

ARRAY의 테스트 코드는 다음과 같습니다.

#include 
#include "ncl/array.h"
int main(int argc, char * argv[])
{
if (argc != 3)
{
printf("usage: %s count sizen", argv[0]);
return 0;
}
int count = atoi(argv[1]);
int size = atoi(argv[2]);
for (int i = 0; i != count; ++i)
{
#ifndef ARRAY_RESERVE
ncl::Array v;
for (int j = 0; j != size; ++j)
//v.insert(v.size(), j);
v.add(j);
#else
ncl::Array v(size);
for (int j = 0; j != size; ++j)
v.item(j) = j;
#endif
}
}

3. Conclusion

신기하게도, insert at end의 경우에는 vector가 제일 빠르고, deque, list의 순입니다. push_back의 경우에는 deque, vector, list의 순이었습니다.

두 경우 모두 list는 매우 느렸습니다. link를 위한 pointer의 overhead와 entry 별 allocation이 큰 것 같습니다. (아마도 allocator 수준에서 pooling을 하게 되면 개선할 수 있을까요?)

reserve를 하지 않는 경우 vector와 Array는 거의 유사한 performance를 보여줍니다. 10만건이 되면 좀 차이가 납니다. item 수가 적은 경우 (10000건 이하인 경우) vector의 alloc/copy와 Array의 realloc이 별로 차이나지 않는 것을 알 수 있습니다. (copy cost외에도 pre-allocation의 전략이 다르기 때문일 수도 있을 것 같습니다.) int형이 아니라 좀 더 큰 size의 (따라서 copy cost가 더 큰) object를 사용할 경우에는, vector와 Array의 차이가 더 커질 수도 있을 것 같습니다. (테스트가 필요합니다)

그리고 deque가 vector와 Array보다 더 빠른 것을 알 수 있습니다. gcc의 구현을 조금 보니, deque는 memory chunk 단위로 alloc하고 이에 대한 index(map)를 유지하는 data structure더군요. push_back의 경우에 추가적인 메모리만 할당하고, index의 size만 조절해주면 되기 때문에 당연히 더 좋을 수 밖에 없는 것 같습니다.

또한, reserve하는 것이 단연 reserve 하지 않는 경우보다 빠른 것을 알 수 있습니다. reserve할 경우에는 ncl::Array가 std::vector보다 훨씬 빠릅니다. Array의 경우에는 생성자를 통하지만, vector의 경우에는 reserve() op를 통하기 때문일까요?