1#include <roaring/portability.h>
2#include <roaring/containers/array.h>
3#include <roaring/misc/configreport.h>
4#include "benchmark.h"
5#include "random.h"
6
7enum { TESTSIZE = 2048 };
8// flushes the array from cache
9#if defined(IS_X64) && !(defined(_MSC_VER) && !defined(__clang__))
10void array_cache_flush(array_container_t* B) {
11 const int32_t CACHELINESIZE =
12 computecacheline(); // 64 bytes per cache line
13 for (int32_t k = 0; k < B->cardinality;
14 k += CACHELINESIZE / (int32_t)sizeof(uint16_t)) {
15 __builtin_ia32_clflush(B->array + k);
16 }
17}
18#else
19// no cache flush on other architectures?
20void array_cache_flush(array_container_t* B) { (void)B; }
21#endif
22
23// tries to put the array in cache
24void array_cache_prefetch(array_container_t* B) {
25#ifdef IS_X64
26 const int32_t CACHELINESIZE =
27 computecacheline(); // 64 bytes per cache line
28#else
29 const int32_t CACHELINESIZE = 64;
30#endif
31#if !(defined(_MSC_VER) && !defined(__clang__))
32 for (int32_t k = 0; k < B->cardinality;
33 k += CACHELINESIZE / (int32_t)sizeof(uint16_t)) {
34 __builtin_prefetch(B->array + k);
35 }
36#endif
37}
38
39int add_test(array_container_t* B) {
40 int x;
41 for (x = 0; x < (1 << 16); x += 3) {
42 array_container_add(B, (uint16_t)x);
43 }
44 return 0;
45}
46
47int remove_test(array_container_t* B) {
48 int x;
49 for (x = 0; x < (1 << 16); x += 3) {
50 array_container_remove(B, (uint16_t)x);
51 }
52 return 0;
53}
54int contains_test(array_container_t* B) {
55 int card = 0;
56 int x;
57 for (x = 0; x < (1 << 16); x++) {
58 card += array_container_contains(B, (uint16_t)x);
59 }
60 return card;
61}
62
63int union_test(array_container_t* B1, array_container_t* B2,
64 array_container_t* BO) {
65 array_container_union(B1, B2, BO);
66 return BO->cardinality;
67}
68
69int intersection_test(array_container_t* B1, array_container_t* B2,
70 array_container_t* BO) {
71 array_container_intersection(B1, B2, BO);
72 return BO->cardinality;
73}
74int main() {
75 int repeat = 500;
76 int size = TESTSIZE;
77 tellmeall();
78 printf("array container benchmarks\n");
79 array_container_t* B = array_container_create();
80 BEST_TIME(add_test(B), 0, repeat, size);
81 int answer = contains_test(B);
82 size = 1 << 16;
83 BEST_TIME(contains_test(B), answer, repeat, size);
84
85 size = (1 << 16) / 3;
86 BEST_TIME(remove_test(B), 0, repeat, size);
87 array_container_free(B);
88
89 for (int howmany = 32; howmany <= (1 << 16); howmany *= 8) {
90 array_container_t* Bt = array_container_create();
91 for (int j = 0; j < howmany; ++j) {
92 array_container_add(Bt, (uint16_t)pcg32_random());
93 }
94 size_t nbrtestvalues = 1024;
95 uint16_t* testvalues = malloc(nbrtestvalues * sizeof(uint16_t));
96 printf("\n number of values in container = %d\n", Bt->cardinality);
97 int card = array_container_cardinality(Bt);
98 uint32_t* out = malloc(sizeof(uint32_t) * (unsigned long)card);
99 BEST_TIME(array_container_to_uint32_array(out, Bt, 1234), card, repeat,
100 card);
101 free(out);
102 BEST_TIME_PRE_ARRAY(Bt, array_container_contains, array_cache_prefetch,
103 testvalues, nbrtestvalues);
104 BEST_TIME_PRE_ARRAY(Bt, array_container_contains, array_cache_flush,
105 testvalues, nbrtestvalues);
106 free(testvalues);
107 array_container_free(Bt);
108 }
109 printf("\n");
110
111 array_container_t* B1 = array_container_create();
112 for (int x = 0; x < 1 << 16; x += 3) {
113 array_container_add(B1, (uint16_t)x);
114 }
115 array_container_t* B2 = array_container_create();
116 for (int x = 0; x < 1 << 16; x += 5) {
117 array_container_add(B2, (uint16_t)x);
118 }
119 int32_t inputsize = B1->cardinality + B2->cardinality;
120 array_container_t* BO = array_container_create();
121 printf("\nUnion and intersections...\n");
122 printf("\nNote:\n");
123 printf(
124 "union times are expressed in cycles per number of input elements "
125 "(both arrays)\n");
126 printf(
127 "intersection times are expressed in cycles per number of output "
128 "elements\n\n");
129 printf("==intersection and union test 1 \n");
130 printf("input 1 cardinality = %d, input 2 cardinality = %d \n",
131 B1->cardinality, B2->cardinality);
132 answer = union_test(B1, B2, BO);
133 printf("union cardinality = %d \n", answer);
134 printf("B1 card = %d B2 card = %d \n", B1->cardinality, B2->cardinality);
135 BEST_TIME(union_test(B1, B2, BO), answer, repeat, inputsize);
136 answer = intersection_test(B1, B2, BO);
137 printf("intersection cardinality = %d \n", answer);
138 BEST_TIME(intersection_test(B1, B2, BO), answer, repeat, answer);
139 printf("==intersection and union test 2 \n");
140 array_container_clear(B1);
141 array_container_clear(B2);
142 for (int x = 0; x < 1 << 16; x += 16) {
143 array_container_add(B1, (uint16_t)x);
144 }
145 for (int x = 1; x < 1 << 16; x += x) {
146 array_container_add(B2, (uint16_t)x);
147 }
148 printf("input 1 cardinality = %d, input 2 cardinality = %d \n",
149 B1->cardinality, B2->cardinality);
150 answer = union_test(B1, B2, BO);
151 printf("union cardinality = %d \n", answer);
152 printf("B1 card = %d B2 card = %d \n", B1->cardinality, B2->cardinality);
153 BEST_TIME(union_test(B1, B2, BO), answer, repeat, inputsize);
154 answer = intersection_test(B1, B2, BO);
155 printf("intersection cardinality = %d \n", answer);
156 BEST_TIME(intersection_test(B1, B2, BO), answer, repeat, answer);
157
158 array_container_free(B1);
159 array_container_free(B2);
160 array_container_free(BO);
161 return 0;
162}
163