search

improbable-eng / phtree-cpp

PH-Tree C++ implementation by Improbable.
Apache License 2.0
22 stars 15 forks source link

Remove std::variant #23

Closed improbable-til closed 2 years ago

improbable-til commented 2 years ago

Replacing Entry's "std::variant" with two single attributes improves update and query performance by about 10%, e.g. insert_benchmark:

OLD

-------------------------------------------------------------------------------
Benchmark                     Time             CPU   Iterations UserCounters...
-------------------------------------------------------------------------------
PhTree3D/INS_CU_1K        0.061 ms        0.061 ms        11091 put_rate=16.423M/s total_put_count=11.091M
PhTree3D/INS_CU_10K       0.817 ms        0.817 ms          840 put_rate=12.2401M/s total_put_count=8.4M
PhTree3D/INS_CU_100K       14.6 ms         14.6 ms           48 put_rate=6.85548M/s total_put_count=4.8M
PhTree3D/INS_CU_1M          318 ms          318 ms            2 put_rate=3.14162M/s total_put_count=2M
PhTree3D/INS_CU_10M        5542 ms         5542 ms            1 put_rate=1.80441M/s total_put_count=10M
PhTree3D/EMP_CU_1K        0.059 ms        0.059 ms        11863 put_rate=17.0557M/s total_put_count=11.863M
PhTree3D/EMP_CU_10K       0.807 ms        0.807 ms          849 put_rate=12.3852M/s total_put_count=8.49M
PhTree3D/EMP_CU_100K       14.0 ms         14.0 ms           50 put_rate=7.14215M/s total_put_count=5M
PhTree3D/EMP_CU_1M          312 ms          312 ms            2 put_rate=3.2011M/s total_put_count=2M
PhTree3D/EMP_CU_10M        5549 ms         5549 ms            1 put_rate=1.80213M/s total_put_count=10M
PhTree3D/SQB_CU_1K        0.062 ms        0.062 ms        10990 put_rate=16.2338M/s total_put_count=10.99M
PhTree3D/SQB_CU_10K       0.869 ms        0.869 ms          799 put_rate=11.5029M/s total_put_count=7.99M
PhTree3D/SQB_CU_100K       15.2 ms         15.1 ms           44 put_rate=6.60741M/s total_put_count=4.4M
PhTree3D/SQB_CU_1M          320 ms          320 ms            2 put_rate=3.12842M/s total_put_count=2M
PhTree3D/SQB_CU_10M        5618 ms         5616 ms            1 put_rate=1.78057M/s total_put_count=10M
PhTree3D/EMP_CL_1K        0.057 ms        0.057 ms        12317 put_rate=17.5601M/s total_put_count=12.317M
PhTree3D/EMP_CL_10K       0.718 ms        0.717 ms          935 put_rate=13.9439M/s total_put_count=9.35M
PhTree3D/EMP_CL_100K       7.94 ms         7.94 ms           88 put_rate=12.5926M/s total_put_count=8.8M
PhTree3D/EMP_CL_1M          104 ms          104 ms            6 put_rate=9.61453M/s total_put_count=6M
PhTree3D/EMP_CL_10M        1217 ms         1216 ms            1 put_rate=8.22086M/s total_put_count=10M

NEW

-------------------------------------------------------------------------------
Benchmark                     Time             CPU   Iterations UserCounters...
-------------------------------------------------------------------------------
PhTree3D/INS_CU_1K        0.053 ms        0.053 ms        11989 put_rate=18.8059M/s total_put_count=11.989M
PhTree3D/INS_CU_10K       0.775 ms        0.775 ms          891 put_rate=12.9019M/s total_put_count=8.91M
PhTree3D/INS_CU_100K       13.8 ms         13.8 ms           50 put_rate=7.27014M/s total_put_count=5M
PhTree3D/INS_CU_1M          308 ms          308 ms            2 put_rate=3.24371M/s total_put_count=2M
PhTree3D/INS_CU_10M        5474 ms         5473 ms            1 put_rate=1.82707M/s total_put_count=10M
PhTree3D/EMP_CU_1K        0.053 ms        0.053 ms        12957 put_rate=18.9283M/s total_put_count=12.957M
PhTree3D/EMP_CU_10K       0.763 ms        0.763 ms          874 put_rate=13.1071M/s total_put_count=8.74M
PhTree3D/EMP_CU_100K       13.4 ms         13.4 ms           52 put_rate=7.44064M/s total_put_count=5.2M
PhTree3D/EMP_CU_1M          325 ms          325 ms            2 put_rate=3.07442M/s total_put_count=2M
PhTree3D/EMP_CU_10M        5498 ms         5497 ms            1 put_rate=1.8191M/s total_put_count=10M
PhTree3D/SQB_CU_1K        0.052 ms        0.052 ms        13123 put_rate=19.1135M/s total_put_count=13.123M
PhTree3D/SQB_CU_10K       0.752 ms        0.752 ms          886 put_rate=13.3066M/s total_put_count=8.86M
PhTree3D/SQB_CU_100K       13.3 ms         13.3 ms           52 put_rate=7.54422M/s total_put_count=5.2M
PhTree3D/SQB_CU_1M          305 ms          305 ms            2 put_rate=3.27879M/s total_put_count=2M
PhTree3D/SQB_CU_10M        5560 ms         5560 ms            1 put_rate=1.7986M/s total_put_count=10M
PhTree3D/EMP_CL_1K        0.051 ms        0.051 ms        13544 put_rate=19.601M/s total_put_count=13.544M
PhTree3D/EMP_CL_10K       0.675 ms        0.675 ms          989 put_rate=14.8112M/s total_put_count=9.89M
PhTree3D/EMP_CL_100K       7.63 ms         7.63 ms           91 put_rate=13.1028M/s total_put_count=9.1M
PhTree3D/EMP_CL_1M          100 ms          100 ms            6 put_rate=9.95517M/s total_put_count=6M
PhTree3D/EMP_CL_10M        1177 ms         1177 ms            1 put_rate=8.49736M/s total_put_count=10M

This PR also cleans up the logic for splitting/merging nodes. This was planned anyway but was made necessary by MSVC refusing to compile without this change. It is a bit unclear what the problem exactly is, but apparently MSVC insists on 'moving' values (even though that isn't enforced) while not having a move-constructor/assignment for std::map (which is clearly a bug).