1#define _GNU_SOURCE
2#include <roaring/roaring.h>
3#include <stdio.h>
4#include "benchmark.h"
5int quickfull() {
6 printf("The naive approach works well when the bitmaps quickly become full\n");
7 uint64_t cycles_start, cycles_final;
8 size_t bitmapcount = 100;
9 size_t size = 1000000;
10 roaring_bitmap_t **bitmaps =
11 (roaring_bitmap_t **)malloc(sizeof(roaring_bitmap_t *) * bitmapcount);
12 for (size_t i = 0; i < bitmapcount; i++) {
13 bitmaps[i] = roaring_bitmap_from_range(0, 1000000, 1);
14 for (size_t j = 0; j < size / 20; j++)
15 roaring_bitmap_remove(bitmaps[i], rand() % size);
16 roaring_bitmap_run_optimize(bitmaps[i]);
17 }
18
19 RDTSC_START(cycles_start);
20 roaring_bitmap_t *answer0 = roaring_bitmap_or_many_heap(bitmapcount, (const roaring_bitmap_t **)bitmaps);
21 RDTSC_FINAL(cycles_final);
22 printf("%f cycles per union (many heap) \n",
23 (cycles_final - cycles_start) * 1.0 / bitmapcount);
24
25 RDTSC_START(cycles_start);
26 roaring_bitmap_t *answer1 = roaring_bitmap_or_many(bitmapcount, (const roaring_bitmap_t **)bitmaps);
27 RDTSC_FINAL(cycles_final);
28 printf("%f cycles per union (many) \n",
29 (cycles_final - cycles_start) * 1.0 / bitmapcount);
30
31 RDTSC_START(cycles_start);
32 roaring_bitmap_t *answer2 = roaring_bitmap_copy(bitmaps[0]);
33 for (size_t i = 1; i < bitmapcount; i++) {
34 roaring_bitmap_or_inplace(answer2, bitmaps[i]);
35 }
36 RDTSC_FINAL(cycles_final);
37 printf("%f cycles per union (naive) \n",
38 (cycles_final - cycles_start) * 1.0 / bitmapcount);
39
40 for (size_t i = 0; i < bitmapcount; i++) {
41 roaring_bitmap_free(bitmaps[i]);
42 }
43 free(bitmaps);
44 roaring_bitmap_free(answer0);
45 roaring_bitmap_free(answer1);
46 roaring_bitmap_free(answer2);
47 return 0;
48}
49
50int notsofull() {
51 printf("The naive approach works less well when the bitmaps do not quickly become full\n");
52 uint64_t cycles_start, cycles_final;
53 size_t bitmapcount = 100;
54 size_t size = 1000000;
55 roaring_bitmap_t **bitmaps =
56 (roaring_bitmap_t **)malloc(sizeof(roaring_bitmap_t *) * bitmapcount);
57 for (size_t i = 0; i < bitmapcount; i++) {
58 bitmaps[i] = roaring_bitmap_from_range(0, 1000000, 100);
59 for (size_t j = 0; j < size / 20; j++)
60 roaring_bitmap_remove(bitmaps[i], rand() % size);
61 roaring_bitmap_run_optimize(bitmaps[i]);
62 }
63
64 RDTSC_START(cycles_start);
65 roaring_bitmap_t *answer0 = roaring_bitmap_or_many_heap(bitmapcount, (const roaring_bitmap_t **)bitmaps);
66 RDTSC_FINAL(cycles_final);
67 printf("%f cycles per union (many heap) \n",
68 (cycles_final - cycles_start) * 1.0 / bitmapcount);
69
70 RDTSC_START(cycles_start);
71 roaring_bitmap_t *answer1 = roaring_bitmap_or_many(bitmapcount, (const roaring_bitmap_t **)bitmaps);
72 RDTSC_FINAL(cycles_final);
73 printf("%f cycles per union (many) \n",
74 (cycles_final - cycles_start) * 1.0 / bitmapcount);
75
76 RDTSC_START(cycles_start);
77 roaring_bitmap_t *answer2 = roaring_bitmap_copy(bitmaps[0]);
78 for (size_t i = 1; i < bitmapcount; i++) {
79 roaring_bitmap_or_inplace(answer2, bitmaps[i]);
80 }
81 RDTSC_FINAL(cycles_final);
82 printf("%f cycles per union (naive) \n",
83 (cycles_final - cycles_start) * 1.0 / bitmapcount);
84
85 for (size_t i = 0; i < bitmapcount; i++) {
86 roaring_bitmap_free(bitmaps[i]);
87 }
88 free(bitmaps);
89 roaring_bitmap_free(answer0);
90 roaring_bitmap_free(answer1);
91 roaring_bitmap_free(answer2);
92 return 0;
93}
94
95
96int main() {
97 printf("How to best aggregate the bitmaps is data-sensitive.\n");
98 quickfull();
99 notsofull();
100 return 0;
101}
102