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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
|
// Copyright Vespa.ai. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
#include <vespa/vespalib/testkit/test_kit.h>
#include "../weak_and/rise_wand.h"
#include "../weak_and/rise_wand.hpp"
#include <vespa/searchlib/fef/matchdatalayout.h>
#include <vespa/searchlib/fef/termfieldmatchdata.h>
#include <vespa/searchlib/fef/termfieldmatchdataarray.h>
#include <vespa/searchlib/queryeval/andnotsearch.h>
#include <vespa/searchlib/queryeval/andsearch.h>
#include <vespa/searchlib/queryeval/dot_product_search.h>
#include <vespa/searchlib/queryeval/orsearch.h>
#include <vespa/searchlib/queryeval/simpleresult.h>
#include <vespa/searchlib/queryeval/wand/weak_and_search.h>
#include <vespa/searchlib/queryeval/weighted_set_term_search.h>
#include <vespa/vespalib/util/box.h>
#include <vespa/vespalib/util/stringfmt.h>
using namespace search::fef;
using namespace search::queryeval;
using namespace vespalib;
namespace {
//-----------------------------------------------------------------------------
struct Writer {
FILE *file;
explicit Writer(const std::string &file_name) {
file = fopen(file_name.c_str(), "w");
assert(file != nullptr);
}
void write(const char *data, size_t size) const {
fwrite(data, 1, size, file);
}
void fmt(const char *format, ...) const __attribute__ ((format (printf,2,3)))
{
va_list ap;
va_start(ap, format);
vfprintf(file, format, ap);
va_end(ap);
}
~Writer() { fclose(file); }
};
//-----------------------------------------------------------------------------
// top-level html report (global, used by plots and graphs directly)
class Report
{
private:
Writer _html;
public:
explicit Report(const std::string &file) : _html(file) {
_html.fmt("<html>\n");
_html.fmt("<head><title>Sparse Vector Search Benchmark Report</title></head>\n");
_html.fmt("<body>\n");
_html.fmt("<h1>Sparse Vector Search Benchmark Report</h1>\n");
}
void addPlot(const std::string &title, const std::string &png_file) {
_html.fmt("<h3>%s</h3>\n", title.c_str());
_html.fmt("<img src=\"%s\">\n", png_file.c_str());
}
~Report() {
_html.fmt("<h2>Test Log with Numbers</h2>\n");
_html.fmt("<pre>\n");
// html file needs external termination
}
};
Report report("report.head");
//-----------------------------------------------------------------------------
// a single graph within a plot
class Graph
{
private:
Writer _writer;
public:
using UP = std::unique_ptr<Graph>;
explicit Graph(const std::string &file) : _writer(file) {}
void addValue(double x, double y) { _writer.fmt("%g %g\n", x, y); }
};
// a plot possibly containing multiple graphs
class Plot
{
private:
std::string _name;
int _graphs;
Writer _writer;
static int _plots;
public:
using UP = std::unique_ptr<Plot>;
explicit Plot(const std::string &title)
: _name(vespalib::make_string("plot.%d", _plots++)), _graphs(0),
_writer(vespalib::make_string("%s.gnuplot", _name.c_str()))
{
std::string png_file = vespalib::make_string("%s.png", _name.c_str());
_writer.fmt("set term png size 1200,800\n");
_writer.fmt("set output '%s'\n", png_file.c_str());
_writer.fmt("set title '%s'\n", title.c_str());
_writer.fmt("set xlabel 'term count'\n");
_writer.fmt("set ylabel 'time (ms)'\n");
report.addPlot(title, png_file);
}
~Plot() {
_writer.fmt("\n");
}
Graph::UP createGraph(const std::string &legend) {
std::string file = vespalib::make_string("%s.graph.%d", _name.c_str(), _graphs);
_writer.fmt("%s '%s' using 1:2 title '%s' w lines",
(_graphs == 0) ? "plot " : ",", file.c_str(), legend.c_str());
++_graphs;
return std::make_unique<Graph>(file);
}
static UP createPlot(const std::string &title) { return std::make_unique<Plot>(title); }
};
int Plot::_plots = 0;
//-----------------------------------------------------------------------------
constexpr uint32_t default_weight = 100;
constexpr vespalib::duration max_time = 1000s;
//-----------------------------------------------------------------------------
struct ChildFactory {
ChildFactory() {}
virtual std::string name() const = 0;
virtual SearchIterator::UP createChild(uint32_t idx, uint32_t limit) const = 0;
virtual ~ChildFactory() = default;
};
struct SparseVectorFactory {
virtual std::string name() const = 0;
virtual SearchIterator::UP createSparseVector(ChildFactory &childFactory, uint32_t childCnt, uint32_t limit) const = 0;
virtual ~SparseVectorFactory() = default;
};
struct FilterStrategy {
virtual std::string name() const = 0;
virtual SearchIterator::UP createRoot(SparseVectorFactory &vectorFactory, ChildFactory &childFactory, uint32_t childCnt, uint32_t limit) const = 0;
virtual ~FilterStrategy() = default;
};
//-----------------------------------------------------------------------------
struct ModSearch : SearchIterator {
uint32_t step;
uint32_t limit;
ModSearch(uint32_t step_in, uint32_t limit_in) : step(step_in), limit(limit_in) { setDocId(step); }
void doSeek(uint32_t docid) override {
assert(docid > getDocId());
uint32_t hit = (docid / step) * step;
if (hit < docid) {
hit += step;
}
if (hit < limit) {
assert(hit >= docid);
setDocId(hit);
} else {
setAtEnd();
}
}
void doUnpack(uint32_t) override {}
};
struct ModSearchFactory : ChildFactory {
uint32_t bias;
ModSearchFactory() : bias(1) {}
explicit ModSearchFactory(int b) : bias(b) {}
std::string name() const override {
return vespalib::make_string("ModSearch(%u)", bias);
}
SearchIterator::UP createChild(uint32_t idx, uint32_t limit) const override {
return SearchIterator::UP(new ModSearch(bias + idx, limit));
}
};
//-----------------------------------------------------------------------------
struct VespaWandFactory : SparseVectorFactory {
uint32_t n;
explicit VespaWandFactory(uint32_t n_in) noexcept : n(n_in) {}
std::string name() const override {
return vespalib::make_string("VespaWand(%u)", n);
}
SearchIterator::UP createSparseVector(ChildFactory &childFactory, uint32_t childCnt, uint32_t limit) const override {
wand::Terms terms;
for (size_t i = 0; i < childCnt; ++i) {
terms.emplace_back(childFactory.createChild(i, limit), default_weight, limit / (i + 1));
}
return WeakAndSearch::create(terms, n, true);
}
};
struct RiseWandFactory : SparseVectorFactory {
uint32_t n;
explicit RiseWandFactory(uint32_t n_in) : n(n_in) {}
std::string name() const override {
return vespalib::make_string("RiseWand(%u)", n);
}
SearchIterator::UP createSparseVector(ChildFactory &childFactory, uint32_t childCnt, uint32_t limit) const override {
wand::Terms terms;
for (size_t i = 0; i < childCnt; ++i) {
terms.emplace_back(childFactory.createChild(i, limit), default_weight, limit / (i + 1));
}
return std::make_unique<rise::TermFrequencyRiseWand>(terms, n);
}
};
struct WeightedSetFactory : SparseVectorFactory {
mutable TermFieldMatchData tfmd;
bool field_is_filter;
WeightedSetFactory(bool field_is_filter_, bool term_is_not_needed)
: tfmd(),
field_is_filter(field_is_filter_)
{
if (term_is_not_needed) {
tfmd.tagAsNotNeeded();
}
}
std::string name() const override {
return vespalib::make_string("WeightedSet%s%s", (field_is_filter ? "-filter" : ""), (tfmd.isNotNeeded() ? "-unranked" : ""));
}
SearchIterator::UP createSparseVector(ChildFactory &childFactory, uint32_t childCnt, uint32_t limit) const override {
std::vector<SearchIterator *> terms;
std::vector<int32_t> weights;
for (size_t i = 0; i < childCnt; ++i) {
// TODO: pass ownership with unique_ptr
terms.push_back(childFactory.createChild(i, limit).release());
weights.push_back(default_weight);
}
return WeightedSetTermSearch::create(terms, tfmd, field_is_filter, weights, MatchData::UP(nullptr));
}
};
struct DotProductFactory : SparseVectorFactory {
mutable TermFieldMatchData tfmd;
bool field_is_filter;
DotProductFactory(bool field_is_filter_, bool term_is_not_needed)
: tfmd(),
field_is_filter(field_is_filter_)
{
if (term_is_not_needed) {
tfmd.tagAsNotNeeded();
}
}
std::string name() const override {
return vespalib::make_string("DotProduct%s%s", (field_is_filter ? "-filter" : ""), (tfmd.isNotNeeded() ? "-unranked" : ""));
}
SearchIterator::UP createSparseVector(ChildFactory &childFactory, uint32_t childCnt, uint32_t limit) const override {
MatchDataLayout layout;
std::vector<TermFieldHandle> handles;
for (size_t i = 0; i < childCnt; ++i) {
handles.push_back(layout.allocTermField(0));
}
std::vector<SearchIterator *> terms;
std::vector<TermFieldMatchData*> childMatch;
std::vector<int32_t> weights;
MatchData::UP md = layout.createMatchData();
for (size_t i = 0; i < childCnt; ++i) {
terms.push_back(childFactory.createChild(i, limit).release());
childMatch.push_back(md->resolveTermField(handles[i]));
weights.push_back(default_weight);
}
return DotProductSearch::create(terms, tfmd, field_is_filter, childMatch, weights, std::move(md));
}
};
struct OrFactory : SparseVectorFactory {
std::string name() const override {
return vespalib::make_string("Or");
}
SearchIterator::UP createSparseVector(ChildFactory &childFactory, uint32_t childCnt, uint32_t limit) const override {
OrSearch::Children children;
for (size_t i = 0; i < childCnt; ++i) {
children.push_back(childFactory.createChild(i, limit));
}
return OrSearch::create(std::move(children), true);
}
};
//-----------------------------------------------------------------------------
struct NoFilterStrategy : FilterStrategy {
std::string name() const override {
return vespalib::make_string("NoFilter");
}
SearchIterator::UP createRoot(SparseVectorFactory &vectorFactory, ChildFactory &childFactory, uint32_t childCnt, uint32_t limit) const override {
return vectorFactory.createSparseVector(childFactory, childCnt, limit);
}
};
struct PositiveFilterBeforeStrategy : FilterStrategy {
virtual std::string name() const override {
return vespalib::make_string("PositiveBefore");
}
SearchIterator::UP createRoot(SparseVectorFactory &vectorFactory, ChildFactory &childFactory, uint32_t childCnt, uint32_t limit) const override {
AndSearch::Children children;
children.emplace_back(new ModSearch(2, limit)); // <- 50% hits (hardcoded)
children.push_back(vectorFactory.createSparseVector(childFactory, childCnt, limit));
return AndSearch::create(std::move(children), true);
}
};
struct NegativeFilterAfterStrategy : FilterStrategy {
virtual std::string name() const override {
return vespalib::make_string("NegativeAfter");
}
SearchIterator::UP createRoot(SparseVectorFactory &vectorFactory, ChildFactory &childFactory, uint32_t childCnt, uint32_t limit) const override {
AndNotSearch::Children children;
children.push_back(vectorFactory.createSparseVector(childFactory, childCnt, limit));
children.emplace_back(new ModSearch(2, limit)); // <- 50% hits (hardcoded)
return AndNotSearch::create(std::move(children), true);
}
};
//-----------------------------------------------------------------------------
struct Result {
vespalib::duration time;
uint32_t num_hits;
Result() noexcept : time(max_time), num_hits(0) {}
Result(vespalib::duration t, uint32_t n) noexcept : time(t), num_hits(n) {}
void combine(const Result &r) {
if (time == max_time) {
*this = r;
} else {
assert(num_hits == r.num_hits);
time = std::min(time, r.time);
}
}
std::string toString() const {
return vespalib::make_string("%u hits, %" PRId64 " ms", num_hits, vespalib::count_ms(time));
}
};
Result run_single_benchmark(FilterStrategy &filterStrategy, SparseVectorFactory &vectorFactory, ChildFactory &childFactory, uint32_t childCnt, uint32_t limit) {
SearchIterator::UP search(filterStrategy.createRoot(vectorFactory, childFactory, childCnt, limit));
SearchIterator &sb = *search;
sb.initFullRange();
uint32_t num_hits = 0;
vespalib::Timer timer;
for (sb.seek(1); !sb.isAtEnd(); sb.seek(sb.getDocId() + 1)) {
++num_hits;
sb.unpack(sb.getDocId());
}
return {timer.elapsed(), num_hits};
}
//-----------------------------------------------------------------------------
// one setup is used to produce all graphs in a single plot
class Setup
{
private:
FilterStrategy &_filterStrategy;
ChildFactory &_childFactory;
uint32_t _limit;
Plot::UP _plot;
std::string make_title() const {
return vespalib::make_string("%u docs, filter:%s, terms:%s", _limit, _filterStrategy.name().c_str(), _childFactory.name().c_str());
}
public:
Setup(FilterStrategy &fs, ChildFactory &cf, uint32_t lim) : _filterStrategy(fs), _childFactory(cf), _limit(lim) {
_plot = Plot::createPlot(make_title());
fprintf(stderr, "benchmark setup: %s\n", make_title().c_str());
}
void benchmark(SparseVectorFactory &svf, const std::vector<uint32_t> &child_counts) {
Graph::UP graph = _plot->createGraph(svf.name());
fprintf(stderr, " search operator: %s\n", svf.name().c_str());
for (unsigned int childCnt : child_counts) {
Result result;
for (int j = 0; j < 5; ++j) {
result.combine(run_single_benchmark(_filterStrategy, svf, _childFactory, childCnt, _limit));
}
graph->addValue(childCnt, vespalib::count_ms(result.time));
fprintf(stderr, " %u children => %s\n", childCnt, result.toString().c_str());
}
}
};
//-----------------------------------------------------------------------------
void benchmark_all_operators(Setup &setup, const std::vector<uint32_t> &child_counts) {
VespaWandFactory vespaWand256(256);
RiseWandFactory riseWand256(256);
WeightedSetFactory weightedSet(false, false);
WeightedSetFactory weightedSet_filter(true, false);
WeightedSetFactory weightedSet_unranked(false, true);
DotProductFactory dotProduct(false, false);
DotProductFactory dotProduct_filter(true, false);
DotProductFactory dotProduct_unranked(false, true);
OrFactory plain_or;
setup.benchmark(vespaWand256, child_counts);
setup.benchmark(riseWand256, child_counts);
setup.benchmark(weightedSet, child_counts);
setup.benchmark(weightedSet_filter, child_counts);
setup.benchmark(weightedSet_unranked, child_counts);
setup.benchmark(dotProduct, child_counts);
setup.benchmark(dotProduct_filter, child_counts);
setup.benchmark(dotProduct_unranked, child_counts);
setup.benchmark(plain_or, child_counts);
}
//-----------------------------------------------------------------------------
Box<uint32_t> make_full_child_counts() {
return Box<uint32_t>()
.add(10).add(20).add(30).add(40).add(50).add(60).add(70).add(80).add(90)
.add(100).add(125).add(150).add(175)
.add(200).add(250).add(300).add(350).add(400).add(450)
.add(500).add(600).add(700).add(800).add(900)
.add(1000).add(1200).add(1400).add(1600).add(1800)
.add(2000);
}
//-----------------------------------------------------------------------------
} // namespace <unnamed>
TEST_FFF("benchmark", NoFilterStrategy(), ModSearchFactory(), Setup(f1, f2, 5000000)) {
benchmark_all_operators(f3, make_full_child_counts());
}
TEST_FFF("benchmark", NoFilterStrategy(), ModSearchFactory(8), Setup(f1, f2, 5000000)) {
benchmark_all_operators(f3, make_full_child_counts());
}
TEST_FFF("benchmark", PositiveFilterBeforeStrategy(), ModSearchFactory(), Setup(f1, f2, 5000000)) {
benchmark_all_operators(f3, make_full_child_counts());
}
TEST_FFF("benchmark", NegativeFilterAfterStrategy(), ModSearchFactory(), Setup(f1, f2, 5000000)) {
benchmark_all_operators(f3, make_full_child_counts());
}
TEST_MAIN() { TEST_RUN_ALL(); }
|
