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는 다음과 유사합니다.
#includeint 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들에 대한 코드는 다음과 유사합니다.
#includeint 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를 통하기 때문일까요?
insert at end/push_back test on C++ Standard Library containers and ncl::Array 더 읽기"
