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