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

From: JOAQUIN LOPEZ MU?Z (joaquin_at_[hidden])
Date: 2006-03-12 10:52:34

Hi Bert,

----- Mensaje original -----
De: bert hubert <bert.hubert_at_[hidden]>
Fecha: Domingo, Marzo 12, 2006 11:31 am
Asunto: [Boost-users] SOLVED! Re:  multi_index 1.33.0,known problems 
with	RHEL 3	compiler (gcc 3.2.3)?

> On Sat, Mar 11, 2006 at 10:03:21PM +0100, JOAQUIN_LOPEZ_MU?Z wrote:
> > 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
[...]

Good! Thanks for using Boost.MultiIndex, hope
you're enjoying it.

> 
> 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::getTT
D> >
>               >
>  > 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:
[...]

So, the prunning code goes like:

/* 1 */
for(j=ttdindex.begin();j!=ttdindex.end();){
  // leave to-be-pruned elements at the beginning
  // of ttdindex
}

/* 2 */
ttdindex.erase(ttdindex.begin(), j);

So as to make sure, where do you observe the O(n^2)
behavior, /* 1 */ or /* 2 */ (or both) ? Can you
time both parts separately?

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo