1#define _GNU_SOURCE
2#include <roaring/roaring.h>
3#include <math.h>
4#include "benchmark.h"
5#include "random.h"
6
7enum order_e {
8 ASC,
9 DESC,
10 SHUFFLE
11};
12typedef enum order_e order_t;
13
14/*
15 * Generate a number of non-overlapping intervals inside [0, $spanlen),
16 * each interval is of length $intvlen.
17 * Returns number of intervals and their offsets.
18 *
19 * TODO also generate overlapping intervals
20 */
21void make_data(uint32_t spanlen, uint32_t intvlen, double density, order_t order,
22 uint32_t **offsets_out, uint32_t *count_out) {
23
24 uint32_t count = floor(spanlen * density / intvlen);
25 uint32_t *offsets = malloc(count * sizeof(uint32_t));
26
27 uint64_t sum = 0;
28 for (uint32_t i = 0; i < count; i++) {
29 offsets[i] = pcg32_random_r(&pcg32_global);
30 sum += offsets[i];
31 }
32 for (uint32_t i = 0; i < count; i++) {
33 double v = offsets[i];
34 v /= sum;
35 v *= (spanlen - count * intvlen) / (double)intvlen;
36 uint32_t gap = floor(v);
37
38 if (i == 0) {
39 offsets[i] = gap;
40 } else {
41 offsets[i] = offsets[i-1] + intvlen + gap;
42 }
43 }
44
45 if (order == SHUFFLE) {
46 shuffle_uint32(offsets, count);
47 } else if (order == DESC) {
48 for (uint32_t i = 0, j = count-1; i < count/2; i++, j--) {
49 uint32_t tmp = offsets[i];
50 offsets[i] = offsets[j];
51 offsets[j] = tmp;
52 }
53 }
54
55 *offsets_out = offsets;
56 *count_out = count;
57}
58
59double array_min(double *arr, size_t len) {
60 double min = arr[0];
61 for (size_t i = 1; i < len; i++) {
62 if (arr[i] < min) {
63 min = arr[i];
64 }
65 }
66 return min;
67}
68
69void run_test(uint32_t spanlen, uint32_t intvlen, double density, order_t order) {
70 printf("intvlen=%u density=%f order=%s\n", intvlen, density,
71 (order == ASC ? "ASC" :
72 (order == DESC ? "DESC" :
73 (order == SHUFFLE ? "SHUFFLE" : "???"))));
74
75 uint32_t *offsets;
76 uint32_t count;
77 make_data(spanlen, intvlen, density, order, &offsets, &count);
78 const int num_passes = 5;
79 uint64_t cycles_start, cycles_final;
80 double results[num_passes];
81
82 printf(" roaring_bitmap_add():");
83 for (int p = 0; p < num_passes; p++) {
84 roaring_bitmap_t *r = roaring_bitmap_create();
85 RDTSC_START(cycles_start);
86 for (int64_t i = 0; i < count; i++) {
87 for (uint32_t j = 0; j < intvlen; j++) {
88 roaring_bitmap_add(r, offsets[i] + j);
89 }
90 }
91 RDTSC_FINAL(cycles_final);
92 results[p] = (cycles_final - cycles_start) * 1.0 / count / intvlen;
93 roaring_bitmap_free(r);
94 }
95 printf(" %6.1f\n", array_min(results, num_passes));
96
97 printf(" roaring_bitmap_add_many():");
98 for (int p = 0; p < num_passes; p++) {
99 roaring_bitmap_t *r = roaring_bitmap_create();
100 RDTSC_START(cycles_start);
101 uint32_t values[intvlen];
102 for (int64_t i = 0; i < count; i++) {
103 for (uint32_t j = 0; j < intvlen; j++) {
104 values[j] = offsets[i] + j;
105 }
106 roaring_bitmap_add_many(r, intvlen, values);
107 }
108 RDTSC_FINAL(cycles_final);
109 results[p] = (cycles_final - cycles_start) * 1.0 / count / intvlen;
110 roaring_bitmap_free(r);
111 }
112 printf(" %6.1f\n", array_min(results, num_passes));
113
114 printf(" roaring_bitmap_add_range():");
115 for (int p = 0; p < num_passes; p++) {
116 roaring_bitmap_t *r = roaring_bitmap_create();
117 RDTSC_START(cycles_start);
118 for (int64_t i = 0; i < count; i++) {
119 roaring_bitmap_add_range(r, offsets[i], offsets[i]+intvlen);
120 }
121 RDTSC_FINAL(cycles_final);
122 results[p] = (cycles_final - cycles_start) * 1.0 / count / intvlen;
123 roaring_bitmap_free(r);
124 }
125 printf(" %6.1f\n", array_min(results, num_passes));
126
127 printf(" roaring_bitmap_remove():");
128 for (int p = 0; p < num_passes; p++) {
129 roaring_bitmap_t *r = roaring_bitmap_create();
130 roaring_bitmap_add_range(r, 0, spanlen);
131 RDTSC_START(cycles_start);
132 for (int64_t i = 0; i < count; i++) {
133 for (uint32_t j = 0; j < intvlen; j++) {
134 roaring_bitmap_remove(r, offsets[i] + j);
135 }
136 }
137 RDTSC_FINAL(cycles_final);
138 results[p] = (cycles_final - cycles_start) * 1.0 / count / intvlen;
139 roaring_bitmap_free(r);
140 }
141 printf(" %6.1f\n", array_min(results, num_passes));
142
143 printf(" roaring_bitmap_remove_range():");
144 for (int p = 0; p < num_passes; p++) {
145 roaring_bitmap_t *r = roaring_bitmap_create();
146 roaring_bitmap_add_range(r, 0, spanlen);
147 RDTSC_START(cycles_start);
148 for (int64_t i = 0; i < count; i++) {
149 roaring_bitmap_remove_range(r, offsets[i], offsets[i]+intvlen);
150 }
151 RDTSC_FINAL(cycles_final);
152 results[p] = (cycles_final - cycles_start) * 1.0 / count / intvlen;
153 roaring_bitmap_free(r);
154 }
155 printf(" %6.1f\n", array_min(results, num_passes));
156
157 free(offsets);
158}
159
160int main(int argc, char* argv[]) {
161 (void)argc;
162 (void)argv;
163
164 const uint32_t spanlen = 1000*1000;
165 uint32_t intvlen_array[] = {1, 4, 16, 64};
166 order_t order_array[] = {SHUFFLE, ASC, DESC};
167 printf("[cycles/element]\n");
168 for (size_t r = 0; r < sizeof(order_array)/sizeof(order_array[0]); r++) {
169 for (size_t i = 0; i < sizeof(intvlen_array)/sizeof(intvlen_array[0]); i++) {
170 run_test(spanlen, intvlen_array[i], 0.2, order_array[r]);
171 }
172 printf("\n");
173 }
174
175 return 0;
176}
177
178