rankselect/bitmap_bench_sdsl.cc at master · splatlab/rankselect · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
/* -*- Mode: C++; c-basic-offset: 4; indent-tabs-mode: nil -*- */

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#define __STDC_LIMIT_MACROS
#include <stdint.h>
#include <unistd.h>
#include <sys/time.h>

#include "rank_support.hpp"
#include "select_support_scan.hpp"
#include "select_support_mcl.hpp"
#include "bitmap.h"
#include "shared.h"

using namespace sdsl;

double densityL = 0.1;
double densityR = 0.1;

uint64 numOnesL = 0;
uint64 numOnesR = 0;

const int numIters = 10;
const int numQueries = 10000000;
uint64 queries[numQueries];
uint64 indices[numQueries];
uint64 queries64[numQueries];

uint32 seed = 1;

inline uint32 xRand()
{
	return seed = (279470273ULL * seed) % 4294967291ULL;
}

inline uint64 xRand64()
{
	return (uint64) xRand() << 32 | xRand();
}

void intVectorRandomBit(uint64 nbits, bit_vector &vector,  uint32 thresholdL, uint32 thresholdR)
{
	fprintf(stderr, "nbits to create: %" PRIu64 "\n", nbits);
	fprintf(stderr, "allocated bits: %" PRIu64 " bytes\n", nbits/8);

	for (uint64 i = 0; i < nbits / 2; i++) {
		if (xRand() < thresholdL) {
			uint64 val = vector.get_int(i / 64, 64);
			val |= 1ul << (i % 64);
			vector.set_int(i / 64, val, 64);
			++numOnesL;
		} else {
			uint64 val = vector.get_int(i / 64, 64);
			val &= ~(1ull << (i % 64));
			vector.set_int(i / 64, val, 64);
		}
	}
	for (uint64 i = nbits / 2; i < nbits; i++) {
		if (xRand() < thresholdR) {
			uint64 val = vector.get_int(i / 64, 64);
			val |= 1ull << (i % 64);
			vector.set_int(i / 64, val, 64);
			++numOnesR;
		} else {
			uint64 val = vector.get_int(i / 64, 64);
			val &= ~(1ull << (i % 64));
			vector.set_int(i / 64, val, 64);
		}
	}
}

enum benchmode {
	BENCH_RANK,
	BENCH_SELECT,
};

int main(int argc, char **argv)
{
	extern int optind;
	int ch;

	uint64 nbits;
	benchmode mode = BENCH_RANK;

	while ((ch = getopt(argc, argv, "sn:d:")) != -1) {
		switch (ch) {
			case 's':
				mode = BENCH_SELECT;
				break;
			case 'n':
				nbits = atoi(optarg);
				nbits = 1ULL << nbits;
				break;
			case 'd':
				densityL = densityR = atof(optarg);
				break;
		}
	}

	printf("benchmode: %s\n", mode == BENCH_RANK ? "rank" : "select");

	uint32 thresholdL = (uint32) (UINT32_MAX * densityL);
	uint32 thresholdR = (uint32) (UINT32_MAX * densityR);
	uint64 numWords = (nbits + 63)/64;

	bit_vector vector(nbits, 0, 1);
	intVectorRandomBit(nbits, vector, thresholdL, thresholdR);
	uint64 cnt = rank_support_v<0>(&vector)(vector.size());
	bit_vector::select_0_type bit_select(&vector);

	uint64 dummy = 0x1234567890ABCDEF;

	if (mode == BENCH_RANK) {
		for (int i = 0; i < numQueries; i++) {
			queries[i] = xRand64() % nbits + 1;
		}
	} else {
		assert(mode == BENCH_SELECT);

		for (int i = 0; i < numQueries / 2; i++) {
			queries[i] = ((xRand64() % numOnesL + 1) % (cnt - 1)) + 1;
		}
		for (int i = numQueries / 2; i < numQueries; i++) {
			queries[i] = ((xRand64() % numOnesR + 1 + numOnesL) % (cnt - 1)) + 1;
		}
	}

	struct timeval tv_start, tv_end;
	double elapsed_seconds;

	gettimeofday(&tv_start, NULL);
	assert(mode == BENCH_SELECT);

	for (int iter = 0; iter < numIters; iter++)
		for (int i = 0; i < numQueries; i++)
			dummy ^= bit_select(queries[i]);
	gettimeofday(&tv_end, NULL);
	elapsed_seconds = timeval_diff(&tv_start, &tv_end);
	printf("%" PRIu64 " ops, %.2f seconds, ns/op: %.2f\n",
				 (uint64) numIters * numQueries,
				 elapsed_seconds,
				 elapsed_seconds * 1000000000 / ((uint64) numIters * numQueries));

	if (dummy == 42) printf("42\n");

	return 0;
}