Re: [boost] portable precise garbage collector for C++

From: Achilleas Margaritis (axilmar_at_[hidden])
Date: 2007-09-20 07:01:08

Thanks for the tip, I will look into it.

I've done a small benchmark to check how fast an std::list is compared 
to cppgc::_list, and the difference is very large.

std::list duration = 4929.17
_list duration = 3.40211

Perhaps the std::list requires a special allocator class to become as 
efficient as an intrucive list.

The benchmark (which can be wrong - I am not a specialist) is attached 
as a file.

Joaquín Mª López Muñoz wrote:
> 
> Achilleas Margaritis ha escrito:
> 
>> I think std::list is slower than my list (I could be wrong of course),
>> because it allocates memory from the heap for each node, whereas my list
>> requires the elements to have the node embedded in them, and so blocks
>> are also nodes.
> 
> Maybe you can then replace your private intrusive list with Boost.Intrusive:
> 
> http://igaztanaga.drivehq.com/intrusive
> 
> which is already included in the SVN trunk.
> 
> Joaquín M López Muñoz
> Telefónica, Investigación y Desarrollo
> 
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
> 


#include <iostream>
#include <list>
using namespace std;

#ifdef WIN32

#include <windows.h>

class PerformanceCounter {
public:
    PerformanceCounter() {
        QueryPerformanceFrequency(&_frequency);
    }
    
    void start() {
        QueryPerformanceCounter(&_start);
    }

    void end() {
        QueryPerformanceCounter(&_end);
    }
    
    double duration() const {
        return (((double)_end.QuadPart - (double)_start.QuadPart) / (double)_frequency.QuadPart) * 1000.0;
    }

private:
    LARGE_INTEGER _frequency;
    LARGE_INTEGER _start;
    LARGE_INTEGER _end;
};

#else

#include <sys/time.h>

class PerformanceCounter {
public:
    PerformanceCounter() {
    }
    
    void start() {
        _start = clock();
    }

    void end() {
        _end = clock();
    }
    
    double duration() const {
        return _end - _start;
    }

private:
    double _start;
    double _end;
    
    static double clock(void) {
        struct timeval t;
        struct timezone tz;
        if (gettimeofday( &t, &tz ) == -1) return 0;
        return (t.tv_sec * 1000 + t.tv_usec / 1000);
    }    
};

#endif //WIN32

//a double-linked list class where nodes have embedded links to previous/next items
template <class T> struct _list {
public:
    //initializes the object; use instead of constructor;
    //the data structure is allocated statically and initialized manually;
    //it solves the problem of initialization order of static data
    inline void _init() {
        _begin = &_begin_elem;
        _end = &_end_elem;
        _begin_elem._list_next = _end;
        _end_elem._list_prev = _begin;
    }

    inline void _cleanup() {
    }

    //get first element
    inline T * begin() const {
        return _begin_elem._list_next;
    }

    //get end element
    inline const T *end() const {
        return &_end_elem;
    }

    //adds an element as the last entry
    inline void add(T *elem) {
        elem->_list_next = &_end_elem;
        elem->_list_prev = _end_elem._list_prev;
        _end_elem._list_prev->_list_next = elem;
        _end_elem._list_prev = elem;
    }

    //removes an element
    inline void remove(T *elem) {
        elem->_list_prev->_list_next = elem->_list_next;
        elem->_list_next->_list_prev = elem->_list_prev;
    }

private:
    T *_begin;
    T *_end;
    T _begin_elem;
    T _end_elem;
};

class Foo1 {
public:
    Foo1 *_list_next, *_list_prev;
    int i, j;
    
    Foo1() {
        _list_next = _list_prev = 0;
        i = j = 0;
    }
};

class Foo2 {
public:
    int i, j;
    
    Foo2() {
        i = j = 0;
    }
};

int main() {
    typedef _list<Foo1> foo1_list_t;
    typedef std::list<Foo2 *> foo2_list_t;
    
    foo1_list_t foo1_list;
    foo1_list._init();
    
    foo2_list_t foo2_list;

    PerformanceCounter pc;
    
    static const size_t _MAX = 100000;
    static Foo1 foo1[_MAX];
    static Foo2 foo2[_MAX];
    
    pc.start();
    for(size_t i = 0; i < _MAX; ++i) {
        foo2_list.push_back(foo2 + i);
    }
    for(foo2_list_t::iterator it = foo2_list.begin(); it != foo2_list.end(); ++it) {
        Foo2 *f = *it;
        ++f->i;
        ++f->j;
    }
    while (!foo2_list.empty()) {
        foo2_list.pop_front();
    }
    pc.end();    
    cout << "std::list duration = " << pc.duration() << endl;

    pc.start();
    for(size_t i = 0; i < _MAX; ++i) {
        foo1_list.add(foo1 + i);
    }
    for(Foo1 *f = foo1_list.begin(); f != foo1_list.end(); f = f->_list_next) {
        ++f->i;
        ++f->j;
    }
    while (foo1_list.begin() != foo1_list.end()) {
        foo1_list.remove(foo1_list.begin());
    }
    pc.end();    
    cout << "_list duration = " << pc.duration() << endl;

    getchar();
    return 0;
}