push_back of STL list got bad performance?

Posted by Leon Zhang on Stack Overflow See other posts from Stack Overflow or by Leon Zhang
Published on 2010-04-06T23:13:37Z Indexed on 2010/04/06 23:23 UTC
Read the original article Hit count: 320

Filed under:
|

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;
}

© Stack Overflow or respective owner

Related posts about c++

Related posts about stl