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

12 Mar 2006

      Hi Bert,

----- Mensaje original -----
De: bert hubert 
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::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 >,
ordered_non_unique >
...
>
...
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

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

JOAQUIN LOPEZ MU?Z