1 #include <stdlib.h>
2 #include <string.h>
3
4 #include "bitbool.h"
5 #include "cmph.h"
6 #include "cmph_benchmark.h"
7 #include "linear_string_map.h"
8
9 // Generates a vector with random unique 32 bits integers
random_numbers_vector_new(cmph_uint32 size)10 cmph_uint32* random_numbers_vector_new(cmph_uint32 size) {
11 cmph_uint32 i = 0;
12 cmph_uint32 dup_bits = sizeof(cmph_uint32)*size*8;
13 char* dup = (char*)malloc(dup_bits/8);
14 cmph_uint32* vec = (cmph_uint32 *)malloc(sizeof(cmph_uint32)*size);
15 memset(dup, 0, dup_bits/8);
16 for (i = 0; i < size; ++i) {
17 cmph_uint32 v = random();
18 while (GETBIT(dup, v % dup_bits)) { v = random(); }
19 SETBIT(dup, v % dup_bits);
20 vec[i] = v;
21 }
22 free(dup);
23 return vec;
24 }
25
cmph_uint32_cmp(const void * a,const void * b)26 int cmph_uint32_cmp(const void *a, const void *b) {
27 return *(const cmph_uint32*)a - *(const cmph_uint32*)b;
28 }
29
create_lsmap_key(CMPH_ALGO algo,int iters)30 char* create_lsmap_key(CMPH_ALGO algo, int iters) {
31 char mphf_name[128];
32 snprintf(mphf_name, 128, "%s:%u", cmph_names[algo], iters);
33 return strdup(mphf_name);
34 }
35
36 static cmph_uint32 g_numbers_len = 0;
37 static cmph_uint32 *g_numbers = NULL;
38 static lsmap_t *g_created_mphf = NULL;
39 static lsmap_t *g_expected_probes = NULL;
40 static lsmap_t *g_mphf_probes = NULL;
41
bm_create(CMPH_ALGO algo,int iters)42 void bm_create(CMPH_ALGO algo, int iters) {
43 cmph_io_adapter_t* source = NULL;
44 cmph_config_t* config = NULL;
45 cmph_t* mphf = NULL;
46
47 if (iters > (int)g_numbers_len) {
48 fprintf(stderr, "No input with proper size.");
49 exit(-1);
50 }
51
52 source = cmph_io_struct_vector_adapter(
53 (void*)g_numbers, sizeof(cmph_uint32),
54 0, sizeof(cmph_uint32), iters);
55 config = cmph_config_new(source);
56 cmph_config_set_algo(config, algo);
57 mphf = cmph_new(config);
58 if (!mphf) {
59 fprintf(stderr, "Failed to create mphf for algorithm %s with %u keys",
60 cmph_names[algo], iters);
61 exit(-1);
62 }
63 cmph_config_destroy(config);
64 cmph_io_struct_vector_adapter_destroy(source);
65 lsmap_append(g_created_mphf, create_lsmap_key(algo, iters), mphf);
66 }
67
bm_search(CMPH_ALGO algo,int iters)68 void bm_search(CMPH_ALGO algo, int iters) {
69 int i = 0;
70 char *mphf_name;
71 cmph_t* mphf = NULL;
72
73 mphf_name = create_lsmap_key(algo, iters);
74 mphf = (cmph_t*)lsmap_search(g_created_mphf, mphf_name);
75 free(mphf_name);
76
77 cmph_uint32* count = (cmph_uint32*)malloc(sizeof(cmph_uint32)*iters);
78 cmph_uint32* hash_count = (cmph_uint32*)malloc(sizeof(cmph_uint32)*iters);
79
80 for (i = 0; i < iters * 100; ++i) {
81 cmph_uint32 pos = random() % iters;
82 const char* buf = (const char*)(g_numbers + pos);
83 cmph_uint32 h = cmph_search(mphf, buf, sizeof(cmph_uint32));
84 ++count[pos];
85 ++hash_count[h];
86 }
87
88 // Verify correctness later.
89 lsmap_append(g_expected_probes, create_lsmap_key(algo, iters), count);
90 lsmap_append(g_mphf_probes, create_lsmap_key(algo, iters), hash_count);
91 }
92
verify()93 void verify() { }
94
95 #define DECLARE_ALGO(algo) \
96 void bm_create_ ## algo(int iters) { bm_create(algo, iters); } \
97 void bm_search_ ## algo(int iters) { bm_search(algo, iters); }
98
99 DECLARE_ALGO(CMPH_BMZ);
100 DECLARE_ALGO(CMPH_CHM);
101 DECLARE_ALGO(CMPH_BRZ);
102 DECLARE_ALGO(CMPH_FCH);
103 DECLARE_ALGO(CMPH_BDZ);
104
main(int argc,char ** argv)105 int main(int argc, char** argv) {
106 g_numbers_len = 1000 * 1000;
107 g_numbers = random_numbers_vector_new(g_numbers_len);
108 g_created_mphf = lsmap_new();
109 g_expected_probes = lsmap_new();
110 g_mphf_probes = lsmap_new();
111
112 BM_REGISTER(bm_create_CMPH_BMZ, 1000 * 1000);
113 BM_REGISTER(bm_search_CMPH_BMZ, 1000 * 1000);
114 BM_REGISTER(bm_create_CMPH_CHM, 1000 * 1000);
115 BM_REGISTER(bm_search_CMPH_CHM, 1000 * 1000);
116 // BM_REGISTER(bm_create_CMPH_BRZ, 1000 * 1000);
117 // BM_REGISTER(bm_search_CMPH_BRZ, 1000 * 1000);
118 // BM_REGISTER(bm_create_CMPH_FCH, 1000 * 1000);
119 // BM_REGISTER(bm_search_CMPH_FCH, 1000 * 1000);
120 BM_REGISTER(bm_create_CMPH_BDZ, 1000 * 1000);
121 BM_REGISTER(bm_search_CMPH_BDZ, 1000 * 1000);
122 run_benchmarks(argc, argv);
123
124 verify();
125 free(g_numbers);
126 lsmap_foreach_key(g_created_mphf, (void(*)(const char*))free);
127 lsmap_foreach_value(g_created_mphf, (void(*)(void*))cmph_destroy);
128 lsmap_destroy(g_created_mphf);
129 return 0;
130 }
131