[Boost-users] boost::multi_index_container::erase very slow on FreeBSD 6.0

From: bert hubert (bert.hubert_at_[hidden])
Date: 2006-03-16 16:59:59

Ok, regarding my previous message, I've now boiled down the problem of
quadratically slower erases to something that does happen on FreeBSD 6.0 and
doesn't happen on my Linux machines.

The problem may be due to:
        1) boost::multi_index container (highly unlikely)
        2) g++ allocator
        3) FreeBSD libc, if the g++ allocator relies on it
        4) FreeBSD kernel

And I don't even know where to start.

Output of attached program on FreeBSD 6.0, g++ 4.1:
$ ./cache-test
Creating..
Copying 499950 nodes
100                           162 usec            1.62 usec/erase
300                           2547 usec           8.49 usec/erase
500                           8132 usec           16.26 usec/erase
700                           68262 usec          97.52 usec/erase
900                           42949 usec          47.72 usec/erase
1100                          201873 usec         183.52 usec/erase
1300                          82376 usec          63.37 usec/erase
1500                          398186 usec         265.46 usec/erase
1700                          110701 usec         65.12 usec/erase

On Ubunty Breezy, g++ 4.1:
$ ./cache-test
Creating..
Copying 499950 nodes
100                           78 usec             0.78 usec/erase
300                           238 usec            0.79 usec/erase
500                           409 usec            0.82 usec/erase
700                           527 usec            0.75 usec/erase
900                           747 usec            0.83 usec/erase
1100                          812 usec            0.74 usec/erase
1300                          1112 usec           0.86 usec/erase
1500                          1084 usec           0.72 usec/erase
1700                          1545 usec           0.91 usec/erase

To reproduce, compile the following, which first seeds a container with
~50000 entries, copies it, erases n nodes, restores the original, erases
n+200 nodes etc.

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/key_extractors.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/format.hpp>
#include <vector>
#include <boost/utility.hpp>
#include <boost/lexical_cast.hpp>
#include <sys/time.h>
#include <time.h>
#include <iostream>

using namespace std;
using namespace boost;
using namespace boost::multi_index;

class DTime 
{
public:
  void set()
  {
    gettimeofday(&d_set,0);
  }

  unsigned int udiff()
  {
    struct timeval now;
    gettimeofday(&now,0);

    return 1000000*(now.tv_sec-d_set.tv_sec)+(now.tv_usec-d_set.tv_usec);
  }

private:
  struct timeval d_set;
};

struct StoredRecord
{
  mutable uint32_t d_ttd;

  string d_string;
  
  bool operator<(const StoredRecord& rhs) const
  {
    return d_string < rhs.d_string;
  }
};

struct CacheEntry
{
  CacheEntry(){}
  CacheEntry(const string& name, const vector<StoredRecord>& records) : d_name(name), d_records(records)
  {}
  string d_name;
  typedef vector<StoredRecord> records_t;
  records_t d_records;
  uint32_t getTTD() const
  {
    uint32_t earliest=numeric_limits<uint32_t>::max();
    for(records_t::const_iterator i=d_records.begin(); i != d_records.end(); ++i)
      earliest=min(earliest, i->d_ttd);
    return earliest;
  }
};

typedef multi_index_container<
  CacheEntry,
  indexed_by <
    hashed_unique<member<CacheEntry,string,&CacheEntry::d_name> >,
    ordered_non_unique<const_mem_fun<CacheEntry,uint32_t,&CacheEntry::getTTD> >
             >
   > cache_t;

int main()
{
  cache_t cache1, cache2;
  CacheEntry ce;
  StoredRecord sr;

  cout<<"Creating..\n";

  for(unsigned int n=0; n < 500000; ++n) {
    ce.d_name=lexical_cast<string>(random());
    sr.d_ttd=n/100 + (random() % 4)*300;
    ce.d_records.clear();
    ce.d_records.push_back(sr);
    sr.d_ttd=n/100 + (random() % 4)*300;
    ce.d_records.push_back(sr);
    cache1.insert(ce);
  }

  cout<<"Copying "<<cache1.size()<<" nodes\n";;
  cache2=cache1;

  typedef cache_t::nth_index<1>::type cache_by_ttd_t;
  cache_by_ttd_t& ttdindex=cache1.get<1>();

  cache_by_ttd_t::iterator limit=ttdindex.begin();
  unsigned int udiff;

  for(unsigned int n=100; n < 5000; n+=200) {
    DTime dt;
    dt.set();
    limit=boost::next(ttdindex.begin(), n);
    ttdindex.erase(ttdindex.begin(), limit);
    udiff=dt.udiff();
    cout << format("%d %|30t|%d usec %|50t|%.02f usec/erase\n") % n % udiff % (1.0*udiff/n);

    cache1=cache2;
  }

}

-- 
http://www.PowerDNS.com      Open source, database driven DNS Software 
http://netherlabs.nl              Open and Closed source services