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

Subject: Re: [boost] [review] Review of PolyCollection starts today (May 3rd)
From: Thorsten Ottosen (tottosen_at_[hidden])
Date: 2017-05-15 17:46:40

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<Base*>           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