[Boost-users] SOLVED! Re: multi_index 1.33.0, known problems with RHEL 3 compiler (gcc 3.2.3)?

From: bert hubert (bert.hubert_at_[hidden])
Date: 2006-03-12 05:31:19

On Sat, Mar 11, 2006 at 10:03:21PM +0100, JOAQUIN_LOPEZ_MU?Z wrote:
> 1. Shouldn't be the expression
>   waiters_by_ttd_index_t& ttdindex=d_waiters.get<KeyTag>();
> written as
>   waiters_by_ttd_index_t& ttdindex=d_waiters.template get<KeyTag>();

You may well be right, it does compile in the second form. gcc 4.1 does not
complain about the first though.

> 2. You might try the equivalent expression:
>
>   waiters_by_ttd_index_t& ttdindex=
>     boost::multi_index::get<KeyTag>(d_waiters);

Indeed, that solved the problem! I think what confused the older 'weaker'
gcc is that all this code is within a template class. Thank you Joaquin! See
http://mailman.powerdns.com/pipermail/pdns-users/2006-March/003140.html

On another note, g++ 4.1 gets Mighty Confused if you use a tag struct within
your templated class, I could only get tags to use if I defined my tag
struct outside my class - which makes some kind of sense.

Another question, I now have this:
  struct 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;

I then fill up a cache_t object, but I find that pruning it takes O(n^2)
time based on how many entries I prune in one go. I'm now pruning once every
10 seconds, which takes 10 to 20ms per try, if I prune once every 3 minutes,
pruning takes 10 seconds!

The odd thing is that it appears to matter how much you prune in one go,
without inserting something in the container in between. Perhaps the cost is
amortized?

The pruning code:
void MemRecursorCache::doPrune(void)
{
  unsigned int names=0;
  uint32_t now=(uint32_t)time(0);

//  cout<<"Going to prune!\n";

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

  uint32_t looked(0), quickZonk(0), fullZonk(0), partialZonk(0), noZonk(0);
  DTime dt;
  dt.set();
  cache_by_ttd_t::iterator j;
  for(j=ttdindex.begin();j!=ttdindex.end();){
    if(j->getTTD() > now) {
//      cout<<"Done pruning, this record ("<<j->d_name<<") only needs to get killed in "<< j->getTTD() - now <
      break;  // this code never gets called, the break near noZonk gets called first
    }
    else
        ;
//      cout<<"Looking at '"<<j->d_name<<"', "<<now - j->getTTD()<<" seconds overdue!\n";
    looked++;
    if(j->d_records.size()==1) {
//      ttdindex.erase(j++);
      j++;
      quickZonk++;
      continue;
    }
    predicate p(now);
    CacheEntry ce=*j;

    size_t before=ce.d_records.size();
    ce.d_records.erase(remove_if(ce.d_records.begin(), ce.d_records.end(), p), ce.d_records.end());
    if(ce.d_records.empty()) { // everything is gone
//      cout<<"Zonked it entirely!\n";
//      ttdindex.erase(j++);
      j++;
      fullZonk++;
    }
    else {
      if(ce.d_records.size()!=before) {
//      cout<<"Zonked partially, putting back, new TTD: "<< ce.getTTD() - now<<endl;;
        cache_by_ttd_t::iterator here=j++;
        ttdindex.replace(here, ce);
        partialZonk++;
      }
      else {
        ++j;
        noZonk++;
        break;
      }
    }
  }
  ttdindex.erase(ttdindex.begin(), j);
  cout<<"Took "<< dt.udiff()<<" useconds, looked: "<<looked<<", quick: "<<quickZonk<<", full: ";
  cout<<fullZonk<<", partial: "<<partialZonk<<", no: "<<noZonk<<"\n";
  //  cache_t(d_cache).swap(d_cache);
}

Any ideas? Multi_index has in any case save my bacon, pruning a map based
container took 10 seconds always :-)

> 3. Substituting identifiers (via an enum if you want
> to retain some legibility) for tags seem to reduce the stress
> on weaker compilers.

In fact, the code started out with identifiers, but that did not make a
difference.

Thanks for your help so far Joaquin!

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