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

15 May 2017

      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
My bad. Your code does what the docs say. You have this
// TODO: can we do better than two passes?
By that, do you mean that the first pass is the size() comparison?
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.
...
...
If one ever puts base_collection's into a container, you are in for a 
huge penalty when the container operation falls back on copying.
Fallback copying cannot occur to the best of my knowledge:
[container.requirements.general]/Notes:
"Those entries marked “(Note A)” or “(Note B)” have linear complexity 
for array and
have constant complexity for all other standard containers."
That is true, but as soon you hit code that calls std::move_if_noexcept,

http://en.cppreference.com/w/cpp/utility/move_if_noexcept

those move operations that are not marked/deduced noexcept will not be 
in effect.
...
As for noexcept in std unordered associative containers, I don't have a 
clue why
move construction is not marked conditionally noexcept the way move 
assignement
is... given this messy state I'd prefer to rely on =default before 
committing to any
noexcept guarantees.
Sounds reasonable. As I stated, it appears to me that you will take 
advantage of noexcept if it exists in the standard container.
...
I did that with this testing shuffled_base_collection class template:
template<typename Base>
   struct shuffled_base_collection
   {
     template<typename T>
     void insert(const T& x)
     {
       bc.insert(x);
     }
template<typename F>
     void for_each(F f)
     {
       std::for_each(v.begin(),v.end(),[&](Base* x){f(*x);});
     }
void prepare_for_for_each()
     {
       std::for_each(bc.begin(),bc.end(),[&](Base& x){v.push_back(&x);});
       std::shuffle(v.begin(),v.end(),std::mt19937(1));
     }
private:
     boost::base_collection<Base> bc;
     std::vector           v;
   };
(Complete performance program attached for your experimentation). 
Results for
Visual C++ 2015 in 32-bit (x86) release mode, Windows 7 64-bit, Intel Core
i5-2520M @2.5GHz, shuffled_base_collection is the fourth column:

...
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.

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

-Thorsten