Pixie
Loading...
Searching...
No Matches
implementations.h
Go to the documentation of this file.
1#pragma once
2
12
13// clang-format off
14/*
15 * RMQ benchmark snapshot, 2026-07-01.
16 *
17 * Commands used for the affected hybrid variants:
18 * taskset -c 0 ./build/benchmark-all-backends/rmq_benchmarks
19 * --benchmark_filter='^rmq_(hybrid_btree|cartesian_hybrid_btree|cartesian_btree)/(1024|16384|262144|4194304|16777216|67108864)/'
20 * --benchmark_report_aggregates_only=true
21 * --benchmark_display_aggregates_only=true
22 *
23 * taskset -c 0 ./build/benchmark-all-backends/rmq_benchmarks
24 * --benchmark_filter='^rmq_build_(hybrid_btree|cartesian_hybrid_btree|cartesian_btree)/(1024|16384|262144|4194304|16777216|67108864)(/|$)'
25 * --benchmark_report_aggregates_only=true
26 * --benchmark_display_aggregates_only=true
27 *
28 * Tables report one pinned Release pass using the benchmark defaults:
29 * 0.2 s warmup and 2.0 s minimum time. Query times are CPU nanoseconds;
30 * build times are CPU milliseconds. Sparse-table rows are intentionally
31 * not registered above 2^22. Benchmarks use 64-bit signed integer values
32 * and 64-bit indexes. Owned auxiliary memory excludes external input values.
33 * Rows above 2^26 are focused large-RMQ measurements; unavailable columns are
34 * marked with "-".
35 * CartesianBTree is CartesianHybridBTree without the value-level top sparse overlay.
36 *
37 * Compact method names:
38 * sparse=SparseTable, seg=SegmentTree, hybrid=HybridBTree,
39 * cart-rmm=CartesianRmM, cart-hybrid=CartesianHybridBTree,
40 * cart-btree=CartesianBTree, sdsl-sct=SDSL SCT.
41 *
42 * Query CPU time, ns.
43 *
44 * | N | width | sparse | seg | hybrid | cart-rmm | cart-hybrid | cart-btree | sdsl-sct |
45 * | ---: | ----: | -----: | ----: | -----: | -------: | ----------: | ---------: | -------: |
46 * | 2^10 | 64 | 17.2 | 51.3 | 42.2 | 86.7 | 99.7 | 97.1 | 136.9 |
47 * | 2^10 | 2^10 | 24.0 | 76.4 | 49.5 | 171.8 | 138.0 | 137.2 | 245.9 |
48 * | ---: | ----: | -----: | ----: | -----: | -------: | ----------: | ---------: | -------: |
49 * | 2^14 | 64 | 19.0 | 54.1 | 45.4 | 103.4 | 118.2 | 117.2 | 166.1 |
50 * | 2^14 | 4096 | 20.1 | 103.8 | 65.7 | 246.2 | 115.3 | 116.9 | 512.3 |
51 * | 2^14 | 2^14 | 18.1 | 114.9 | 33.7 | 329.7 | 48.2 | 98.5 | 612.8 |
52 * | ---: | ----: | -----: | ----: | -----: | -------: | ----------: | ---------: | -------: |
53 * | 2^18 | 64 | 36.3 | 78.1 | 53.9 | 103.0 | 131.2 | 130.2 | 187.0 |
54 * | 2^18 | 4096 | 35.7 | 148.7 | 83.1 | 271.5 | 251.2 | 248.8 | 655.6 |
55 * | 2^18 | 2^18 | 27.8 | 196.8 | 24.7 | 452.4 | 37.3 | 285.2 | 838.7 |
56 * | ---: | ----: | -----: | ----: | -----: | -------: | ----------: | ---------: | -------: |
57 * | 2^22 | 64 | 89.3 | 170.5 | 142.6 | 115.0 | 148.3 | 149.3 | 211.0 |
58 * | 2^22 | 4096 | 73.2 | 310.2 | 136.0 | 305.0 | 301.7 | 300.9 | 808.0 |
59 * | 2^22 | 2^18 | 61.9 | 461.6 | 40.7 | 601.0 | 59.3 | 245.4 | 1078.0 |
60 * | 2^22 | 2^22 | 57.3 | 507.1 | 19.9 | 605.0 | 19.1 | 138.6 | 1018.0 |
61 * | ---: | ----: | -----: | ----: | -----: | -------: | ----------: | ---------: | -------: |
62 * | 2^24 | 64 | - | 193.9 | 175.8 | 170.5 | 230.0 | 218.1 | 274.9 |
63 * | 2^24 | 4096 | - | 365.6 | 187.1 | 470.7 | 425.6 | 441.8 | 931.9 |
64 * | 2^24 | 2^18 | - | 497.2 | 57.8 | 748.7 | 89.3 | 408.6 | 1276.3 |
65 * | 2^24 | 2^22 | - | 603.4 | 28.7 | 857.6 | 25.7 | 285.7 | 1287.3 |
66 * | 2^24 | 2^24 | - | 574.9 | 19.5 | 862.1 | 16.5 | 311.4 | 1251.4 |
67 * | ---: | ----: | -----: | ----: | -----: | -------: | ----------: | ---------: | -------: |
68 * | 2^26 | 64 | - | 250.4 | 201.3 | 250.0 | 276.0 | 273.8 | 559.0 |
69 * | 2^26 | 4096 | - | 450.0 | 237.7 | 571.0 | 497.2 | 520.6 | 1409.0 |
70 * | 2^26 | 2^18 | - | 678.1 | 87.8 | 895.0 | 114.7 | 487.5 | 2090.0 |
71 * | 2^26 | 2^22 | - | 697.8 | 40.0 | 930.0 | 36.6 | 370.2 | 2163.0 |
72 * | 2^26 | 2^26 | - | 698.8 | 19.1 | 1255.0 | 17.6 | 401.6 | 2299.0 |
73 * | ---: | ----: | -----: | ----: | -----: | -------: | ----------: | ---------: | -------: |
74 * | 2^28 | 64 | - | - | 300.0 | 438.8 | 451.8 | - | - |
75 * | 2^28 | 4096 | - | - | 372.6 | 968.1 | 803.9 | - | - |
76 * | 2^28 | 2^18 | - | - | 224.9 | 1516.5 | 416.6 | - | - |
77 * | 2^28 | 2^22 | - | - | 56.9 | 1441.8 | 77.2 | - | - |
78 * | 2^28 | 2^26 | - | - | 21.2 | 1449.2 | 31.7 | - | - |
79 * | 2^28 | 2^28 | - | - | 21.3 | 1537.7 | 19.0 | - | - |
80 * | ---: | ----: | -----: | ----: | -----: | -------: | ----------: | ---------: | -------: |
81 * | 2^30 | 64 | - | - | 334.2 | 659.2 | 656.2 | - | - |
82 * | 2^30 | 4096 | - | - | 408.5 | 1038.2 | 1006.4 | - | - |
83 * | 2^30 | 2^18 | - | - | 557.7 | 1829.2 | 927.3 | - | - |
84 * | 2^30 | 2^22 | - | - | 145.5 | 2487.1 | 258.8 | - | - |
85 * | 2^30 | 2^26 | - | - | 45.5 | 2546.9 | 82.3 | - | - |
86 * | 2^30 | 2^30 | - | - | 30.4 | 2103.8 | 28.5 | - | - |
87 *
88 * Build CPU time, ms.
89 *
90 * | N | sparse | seg | hybrid | cart-rmm | cart-hybrid | cart-btree | sdsl-sct |
91 * | ---: | ------: | -------: | -------: | --------: | ----------: | ---------: | -------: |
92 * | 2^10 | 0.007 | 0.001 | 0.002 | 0.014 | 0.013 | 0.012 | 0.007 |
93 * | ---: | ------: | -------: | -------: | --------: | ----------: | ---------: | -------: |
94 * | 2^14 | 1.232 | 0.014 | 0.028 | 0.137 | 0.136 | 0.121 | 0.218 |
95 * | ---: | ------: | -------: | -------: | --------: | ----------: | ---------: | -------: |
96 * | 2^18 | 30.883 | 0.279 | 0.461 | 3.372 | 3.214 | 3.053 | 2.556 |
97 * | ---: | ------: | -------: | -------: | --------: | ----------: | ---------: | -------: |
98 * | 2^22 | 715.861 | 65.124 | 8.863 | 50.700 | 55.171 | 52.499 | 47.500 |
99 * | ---: | ------: | -------: | -------: | --------: | ----------: | ---------: | -------: |
100 * | 2^24 | - | 276.132 | 35.783 | 225.624 | 226.634 | 204.719 | 170.930 |
101 * | ---: | ------: | -------: | -------: | --------: | ----------: | ---------: | -------: |
102 * | 2^26 | - | 1281.908 | 138.485 | 821.000 | 874.314 | 849.984 | 813.000 |
103 * | ---: | ------: | -------: | -------: | --------: | ----------: | ---------: | -------: |
104 * | 2^28 | - | - | 586.827 | 3730.628 | 3347.897 | - | - |
105 * | ---: | ------: | -------: | -------: | --------: | ----------: | ---------: | -------: |
106 * | 2^30 | - | - | 2324.537 | 15002.269 | 16070.000 | - | - |
107 *
108 * Owned auxiliary memory, MiB.
109 *
110 * | N | sparse | seg | hybrid | cart-rmm | cart-hybrid | cart-btree | sdsl-sct |
111 * | ---: | ------: | -------: | ------: | -------: | ----------: | ---------: | -------: |
112 * | 2^10 | 0.071 | 0.016 | 0.001 | 0.004 | 0.014 | 0.014 | 0.001 |
113 * | ---: | ------: | -------: | ------: | -------: | ----------: | ---------: | -------: |
114 * | 2^14 | 1.626 | 0.250 | 0.003 | 0.008 | 0.018 | 0.017 | 0.005 |
115 * | ---: | ------: | -------: | ------: | -------: | ----------: | ---------: | -------: |
116 * | 2^18 | 34.001 | 4.000 | 0.036 | 0.077 | 0.082 | 0.079 | 0.079 |
117 * | ---: | ------: | -------: | ------: | -------: | ----------: | ---------: | -------: |
118 * | 2^22 | 672.001 | 64.000 | 0.606 | 1.180 | 1.139 | 1.053 | 1.262 |
119 * | ---: | ------: | -------: | ------: | -------: | ----------: | ---------: | -------: |
120 * | 2^24 | - | 256.000 | 2.483 | 4.711 | 4.578 | 4.171 | 5.051 |
121 * | ---: | ------: | -------: | ------: | -------: | ----------: | ---------: | -------: |
122 * | 2^26 | - | 1024.000 | 10.182 | 18.836 | 18.519 | 16.644 | 20.224 |
123 * | ---: | ------: | -------: | ------: | -------: | ----------: | ---------: | -------: |
124 * | 2^28 | - | - | 35.102 | 75.333 | 68.411 | - | - |
125 * | ---: | ------: | -------: | ------: | -------: | ----------: | ---------: | -------: |
126 * | 2^30 | - | - | 134.783 | 301.325 | 267.979 | - | - |
127 *
128 * Owned auxiliary memory normalized by indexed value count, bits/value.
129 *
130 * | N | sparse | seg | hybrid | cart-rmm | cart-hybrid | cart-btree | sdsl-sct |
131 * | ---: | -------: | ------: | -----: | -------: | ----------: | ---------: | -------: |
132 * | 2^10 | 579.188 | 128.438 | 4.500 | 29.625 | 112.938 | 112.875 | 7.312 |
133 * | ---: | -------: | ------: | -----: | -------: | ----------: | ---------: | -------: |
134 * | 2^14 | 832.262 | 128.027 | 1.293 | 3.852 | 8.977 | 8.930 | 2.770 |
135 * | ---: | -------: | ------: | -----: | -------: | ----------: | ---------: | -------: |
136 * | 2^18 | 1088.020 | 128.002 | 1.162 | 2.450 | 2.625 | 2.516 | 2.534 |
137 * | ---: | -------: | ------: | -----: | -------: | ----------: | ---------: | -------: |
138 * | 2^22 | 1344.002 | 128.000 | 1.211 | 2.360 | 2.277 | 2.105 | 2.524 |
139 * | ---: | -------: | ------: | -----: | -------: | ----------: | ---------: | -------: |
140 * | 2^24 | - | 128.000 | 1.242 | 2.356 | 2.289 | 2.086 | 2.526 |
141 * | ---: | -------: | ------: | -----: | -------: | ----------: | ---------: | -------: |
142 * | 2^26 | - | 128.000 | 1.273 | 2.354 | 2.315 | 2.081 | 2.528 |
143 * | ---: | -------: | ------: | -----: | -------: | ----------: | ---------: | -------: |
144 * | 2^28 | - | - | 1.097 | 2.354 | 2.138 | - | - |
145 * | ---: | -------: | ------: | -----: | -------: | ----------: | ---------: | -------: |
146 * | 2^30 | - | - | 1.053 | 2.354 | 2.094 | - | - |
147 */
148// clang-format on
149
150#include <pixie/rmq.h>
151#include <pixie/rmq/cartesian_hybrid_btree.h>
152#include <pixie/rmq/cartesian_rmm.h>
153#include <pixie/rmq/hybrid_btree.h>
154#include <pixie/rmq/segment_tree.h>
155#include <pixie/rmq/sparse_table.h>
156
157#ifdef SDSL_SUPPORT
158#include <pixie/rmq/sdsl_sct.h>
159#endif
rmq.h
Common interface for static range-minimum-query indexes.