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

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