Re: [boost] Proposal: Monotonic Containers: Performance test

Subject: Re: [boost] Proposal: Monotonic Containers: Performance test
From: Scott McMurray (me22.ca+boost_at_[hidden])
Date: 2009-06-11 01:29:50

2009/6/10 Christian Schladetsch <christian.schladetsch_at_[hidden]>:
>
> monotonic: 0.005
> std: 0.09
>

How about intrusive?  I had to up the count to 0x101010 to get a
measurable value, which gave the following timings (three runs,
reported in order):

mono: 1.37/1.41/1.38
std: 1.51/1.51/1.51
intrusive: 1.34/1.33/1.33

Upping it to 0x1010101 gave this:

mono: 35.82/35.71/35.82
std: 37.94/37.83/37.81
intrusive: 36.17/35.78/35.62

GCC 4.3.3 with -O3, 32-bit linux on Core2.

Here's the intrusive code:

struct mylistnode : list_base_hook<link_mode<normal_link> > {
        int i;
};

struct mymapnode : set_base_hook<link_mode<normal_link> > {
        list<mylistnode> v;	
        int k;
};
bool operator<(mymapnode const &lhs, mymapnode const &rhs) {
        return lhs.k < rhs.k;
}

union node {
        void *_;
        char mapnode[sizeof(mymapnode)];
        char listnode[sizeof(mylistnode)];
};

int main()
{
        unsigned const count = 0x101010;//101;

//	node nodes[count];
        node *nodes = new node[count];

    set<mymapnode> m;

    boost::timer timer;
    for (size_t i = 0; i < count; ++i)
    {
        int random = rand();
        mymapnode &mapnode = *(new(nodes[i].mapnode) mymapnode);
        mapnode.k = random;
        set<mymapnode>::iterator iter = m.find(mapnode);
        if (iter == m.end()) {
            m.insert(mapnode);
        } else {
                mapnode.~mymapnode();
                mylistnode &listnode = *(new(nodes[i].listnode) mylistnode);
            iter->v.push_back(listnode);
        }
    }
    double elapsed = timer.elapsed();
    cout << "intrusive: " << elapsed << endl;
}