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

20 Sep 2007

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