Skip to content

Commit 6978a0b

Browse files
jkeiserlemire
jkeiser
authored and
lemire
committed
Benchmark escapes (simdjson#464)
* Add escapes as a feature we benchmark * Don't print effectiveness metric unless verbose is on
1 parent 6784530 commit 6978a0b

4 files changed

Lines changed: 104 additions & 44 deletions

File tree

‎Makefile‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -77,7 +77,7 @@ LIBFILES=src/jsonioutil.cpp src/jsonparser.cpp src/jsonstream.cpp src/simdjson.c
7777
MINIFIERHEADERS=include/simdjson/jsonminifier.h
7878
MINIFIERLIBFILES=src/jsonminifier.cpp
7979

80-
FEATURE_JSON_FILES=jsonexamples/generated/0-structurals-full.json jsonexamples/generated/15-structurals-miss.json jsonexamples/generated/7-structurals.json jsonexamples/generated/0-structurals.json jsonexamples/generated/23-structurals-full.json jsonexamples/generated/7-structurals-miss.json jsonexamples/generated/0-structurals-miss.json jsonexamples/generated/23-structurals.json jsonexamples/generated/utf-8-full.json jsonexamples/generated/15-structurals-full.json jsonexamples/generated/23-structurals-miss.json jsonexamples/generated/utf-8.json jsonexamples/generated/15-structurals.json jsonexamples/generated/7-structurals-full.json jsonexamples/generated/utf-8-miss.json
80+
FEATURE_JSON_FILES=jsonexamples/generated/0-structurals-full.json jsonexamples/generated/0-structurals-miss.json jsonexamples/generated/0-structurals.json jsonexamples/generated/15-structurals-full.json jsonexamples/generated/15-structurals-miss.json jsonexamples/generated/15-structurals.json jsonexamples/generated/23-structurals-full.json jsonexamples/generated/23-structurals-miss.json jsonexamples/generated/23-structurals.json jsonexamples/generated/7-structurals-full.json jsonexamples/generated/7-structurals-miss.json jsonexamples/generated/7-structurals.json jsonexamples/generated/escape-full.json jsonexamples/generated/escape-miss.json jsonexamples/generated/escape.json jsonexamples/generated/utf-8-full.json jsonexamples/generated/utf-8-miss.json jsonexamples/generated/utf-8.json
8181

8282
RAPIDJSON_INCLUDE:=dependencies/rapidjson/include
8383
SAJSON_INCLUDE:=dependencies/sajson/include

‎benchmark/benchfeatures.cpp‎

Lines changed: 70 additions & 38 deletions
Original file line numberDiff line numberDiff line change
@@ -148,6 +148,8 @@ struct option_struct {
148148
struct feature_benchmarker {
149149
benchmarker utf8;
150150
benchmarker utf8_miss;
151+
benchmarker escape;
152+
benchmarker escape_miss;
151153
benchmarker empty;
152154
benchmarker empty_miss;
153155
benchmarker struct7;
@@ -161,6 +163,8 @@ struct feature_benchmarker {
161163
feature_benchmarker(json_parser& parser, event_collector& collector) :
162164
utf8 ("jsonexamples/generated/utf-8.json", parser, collector),
163165
utf8_miss ("jsonexamples/generated/utf-8-miss.json", parser, collector),
166+
escape ("jsonexamples/generated/escape.json", parser, collector),
167+
escape_miss ("jsonexamples/generated/escape-miss.json", parser, collector),
164168
empty ("jsonexamples/generated/0-structurals.json", parser, collector),
165169
empty_miss ("jsonexamples/generated/0-structurals-miss.json", parser, collector),
166170
struct7 ("jsonexamples/generated/7-structurals.json", parser, collector),
@@ -180,6 +184,8 @@ struct feature_benchmarker {
180184
struct7_full.run_iterations(iterations, stage1_only);
181185
utf8.run_iterations(iterations, stage1_only);
182186
utf8_miss.run_iterations(iterations, stage1_only);
187+
escape.run_iterations(iterations, stage1_only);
188+
escape_miss.run_iterations(iterations, stage1_only);
183189
empty.run_iterations(iterations, stage1_only);
184190
empty_miss.run_iterations(iterations, stage1_only);
185191
struct15.run_iterations(iterations, stage1_only);
@@ -258,12 +264,27 @@ struct feature_benchmarker {
258264
return double(utf8_miss[stage].best.branch_misses() - utf8[stage].best.branch_misses()) / utf8_miss.stats->blocks_with_utf8_flipped;
259265
}
260266

267+
// Extra cost of having escapes in a block
268+
double escape_cost(BenchmarkStage stage) const {
269+
return cost_per_block(stage, escape, escape.stats->blocks_with_escapes, struct7_full);
270+
}
271+
// Extra cost of an escape miss
272+
double escape_miss_cost(BenchmarkStage stage) const {
273+
return cost_per_block(stage, escape_miss, escape_miss.stats->blocks_with_escapes_flipped, escape);
274+
}
275+
// Rate of escape misses per escape flip
276+
double escape_miss_rate(BenchmarkStage stage) const {
277+
if (!has_events()) { return 1; }
278+
return double(escape_miss[stage].best.branch_misses() - escape[stage].best.branch_misses()) / escape_miss.stats->blocks_with_escapes_flipped;
279+
}
280+
261281
double calc_expected_feature_cost(BenchmarkStage stage, const benchmarker& file) const {
262282
// Expected base ns/block (empty)
263283
json_stats& stats = *file.stats;
264284
double expected = base_cost(stage) * stats.blocks;
265285
expected += struct1_7_cost(stage) * stats.blocks_with_1_structural;
266286
expected += utf8_cost(stage) * stats.blocks_with_utf8;
287+
expected += escape_cost(stage) * stats.blocks_with_escapes;
267288
expected += struct8_15_cost(stage) * stats.blocks_with_8_structurals;
268289
expected += struct16_cost(stage) * stats.blocks_with_16_structurals;
269290
return expected / stats.blocks;
@@ -274,6 +295,7 @@ struct feature_benchmarker {
274295
json_stats& stats = *file.stats;
275296
double expected = struct1_7_miss_cost(stage) * stats.blocks_with_1_structural_flipped * struct1_7_miss_rate(stage);
276297
expected += utf8_miss_cost(stage) * stats.blocks_with_utf8_flipped * utf8_miss_rate(stage);
298+
expected += escape_miss_cost(stage) * stats.blocks_with_escapes_flipped * escape_miss_rate(stage);
277299
expected += struct8_15_miss_cost(stage) * stats.blocks_with_8_structurals_flipped * struct8_15_miss_rate(stage);
278300
expected += struct16_miss_cost(stage) * stats.blocks_with_16_structurals_flipped * struct16_miss_rate(stage);
279301
return expected / stats.blocks;
@@ -283,6 +305,7 @@ struct feature_benchmarker {
283305
json_stats& stats = *file.stats;
284306
double expected = stats.blocks_with_1_structural_flipped * struct1_7_miss_rate(stage);
285307
expected += stats.blocks_with_utf8_flipped * utf8_miss_rate(stage);
308+
expected += stats.blocks_with_escapes_flipped * escape_miss_rate(stage);
286309
expected += stats.blocks_with_8_structurals_flipped * struct8_15_miss_rate(stage);
287310
expected += stats.blocks_with_16_structurals_flipped * struct16_miss_rate(stage);
288311
return expected;
@@ -300,10 +323,12 @@ struct feature_benchmarker {
300323
printf("| %8s ", "Base");
301324
printf("| %8s ", "7 Struct");
302325
printf("| %8s ", "UTF-8");
326+
printf("| %8s ", "Escape");
303327
printf("| %8s ", "15 Str.");
304328
printf("| %8s ", "16+ Str.");
305329
printf("| %15s ", "7 Struct Miss");
306330
printf("| %15s ", "UTF-8 Miss");
331+
printf("| %15s ", "Escape Miss");
307332
printf("| %15s ", "15 Str. Miss");
308333
printf("| %15s ", "16+ Str. Miss");
309334
printf("|\n");
@@ -314,6 +339,8 @@ struct feature_benchmarker {
314339
printf("|%.10s", "---------------------------------------");
315340
printf("|%.10s", "---------------------------------------");
316341
printf("|%.10s", "---------------------------------------");
342+
printf("|%.10s", "---------------------------------------");
343+
printf("|%.17s", "---------------------------------------");
317344
printf("|%.17s", "---------------------------------------");
318345
printf("|%.17s", "---------------------------------------");
319346
printf("|%.17s", "---------------------------------------");
@@ -325,16 +352,19 @@ struct feature_benchmarker {
325352
printf("| %8.3g ", base_cost(stage));
326353
printf("| %8.3g ", struct1_7_cost(stage));
327354
printf("| %8.3g ", utf8_cost(stage));
355+
printf("| %8.3g ", escape_cost(stage));
328356
printf("| %8.3g ", struct8_15_cost(stage));
329357
printf("| %8.3g ", struct16_cost(stage));
330358
if (has_events()) {
331359
printf("| %8.3g (%3d%%) ", struct1_7_miss_cost(stage), int(struct1_7_miss_rate(stage)*100));
332360
printf("| %8.3g (%3d%%) ", utf8_miss_cost(stage), int(utf8_miss_rate(stage)*100));
361+
printf("| %8.3g (%3d%%) ", escape_miss_cost(stage), int(escape_miss_rate(stage)*100));
333362
printf("| %8.3g (%3d%%) ", struct8_15_miss_cost(stage), int(struct8_15_miss_rate(stage)*100));
334363
printf("| %8.3g (%3d%%) ", struct16_miss_cost(stage), int(struct16_miss_rate(stage)*100));
335364
} else {
336365
printf("| %8.3g ", struct1_7_miss_cost(stage));
337366
printf("| %8.3g ", utf8_miss_cost(stage));
367+
printf("| %8.3g ", escape_miss_cost(stage));
338368
printf("| %8.3g ", struct8_15_miss_cost(stage));
339369
printf("| %8.3g ", struct16_miss_cost(stage));
340370
}
@@ -349,7 +379,7 @@ void print_file_effectiveness(BenchmarkStage stage, const char* filename, const
349379
uint64_t actual_misses = results[stage].best.branch_misses();
350380
uint64_t calc_misses = uint64_t(features.calc_expected_misses(stage, results));
351381
double calc_miss_cost = features.calc_expected_miss_cost(stage, results);
352-
printf("| %-8s ", benchmark_stage_name(stage));
382+
printf(" | %-8s ", benchmark_stage_name(stage));
353383
printf("| %-15s ", filename);
354384
printf("| %8.3g ", features.calc_expected_feature_cost(stage, results));
355385
printf("| %8.3g ", calc_miss_cost);
@@ -412,45 +442,47 @@ int main(int argc, char *argv[]) {
412442
features.print(options);
413443

414444
// Gauge effectiveness
415-
printf("\n");
416-
printf("Estimated vs. Actual ns/block for real files:\n");
417-
printf("\n");
418-
printf("| %8s ", "Stage");
419-
printf("| %-15s ", "File");
420-
printf("| %11s ", "Est. (Base)");
421-
printf("| %11s ", "Est. (Miss)");
422-
printf("| %8s ", "Est.");
423-
printf("| %8s ", "Actual");
424-
printf("| %8s ", "Diff");
425-
printf("| %13s ", "Est. Misses");
426-
if (features.has_events()) {
427-
printf("| %13s ", "Actual Misses");
428-
printf("| %13s ", "Diff (Misses)");
429-
printf("| %13s ", "Adjusted Miss");
430-
printf("| %13s ", "Adjusted Diff");
431-
}
432-
printf("|\n");
433-
printf("|%.10s", "---------------------------------------");
434-
printf("|%.17s", "---------------------------------------");
435-
printf("|%.13s", "---------------------------------------");
436-
printf("|%.13s", "---------------------------------------");
437-
printf("|%.10s", "---------------------------------------");
438-
printf("|%.10s", "---------------------------------------");
439-
printf("|%.10s", "---------------------------------------");
440-
printf("|%.15s", "---------------------------------------");
441-
if (features.has_events()) {
442-
printf("|%.15s", "---------------------------------------");
443-
printf("|%.15s", "---------------------------------------");
444-
printf("|%.15s", "---------------------------------------");
445+
if (options.verbose) {
446+
printf("\n");
447+
printf(" Effectiveness Check: Estimated vs. Actual ns/block for real files:\n");
448+
printf("\n");
449+
printf(" | %8s ", "Stage");
450+
printf("| %-15s ", "File");
451+
printf("| %11s ", "Est. (Base)");
452+
printf("| %11s ", "Est. (Miss)");
453+
printf("| %8s ", "Est.");
454+
printf("| %8s ", "Actual");
455+
printf("| %8s ", "Diff");
456+
printf("| %13s ", "Est. Misses");
457+
if (features.has_events()) {
458+
printf("| %13s ", "Actual Misses");
459+
printf("| %13s ", "Diff (Misses)");
460+
printf("| %13s ", "Adjusted Miss");
461+
printf("| %13s ", "Adjusted Diff");
462+
}
463+
printf("|\n");
464+
printf(" |%.10s", "---------------------------------------");
465+
printf("|%.17s", "---------------------------------------");
466+
printf("|%.13s", "---------------------------------------");
467+
printf("|%.13s", "---------------------------------------");
468+
printf("|%.10s", "---------------------------------------");
469+
printf("|%.10s", "---------------------------------------");
470+
printf("|%.10s", "---------------------------------------");
445471
printf("|%.15s", "---------------------------------------");
446-
}
447-
printf("|\n");
472+
if (features.has_events()) {
473+
printf("|%.15s", "---------------------------------------");
474+
printf("|%.15s", "---------------------------------------");
475+
printf("|%.15s", "---------------------------------------");
476+
printf("|%.15s", "---------------------------------------");
477+
}
478+
printf("|\n");
448479

449-
options.each_stage([&](auto stage) {
450-
print_file_effectiveness(stage, "gsoc-2018.json", gsoc_2018, features);
451-
print_file_effectiveness(stage, "twitter.json", twitter, features);
452-
print_file_effectiveness(stage, "random.json", random, features);
453-
});
480+
options.each_stage([&](auto stage) {
481+
print_file_effectiveness(stage, "gsoc-2018.json", gsoc_2018, features);
482+
print_file_effectiveness(stage, "twitter.json", twitter, features);
483+
print_file_effectiveness(stage, "random.json", random, features);
484+
});
485+
}
454486

455487
return EXIT_SUCCESS;
456488
}

‎benchmark/benchmarker.h‎

Lines changed: 32 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -75,6 +75,8 @@ struct json_stats {
7575
size_t structurals = 0;
7676
size_t blocks_with_utf8 = 0;
7777
size_t blocks_with_utf8_flipped = 0;
78+
size_t blocks_with_escapes = 0;
79+
size_t blocks_with_escapes_flipped = 0;
7880
size_t blocks_with_0_structurals = 0;
7981
size_t blocks_with_0_structurals_flipped = 0;
8082
size_t blocks_with_1_structural = 0;
@@ -113,6 +115,29 @@ struct json_stats {
113115
last_block_has_utf8 = block_has_utf8;
114116
}
115117

118+
// Calculate stats on blocks that will trigger escape if statements / mispredictions
119+
bool last_block_has_escapes = false;
120+
for (size_t block=0; block<blocks; block++) {
121+
// Find utf-8 in the block
122+
size_t block_start = block*BYTES_PER_BLOCK;
123+
size_t block_end = block_start+BYTES_PER_BLOCK;
124+
if (block_end > json.size()) { block_end = json.size(); }
125+
bool block_has_escapes = false;
126+
for (size_t i=block_start; i<block_end; i++) {
127+
if (json.data()[i] == '\\') {
128+
block_has_escapes = true;
129+
break;
130+
}
131+
}
132+
if (block_has_escapes) {
133+
blocks_with_escapes++;
134+
}
135+
if (block > 0 && last_block_has_escapes != block_has_escapes) {
136+
blocks_with_escapes_flipped++;
137+
}
138+
last_block_has_escapes = block_has_escapes;
139+
}
140+
116141
// Calculate stats on blocks that will trigger structural count if statements / mispredictions
117142
bool last_block_has_0_structurals = false;
118143
bool last_block_has_1_structural = false;
@@ -280,7 +305,7 @@ struct benchmarker {
280305
return all_stages.iterations;
281306
}
282307

283-
really_inline void run_iteration(bool stage1_only, bool hotbuffers) {
308+
really_inline void run_iteration(bool stage1_only, bool hotbuffers=false) {
284309
// Allocate ParsedJson
285310
collector.start();
286311
ParsedJson pj;
@@ -336,7 +361,7 @@ struct benchmarker {
336361
}
337362
}
338363

339-
really_inline void run_iterations(size_t iterations, bool stage1_only, bool hotbuffers) {
364+
really_inline void run_iterations(size_t iterations, bool stage1_only, bool hotbuffers=false) {
340365
for (size_t i = 0; i<iterations; i++) {
341366
run_iteration(stage1_only, hotbuffers);
342367
}
@@ -425,16 +450,18 @@ struct benchmarker {
425450
printf("%s\n", string(strlen(filename), '=').c_str());
426451
printf("%9zu blocks - %10zu bytes - %5zu structurals (%5.1f %%)\n", stats->bytes / BYTES_PER_BLOCK, stats->bytes, stats->structurals, 100.0 * stats->structurals / stats->bytes);
427452
if (stats) {
428-
printf("special blocks with: utf8 %9zu (%5.1f %%) - 0 structurals %9zu (%5.1f %%) - 1+ structurals %9zu (%5.1f %%) - 8+ structurals %9zu (%5.1f %%) - 16+ structurals %9zu (%5.1f %%)\n",
453+
printf("special blocks with: utf8 %9zu (%5.1f %%) - escape %9zu (%5.1f %%) - 0 structurals %9zu (%5.1f %%) - 1+ structurals %9zu (%5.1f %%) - 8+ structurals %9zu (%5.1f %%) - 16+ structurals %9zu (%5.1f %%)\n",
429454
stats->blocks_with_utf8, 100.0 * stats->blocks_with_utf8 / stats->blocks,
455+
stats->blocks_with_escapes, 100.0 * stats->blocks_with_escapes / stats->blocks,
430456
stats->blocks_with_0_structurals, 100.0 * stats->blocks_with_0_structurals / stats->blocks,
431457
stats->blocks_with_1_structural, 100.0 * stats->blocks_with_1_structural / stats->blocks,
432458
stats->blocks_with_8_structurals, 100.0 * stats->blocks_with_8_structurals / stats->blocks,
433459
stats->blocks_with_16_structurals, 100.0 * stats->blocks_with_16_structurals / stats->blocks);
434-
printf("special block flips: utf8 %9zu (%5.1f %%) - 0 structurals %9zu (%5.1f %%) - 1+ structurals %9zu (%5.1f %%) - 8+ structurals %9zu (%5.1f %%) - 16+ structurals %9zu (%5.1f %%)\n",
460+
printf("special block flips: utf8 %9zu (%5.1f %%) - escape %9zu (%5.1f %%) - 0 structurals %9zu (%5.1f %%) - 1+ structurals %9zu (%5.1f %%) - 8+ structurals %9zu (%5.1f %%) - 16+ structurals %9zu (%5.1f %%)\n",
435461
stats->blocks_with_utf8_flipped, 100.0 * stats->blocks_with_utf8_flipped / stats->blocks,
436-
stats->blocks_with_1_structural_flipped, 100.0 * stats->blocks_with_1_structural_flipped / stats->blocks,
462+
stats->blocks_with_escapes_flipped, 100.0 * stats->blocks_with_escapes_flipped / stats->blocks,
437463
stats->blocks_with_0_structurals_flipped, 100.0 * stats->blocks_with_0_structurals_flipped / stats->blocks,
464+
stats->blocks_with_1_structural_flipped, 100.0 * stats->blocks_with_1_structural_flipped / stats->blocks,
438465
stats->blocks_with_8_structurals_flipped, 100.0 * stats->blocks_with_8_structurals_flipped / stats->blocks,
439466
stats->blocks_with_16_structurals_flipped, 100.0 * stats->blocks_with_16_structurals_flipped / stats->blocks);
440467
}

‎benchmark/genfeaturejson.rb‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -88,6 +88,7 @@ def write_chunks(file, start1, repeat1, end1, size)
8888
Dir.mkdir(output_dir) unless File.directory?(output_dir)
8989
w = ChunkWriter.new(output_dir, miss_templates)
9090
w.write_files "utf-8", '["֏","֏",{}', ',"֏","֏",{}', ',"֏","֏","֏"]', repeat2: ',"ab","ab",{}'
91+
w.write_files "escape", '["\\"","\\"",{}', ',"\\"","\\"",{}', ',"\\"","\\"","\\""]', repeat2: ',"ab","ab",{}'
9192
w.write_files "0-structurals", '"ab"', '', ''
9293
# w.write_files "1-structurals", [ '[', '"ab"' ], [ ',', '"ab"' ], [ ',', '{', '}', ']' ]
9394
# w.write_files "2-structurals", '["ab"', ',"ab"', [',{', '}]']

0 commit comments

Comments
 (0)