Closed Jesus89 closed 2 years ago
This PR adds a relevant performance optimization in the cell_to_children function. Using bit operation instead of walking the XY space reduces the cost from O(n^2) to O(n). Additionally, cell/tile conversions are not required.
cell_to_children
cell: 5209574053332910079 res: 5 to 13
New approach
Old approach
------------------------------------------------------------------------------------------------------------------- benchmark: 18 tests -------------------------------------------------------------------------------------------------------------------- Name (time in ns) Min Max Mean StdDev Median IQR Outliers OPS Rounds Iterations ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ test_cell_to_children[5] 783.9990 (1.0) 44,246.9900 (1.61) 991.7945 (1.0) 618.5066 (1.70) 908.0104 (1.0) 66.9970 (1.0) 2347;3753 1,008,273.4358 (1.0) 81606 1 test_cell_to_children[6] 1,094.0130 (1.40) 27,429.9819 (1.0) 1,319.1557 (1.33) 364.5004 (1.0) 1,284.0028 (1.41) 80.9960 (1.21) 4028;4419 758,060.6191 (0.75) 102681 1 test_cell_to_children[7] 1,384.9931 (1.77) 29,283.5030 (1.07) 1,721.1886 (1.74) 517.2540 (1.42) 1,641.4997 (1.81) 218.4970 (3.26) 19219;20655 580,993.8622 (0.58) 166307 2 test_cell_to_children[8] 1,665.3309 (2.12) 171,949.6698 (6.27) 2,097.2357 (2.11) 725.4417 (1.99) 1,970.6689 (2.17) 220.6652 (3.29) 16867;19508 476,818.1346 (0.47) 165618 3 test_cell_to_children[9] 2,018.0014 (2.57) 49,246.9990 (1.80) 2,311.3809 (2.33) 503.2105 (1.38) 2,174.9875 (2.40) 262.0218 (3.91) 10418;10436 432,641.8015 (0.43) 192938 1 test_cell_to_children[10] 2,305.9838 (2.94) 42,300.9915 (1.54) 2,578.5224 (2.60) 458.3276 (1.26) 2,476.0084 (2.73) 107.0148 (1.60) 5609;37181 387,819.0146 (0.38) 175132 1 test_cell_to_children[11] 2,622.9827 (3.35) 41,669.9913 (1.52) 3,073.4448 (3.10) 707.6802 (1.94) 2,857.9962 (3.15) 357.0167 (5.33) 10331;10570 325,367.8111 (0.32) 162682 1 test_cell_to_children[12] 2,904.9988 (3.71) 58,398.9895 (2.13) 3,756.2357 (3.79) 1,280.0182 (3.51) 3,431.9819 (3.78) 428.0009 (6.39) 14206;15941 266,223.9750 (0.26) 105419 1 test_cell_to_children[13] 3,222.9873 (4.11) 1,835,944.0146 (66.93) 3,707.8726 (3.74) 4,968.8697 (13.63) 3,477.9951 (3.83) 133.0045 (1.99) 81;30004 269,696.4326 (0.27) 139315 1 test_old_cell_to_children[5] 5,139.0089 (6.55) 35,222.9981 (1.28) 5,867.1946 (5.92) 849.2204 (2.33) 5,690.0026 (6.27) 177.0095 (2.64) 2549;11020 170,439.2074 (0.17) 70413 1 test_old_cell_to_children[6] 16,306.0031 (20.80) 92,629.9836 (3.38) 18,596.3338 (18.75) 2,812.9970 (7.72) 17,994.9857 (19.82) 487.5037 (7.28) 1392;6854 53,774.0401 (0.05) 39724 1 test_old_cell_to_children[7] 60,517.0208 (77.19) 251,871.9994 (9.18) 69,207.8021 (69.78) 10,424.3428 (28.60) 66,917.0113 (73.70) 1,795.5026 (26.80) 452;1408 14,449.2379 (0.01) 9051 1 test_old_cell_to_children[8] 242,365.0003 (309.14) 595,567.0204 (21.71) 271,492.4274 (273.74) 42,354.8445 (116.20) 261,050.9982 (287.50) 11,773.0233 (175.72) 162;291 3,683.3440 (0.00) 3698 1 test_old_cell_to_children[9] 970,790.9776 (>1000.0) 2,246,804.0115 (81.91) 1,086,292.8505 (>1000.0) 182,599.1794 (500.96) 1,043,394.9938 (>1000.0) 35,392.5061 (528.27) 42;106 920.5621 (0.00) 861 1 test_old_cell_to_children[10] 3,928,577.0035 (>1000.0) 8,102,966.0068 (295.41) 4,368,348.6520 (>1000.0) 668,578.4139 (>1000.0) 4,178,454.0226 (>1000.0) 137,178.7439 (>1000.0) 9;26 228.9195 (0.00) 161 1 test_old_cell_to_children[11] 16,511,858.0044 (>1000.0) 29,072,867.9975 (>1000.0) 17,557,080.9636 (>1000.0) 2,471,670.7730 (>1000.0) 16,826,074.0174 (>1000.0) 172,389.4820 (>1000.0) 4;7 56.9571 (0.00) 53 1 test_old_cell_to_children[12] 67,946,013.9945 (>1000.0) 79,509,528.9941 (>1000.0) 71,088,735.7687 (>1000.0) 3,418,857.1440 (>1000.0) 69,089,780.9982 (>1000.0) 4,829,202.2475 (>1000.0) 1;0 14.0669 (0.00) 13 1 test_old_cell_to_children[13] 277,176,820.9932 (>1000.0) 287,354,424.0138 (>1000.0) 283,554,252.4001 (>1000.0) 4,191,179.7512 (>1000.0) 284,898,861.0203 (>1000.0) 6,306,879.2515 (>1000.0) 1;0 3.5267 (0.00) 5 1 -----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
This PR adds a relevant performance optimization in the
cell_to_childrenfunction. Using bit operation instead of walking the XY space reduces the cost from O(n^2) to O(n). Additionally, cell/tile conversions are not required.Benchmark
cell: 5209574053332910079 res: 5 to 13
New approach
Old approach