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