SortedListIntersection/main.cpp at main · ralgond/SortedListIntersection · 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
#include <fstream>
#include <string>
#include <iostream>
#include <cstdlib>
#include <string>
#include <stdint.h>
#include "utils.h"

#include "sorted_int_file_reader.h"

#include "algo_intersection.h"

using namespace std;

float qps(int N, long ms) {
	return N*1.0/(ms*1.0/1000);
}

int main(int argc, char* argv[]) {

	string file1 = argv[1];
	string file2 = argv[2];

	uint32_t a_len = 0;
	uint32_t* a = read_sorted_int_from_file(file1, &a_len);
	cout<<"file "<<file1<<": "<<a_len<<endl;

	uint32_t b_len = 0;
	uint32_t* b = read_sorted_int_from_file(file2, &b_len);
	cout<<"file "<<file2<<": "<<b_len<<endl;


	uint32_t rareLen = 0;
	uint32_t* rare = NULL;
	uint32_t freqLen = 0;
	uint32_t* freq = NULL;

	if (a_len < b_len) {
		rareLen = a_len;
		rare = a;
		freqLen = b_len;
		freq = b;
	} else {
		rareLen = b_len;
		rare = b;
		freqLen = a_len;
		freq = a;
	}


	uint32_t* c = new uint32_t[rareLen];

	uint32_t cnt = 0;

	bloom_filter* filter = create_bloom_filter(freq, freqLen);

	long time1, time2;

	int N = 10000;


	time1 = currentTimeMs();
	for (int i = 0; i < 10000; i++)
		cnt = v1_avx2_intersection(freq, freqLen, rare, rareLen, c);
	time2 = currentTimeMs();
	cout << "v1_avx2\t" << (time2-time1) << "ms"<<"\t"<<qps(N, (time2-time1))<<"\t"<<cnt<<endl;

	time1 = currentTimeMs();
	for (int i = 0; i < 10000; i++)
		cnt = v3_avx2_intersection(freq, freqLen, rare, rareLen, c);
	time2 = currentTimeMs();
	cout << "v3_avx2\t" << (time2-time1) << "ms"<<"\t"<<qps(N, (time2-time1))<<"\t"<<cnt<<endl;

	time1 = currentTimeMs();
	for (int i = 0; i < 10000; i++)
		cnt = highlyscalable_SIMD_intersection(freq, freqLen, rare, rareLen, c);
	time2 = currentTimeMs();
	cout << "highlyscalable_SIMD\t" << (time2-time1) << "ms"<<"\t"<<qps(N, (time2-time1))<<"\t"<<cnt<<endl;

	prepare_shuffling_dict32();
	time1 = currentTimeMs();
	for (int i = 0; i < 10000; i++)
		cnt = highlyscalable_avx2_intersection(freq, freqLen, rare, rareLen, c);
	time2 = currentTimeMs();
	cout << "highlyscalable_avx2\t" << (time2-time1) << "ms"<<"\t"<<qps(N, (time2-time1))<<"\t"<<cnt<<endl;

	prepare_shuffling_dict64();
	time1 = currentTimeMs();
	for (int i = 0; i < 10000; i++)
		cnt = highlyscalable_avx512_intersection(freq, freqLen, rare, rareLen, c);
	time2 = currentTimeMs();
	cout << "highlyscalable_avx512\t" << (time2-time1) << "ms"<<"\t"<<qps(N, (time2-time1))<<"\t"<<cnt<<endl;


	time1 = currentTimeMs();
	for (int i = 0; i < 10000; i++)
		cnt = lemire_highlyscalable_SIMD_intersection(freq, freqLen, rare, rareLen, c);
	time2 = currentTimeMs();
	cout << "lemire_highlyscalable_SIMD\t" << (time2-time1) << "ms"<<"\t"<<qps(N, (time2-time1))<<"\t"<<cnt<<endl;

	time1 = currentTimeMs();
	for (int i = 0; i < 10000; i++)
		cnt = scalar(freq, freqLen, rare, rareLen, c);
	time2 = currentTimeMs();
	cout << "scalar\t" << (time2-time1) << "ms"<<"\t"<<qps(N, (time2-time1))<<"\t"<<cnt<<endl;

	time1 = currentTimeMs();
	for (int i = 0; i < 10000; i++)
		cnt = block_merge_intersection(freq, freqLen, rare, rareLen, c);
	time2 = currentTimeMs();
	cout << "block_merge\t" << (time2-time1) << "ms"<<"\t"<<qps(N, (time2-time1))<<"\t"<<cnt<<endl;

//	time1 = currentTimeMs();
//	for (int i = 0; i < 10000; i++)
//		cnt = bisearch_intersection(freq, freqLen, rare, rareLen, c);
//	time2 = currentTimeMs();
//	cout << "bisearch\t" << (time2-time1) << "ms"<<"\t"<<qps(N, (time2-time1))<<"\t"<<cnt<<endl;

//	time1 = currentTimeMs();
//	for (int i = 0; i < 10000; i++)
//		cnt = bloomfilter_intersection(filter, freq, freqLen, rare, rareLen, c);
//	time2 = currentTimeMs();
//	cout << "bloom\t" << (time2-time1) << "ms"<<"\t"<<qps(N, (time2-time1))<<"\t"<<cnt<<endl;
label1:
	prepare_shuffling_dict16();
	PrefixList* rarePl = buildPrefixList(rare, rareLen);
	PrefixList* freqPl = buildPrefixList(freq, freqLen);

	time1 = currentTimeMs();
	for (int i = 0; i < 10000; i++)
		cnt = intersectPrefixList(freqPl, rarePl, c);
	time2 = currentTimeMs();
	cout << "sttni\t" << (time2-time1) << "ms"<<"\t"<<qps(N, (time2-time1))<<"\t"<<cnt<<endl;

	//for (uint32_t i = 0; i < cnt; i++) {
	//	cout<<c[i]<<endl;
	//}

	return 0;
}