Boost logo

Boost :

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,

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


Boost list run by bdawes at, gregod at, cpdaniel at, john at