push_back of STL list got bad performance?
- by Leon Zhang
I wrote a simple program to test STL list performance against a simple C list-like data structure. It shows bad performance at "push_back()" line. Any comments on it?
$ ./test2
Build the type list : time consumed -> 0.311465
Iterate over all items: time consumed -> 0.00898
Build the simple C List: time consumed -> 0.020275
Iterate over all items: time consumed -> 0.008755
The source code is:
#include <stdexcept>
#include "high_resolution_timer.hpp"
#include <list>
#include <algorithm>
#include <iostream>
#define TESTNUM 1000000
/* The test struct */
struct MyType {
int num;
};
/*
* C++ STL::list Test
*/
typedef struct MyType* mytype_t;
void myfunction(mytype_t t) {
}
int test_stl_list()
{
std::list<mytype_t> mylist;
util::high_resolution_timer t;
/*
* Build the type list
*/
t.restart();
for(int i = 0; i < TESTNUM; i++) {
mytype_t aItem = (mytype_t) malloc(sizeof(struct MyType));
if(aItem == NULL) {
printf("Error: while malloc\n");
return -1;
}
aItem->num = i;
mylist.push_back(aItem);
}
std::cout << " Build the type list : time consumed -> " << t.elapsed() << std::endl;
/*
* Iterate over all item
*/
t.restart();
std::for_each(mylist.begin(), mylist.end(), myfunction);
std::cout << " Iterate over all items: time consumed -> " << t.elapsed() << std::endl;
return 0;
}
/*
* a simple C list
*/
struct MyCList;
struct MyCList{
struct MyType m;
struct MyCList* p_next;
};
int test_simple_c_list()
{
struct MyCList* p_list_head = NULL;
util::high_resolution_timer t;
/*
* Build it
*/
t.restart();
struct MyCList* p_new_item = NULL;
for(int i = 0; i < TESTNUM; i++) {
p_new_item = (struct MyCList*) malloc(sizeof(struct MyCList));
if(p_new_item == NULL) {
printf("ERROR : while malloc\n");
return -1;
}
p_new_item->m.num = i;
p_new_item->p_next = p_list_head;
p_list_head = p_new_item;
}
std::cout << " Build the simple C List: time consumed -> " << t.elapsed() << std::endl;
/*
* Iterate all items
*/
t.restart();
p_new_item = p_list_head;
while(p_new_item->p_next != NULL) {
p_new_item = p_new_item->p_next;
}
std::cout << " Iterate over all items: time consumed -> " << t.elapsed() << std::endl;
return 0;
}
int main(int argc, char** argv)
{
if(test_stl_list() != 0) {
printf("ERROR: error at testcase1\n");
return -1;
}
if(test_simple_c_list() != 0) {
printf("ERROR: error at testcase2\n");
return -1;
}
return 0;
}
