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

15 May 2017


      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
   bool operator==(
     const poly_collection& x,
     const poly_collection& y)
   {
     typename poly_collection::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