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 17:01:21

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.

>>  >>> E. should the test check (perhaps via static_assert) the conditions
>>  >>> under which move-construction and move-assignment is noexcept? 
>> (sorry
>
>>  > I don't get it. [...]
>>
>> My bad, I misread your question. Of course move construction and move
>> assignment do not throw or copy elements etc., but I didn't mark them as
>> noexcept following the no-noexcept signature of std unordered 
>> associative
>> containers. I don't know why the std has not made those noexcept.
>
> I guess some vendors wanted freedom, and then gave users the near 
> impossible task of tracking no-except/except impacts through their 
> code bases. Now, you use =default for all the move operations, so I 
> think they are required to be deduced to be noexcept exactly when they 
> can be. Though a static assertion in the tests can track any fault in 
> that logic.
>
> 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."

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.

>
>>  >>> S. The test are testing best possible scenario; a more realistic 
>> test
>>  >>> would be to copy pointers to an std::vector<base*>, shuffle it 
>> and run
>>  >>> update on that.
>> [...]
> So take the processing test. You already compare against a shuffled 
> ptr_vector<T>. So far so good. Now take a base_collection<T> as is 
> also done. Then take the address of every element in the base 
> collection and put them into a vector<T*>. Now shuffle this 
> vector<T*>'s content like you did for ptr_vector. Then compare the 
> processing time over a ptr_vector with the processing over the 
> vector<T*>.
>
> I claim this is a slightly more realistic test because one often wants 
> to impose an order of some or all of the elements in the 
> base_collection<T> before processing/iterating them somehow. So you 
> won't always access the items in the order induced by the 
> base_collection<T>. That's why I said that the current test is a 
> best-case scenario, and there is no need to change that test. But I 
> think it would be useful to see how much better your library is when 
> access is not segment-sequential even though storage is.

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:

for_each:
n;ptr_vector;sorted ptr_vector;shuffled ptr_vector;shuffled 
base_collection;base_collection;base_collection 
(poly::for_each);base_collection (restituted poly::for_each)
1000;68.6908;28.0432;86.3083;94.0958;37.7935;30.107;29.0816
2000;66.4786;27.1926;91.2408;96.0413;35.2004;27.8589;26.583
3100;65.5093;26.8698;89.2557;93.8447;34.4803;27.2731;26.1223
4310;64.4793;27.1499;89.499;98.0149;35.1578;28.2978;26.5429
5640;64.266;26.9044;91.033;98.202;34.2633;27.501;25.8809
7105;64.0913;26.8572;91.0014;97.3875;33.7854;27.4859;26.5453
8715;63.7974;27.3087;91.9985;98.399;34.2015;27.2596;25.599
10485;65.3485;26.5905;94.7418;97.5851;33.7521;27.6211;26.5611
12430;64.7723;27.3904;96.0209;99.1571;34.043;27.2985;26.1444
14575;64.2452;27.1067;96.5124;97.7042;34.5654;27.4023;25.8673
16930;65.1636;27.3421;98.1957;98.6361;34.0196;27.3581;25.9065
19520;64.7248;27.515;99.7822;99.5556;33.8953;27.5236;26.1173
22370;65.5374;27.8343;101.01;98.5953;33.8068;27.7628;27.0117
25505;65.0315;27.0511;103.225;101.638;34.2136;27.0208;26.2058
28955;64.1178;27.5933;103.772;105.797;33.9232;27.4988;26.231
32745;64.029;28.1792;103.421;106.625;33.8092;27.3831;25.794
36915;64.8421;28.1159;104.303;107.454;34.0542;27.405;25.7482
41505;65.1041;28.1572;105.835;108.924;34.07;27.1529;25.7295
46550;65.1797;27.8241;107.201;111.251;34.6232;27.6993;25.7345
52100;64.4235;28.0879;106.881;111.354;33.8314;27.0135;25.7227
58205;64.6465;27.9511;107.758;110.244;34.211;27.1424;25.8198
64920;65.1627;27.8584;110.97;111.413;34.7061;27.5941;26.0383
72305;65.5236;28.4969;111.552;112.634;34.0255;27.8747;25.7921
80430;66.1873;28.6039;115.026;114.442;34.3514;28.2707;25.6547
89365;66.3345;29.7042;119.888;114.368;33.976;27.5066;26.405
99195;67.5842;29.8768;132.691;118.178;33.8057;27.5137;26.3577
110005;67.502;33.2295;137.329;119.368;33.9743;28.261;25.8561
121900;67.8779;32.8886;144.397;119.939;34.0421;27.5768;26.1762
134980;73.2615;35.4748;215.428;150.062;35.1048;27.9387;26.3445
149370;69.5914;39.4097;166.049;132.759;35.3813;28.1609;26.5035
165195;70.0795;36.9757;176.128;125.824;35.4784;28.0991;27.1848
182605;70.678;39.4236;184.899;132.561;34.7531;27.9232;26.7449
201755;69.804;41.916;189.486;147.688;34.5916;28.4368;26.4968
222815;70.9049;43.3167;197.706;151.125;35.4652;28.6605;27.8671
245985;70.03;53.1854;201.855;164.847;35.7549;28.4426;27.1877
271470;69.6931;46.2775;209.332;179.249;36.2631;29.0661;28.4608
299505;70.9044;47.3569;212.374;194.289;36.024;29.2358;27.8824
330340;70.5898;47.0813;211.55;198.904;37.2955;29.1048;28.3034
364260;69.3568;48.0286;216.136;213.392;36.4719;29.6492;28.947
401570;70.0784;55.6783;217.553;216.374;36.6151;29.8494;28.6781
442610;70.2452;55.8915;222.709;222.249;36.4878;29.7408;28.192
487755;70.0358;48.7904;222.94;229.27;36.3237;30.3672;28.6129
537415;70.3103;50.0021;221.074;231.909;37.1915;30.0791;28.471
592040;70.1439;55.2571;223.077;234.858;37.6925;29.8299;28.4722
652125;70.8862;51.2554;230.277;239.505;37.3451;30.2505;28.1771
718220;70.4251;49.5872;233.219;239.863;36.5727;30.2672;28.6706
790920;69.7149;55.3772;230.926;242.922;37.2833;30.2138;28.9888
870895;69.4214;51.0372;235.172;251.45;36.9112;30.0106;29.2397
958865;70.4314;51.3184;235.628;252.243;37.3236;30.2469;28.4398
1055630;70.0297;52.1747;240.768;253.405;36.8073;30.0849;28.7678
1162075;71.0985;50.314;247.533;259.274;37.3846;30.3551;28.422
1279160;71.061;55.4783;243.327;257.581;37.0938;29.5389;29.1207
1407955;70.1601;50.6091;247.387;264.074;37.0902;29.8258;28.5657
1549630;70.4848;50.497;246.17;264.641;36.97;30.0207;28.4441
1705470;69.8107;50.983;247.042;261.625;36.5883;30.2686;28.5624
1876895;69.9785;51.5235;252.602;266.711;36.9832;29.9705;29.0799
2065465;69.4235;51.4422;256.153;265.141;37.3256;29.9859;29.0338
2272885;69.8385;51.4589;250.552;266.472;37.3823;30.3282;28.4389
2501050;69.9755;55.2984;255.818;272.43;36.9822;29.7997;28.9513
2752030;69.9469;54.2768;256.759;266.995;37.3053;30.2714;28.5217
3028110;70.3192;50.6052;261.753;272.133;37.5515;30.1139;28.9316
3331795;70.5005;49.9084;266.412;277.529;37.3315;30.3557;29.0938
3665850;70.0603;56.1319;271.833;276.466;37.199;29.6312;29.383
4033310;70.3551;51.7834;270.162;276.077;37.2656;29.772;28.5666
4437515;70.1824;50.7757;278.203;278.845;36.9247;29.4452;28.7805
4882140;70.5786;49.2731;281.148;283.854;37.1183;30.1079;28.9781
5371225;70.0242;49.7885;285.602;287.699;37.0402;30.4146;28.411
5909220;69.9687;51.3314;284.474;282.396;36.4418;29.6589;28.3406
6501010;70.3126;55.6867;297.482;284.977;36.9394;30.0999;28.9472
7151985;69.8237;50.2656;295.983;286.696;36.7772;29.8695;28.7694
7868050;69.6268;55.6824;303.074;291.302;37.4062;30.572;29.7347
8655725;69.5738;50.8151;310.437;300.738;37.2501;30.0555;28.7516
9522170;69.8031;56.4064;317.517;301.382;36.8001;30.8586;28.9918
10475255;69.6152;50.142;331.536;302.847;37.3644;30.9883;29.0113

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.

Joaquín M López Muñoz