Re: [boost] [review] Review of PolyCollection starts today (May 3rd)

Subject: Re: [boost] [review] Review of PolyCollection starts today (May 3rd)
From: Joaquin M López Muñoz (joaquinlopezmunoz_at_[hidden])
Date: 2017-05-15 19:21:44

El 15/05/2017 a las 19:46, Thorsten Ottosen via Boost escribió:
> Den 15-05-2017 kl. 19:01 skrev Joaquin M López Muñoz via Boost:
>> El 15/05/2017 a las 16:13, Thorsten Ottosen via Boost escribió:
>>>>  >>> D. Implementation of equality: do we need to be set like 
>>>> semantics
>>> [...]
>> OK, now I get it. Yes. the size() comparison does a first pass of both
>> containers' internal std::unordered_maps, and I wondered whether we
>> can come up with something smarter that avoids that.
>
> Hm. Yeah, I guess we have at least three options:
>
> a) current version
>
> b) omit check to "global" size() and let segment comparison deal with 
> that
>
> c) store the size in poly_collection
>
> I think c) is not that attractive due to all the code to provide 
> consistency. Whether a) is better than b) I guess will depend on the 
> on the actual runtime data. I speculate that your current version is 
> the best.
>

I think this variation of a) might perform better (code untested):

   template<typename Model,typename Allocator>
   bool operator==(
     const poly_collection<Model,Allocator>& x,
     const poly_collection<Model,Allocator>& y)
   {
     typename poly_collection<Model,Allocator>::size_type s=0;
     const auto &mapx=x.map,&mapy=y.map;
     for(const auto& p:mapx){
       s+=p.second.size();
       auto it=mapy.find(p.first);
if(it==mapy.end()?!p.second.empty():p.second!=it->second)return false;
     }
     if(s!=mapy.size())return false;
     return true;
   }

> [...]
>
>> So, shuffled ptr_vector and shuffled base_collection seem to perform 
>> equally
>> bad; I can't see any significant pattern here, which leads me to 
>> conclude
>> shuffling destroys any cache friendliness elements might have due to the
>> fact they come from a boost::base_collection.
>
> Thanks for quick update. It wasn't clear to me if your time includes 
> the time to insert and prepare_for_for_each. If so, it would be fair 
> to call
> v.reserve( bc.size() ); in prepare_for_for_each.

Timing does not include insert() or prepare_for_for_each().

> Anyway, it is a bit surprising. Perhaps modern allocators are good at 
> allocating same size objects closely and without much overhead ... 

I think the similarity in performance between shuffled ptr_vector and
shuffled base_collectin goes the other way around: once sequentiality is 
destroyed,
it doesn't matter much whether elements lie relativley close to each 
other in
main memory.

Joaquín M López Muñoz