1#define _GNU_SOURCE
2#include <roaring/roaring.h>
3#include "benchmark.h"
4#include "numbersfromtextfiles.h"
5
6/**
7 * Once you have collected all the integers, build the bitmaps.
8 */
9static roaring_bitmap_t **create_all_bitmaps(size_t *howmany,
10 uint32_t **numbers, size_t count,
11 bool runoptimize, bool copy_on_write) {
12 if (numbers == NULL) return NULL;
13 printf("Constructing %d bitmaps.\n", (int)count);
14 roaring_bitmap_t **answer = malloc(sizeof(roaring_bitmap_t *) * count);
15 for (size_t i = 0; i < count; i++) {
16 printf(".");
17 fflush(stdout);
18 answer[i] = roaring_bitmap_of_ptr(howmany[i], numbers[i]);
19 if(runoptimize) roaring_bitmap_run_optimize(answer[i]);
20 roaring_bitmap_shrink_to_fit(answer[i]);
21 roaring_bitmap_set_copy_on_write(answer[i], copy_on_write);
22 }
23 printf("\n");
24 return answer;
25}
26
27static void printusage(char *command) {
28 printf(
29 " Try %s directory \n where directory could be "
30 "benchmarks/realdata/census1881\n",
31 command);
32 ;
33}
34
35#define KNRM "\x1B[0m"
36#define KRED "\x1B[31m"
37#define KGRN "\x1B[32m"
38#define KYEL "\x1B[33m"
39#define KBLU "\x1B[34m"
40#define KMAG "\x1B[35m"
41#define KCYN "\x1B[36m"
42#define KWHT "\x1B[37m"
43
44int main(int argc, char **argv) {
45 int c;
46 const char *extension = ".txt";
47 bool copy_on_write = false;
48 bool runoptimize = true;
49 while ((c = getopt(argc, argv, "e:h")) != -1) switch (c) {
50 case 'e':
51 extension = optarg;
52 break;
53 case 'h':
54 printusage(argv[0]);
55 return 0;
56 default:
57 abort();
58 }
59 if (optind >= argc) {
60 printusage(argv[0]);
61 return -1;
62 }
63 char *dirname = argv[optind];
64 size_t count;
65
66 size_t *howmany = NULL;
67 uint32_t **numbers =
68 read_all_integer_files(dirname, extension, &howmany, &count);
69 if (numbers == NULL) {
70 printf(
71 "I could not find or load any data file with extension %s in "
72 "directory %s.\n",
73 extension, dirname);
74 return -1;
75 }
76
77 uint64_t cycles_start = 0, cycles_final = 0;
78
79 RDTSC_START(cycles_start);
80 roaring_bitmap_t **bitmaps =
81 create_all_bitmaps(howmany, numbers, count, runoptimize, copy_on_write);
82 RDTSC_FINAL(cycles_final);
83 if (bitmaps == NULL) return -1;
84 printf("Loaded %d bitmaps from directory %s \n", (int)count, dirname);
85
86 printf("Creating %zu bitmaps took %" PRIu64 " cycles\n", count,
87 cycles_final - cycles_start);
88
89 RDTSC_START(cycles_start);
90 for (int i = 0; i < (int)count; i += 2) {
91 roaring_bitmap_t *CI = roaring_bitmap_copy(
92 bitmaps[i]); // to test the inplace version we create a copy
93 roaring_bitmap_free(CI);
94 }
95 RDTSC_FINAL(cycles_final);
96 printf("Copying and freeing %zu bitmaps took %" PRIu64 " cycles\n", count,
97 cycles_final - cycles_start);
98
99 uint64_t successive_and = 0;
100 uint64_t successive_or = 0;
101 // try ANDing and ORing together consecutive pairs
102 for (int i = 0; i < (int)count - 1; ++i) {
103 uint32_t c1 = (uint32_t)roaring_bitmap_get_cardinality(bitmaps[i]);
104 uint32_t c2 = (uint32_t)roaring_bitmap_get_cardinality(bitmaps[i + 1]);
105 RDTSC_START(cycles_start);
106 roaring_bitmap_t *tempand =
107 roaring_bitmap_and(bitmaps[i], bitmaps[i + 1]);
108 RDTSC_FINAL(cycles_final);
109 successive_and += cycles_final - cycles_start;
110
111 uint32_t ci = (uint32_t)roaring_bitmap_get_cardinality(tempand);
112 roaring_bitmap_free(tempand);
113 RDTSC_START(cycles_start);
114 roaring_bitmap_t *tempor =
115 roaring_bitmap_or(bitmaps[i], bitmaps[i + 1]);
116 RDTSC_FINAL(cycles_final);
117 successive_or += cycles_final - cycles_start;
118
119 uint32_t co = (uint32_t)roaring_bitmap_get_cardinality(tempor);
120 roaring_bitmap_free(tempor);
121
122 if (c1 + c2 != co + ci) {
123 printf(KRED "cardinalities are wrong somehow\n");
124 printf("c1 = %d, c2 = %d, co = %d, ci = %d\n", c1, c2, co, ci);
125 return -1;
126 }
127 }
128 printf(" %zu successive bitmaps intersections took %" PRIu64 " cycles\n",
129 count - 1, successive_and);
130 printf(" %zu successive bitmaps unions took %" PRIu64 " cycles\n",
131 count - 1, successive_or);
132
133 roaring_bitmap_t **copyofr = malloc(sizeof(roaring_bitmap_t *) * count);
134 for (int i = 0; i < (int)count; i++) {
135 copyofr[i] = roaring_bitmap_copy(bitmaps[i]);
136 }
137 RDTSC_START(cycles_start);
138 for (int i = 0; i < (int)count - 1; i++) {
139 roaring_bitmap_and_inplace(copyofr[i], bitmaps[i + 1]);
140 }
141 RDTSC_FINAL(cycles_final);
142 printf(" %zu successive in-place bitmaps intersections took %" PRIu64
143 " cycles\n",
144 count - 1, cycles_final - cycles_start);
145
146 free(copyofr);
147 copyofr = malloc(sizeof(roaring_bitmap_t *) * count);
148 for (int i = 0; i < (int)count; i++) {
149 copyofr[i] = roaring_bitmap_copy(bitmaps[i]);
150 }
151 RDTSC_START(cycles_start);
152 for (int i = 0; i < (int)count - 1; i++) {
153 roaring_bitmap_or_inplace(copyofr[i], bitmaps[i + 1]);
154 }
155 RDTSC_FINAL(cycles_final);
156 printf(" %zu successive in-place bitmaps unions took %" PRIu64 " cycles\n",
157 count - 1, cycles_final - cycles_start);
158 size_t total_count = 0;
159 RDTSC_START(cycles_start);
160 for (size_t i = 0; i < count; ++i) {
161 roaring_bitmap_t *ra = bitmaps[i];
162 roaring_uint32_iterator_t j;
163 roaring_init_iterator(ra, &j);
164 while (j.has_value) {
165 total_count++;
166 roaring_advance_uint32_iterator(&j);
167 }
168 }
169 RDTSC_FINAL(cycles_final);
170
171 printf("Iterating over %zu bitmaps and %zu values took %" PRIu64
172 " cycles\n",
173 count, total_count, cycles_final - cycles_start);
174
175 for (int i = 0; i < (int)count; ++i) {
176 free(numbers[i]);
177 numbers[i] = NULL; // paranoid
178 roaring_bitmap_free(bitmaps[i]);
179 bitmaps[i] = NULL; // paranoid
180 }
181 free(bitmaps);
182 free(howmany);
183 free(numbers);
184
185 return 0;
186}
187