Skip to content

Commit e2f349e

Browse files
jkeiserjkeiser
committed
Measure impact of utf-8 blocks and structurals per block directly
1 parent 102262c commit e2f349e

14 files changed

Lines changed: 21367 additions & 385 deletions

File tree

‎.gitignore‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -53,6 +53,7 @@ objs
5353
# Build outputs (TODO build to a subdir so we can exclude that instead)
5454
/allparserscheckfile
5555
/basictests
56+
/benchfeatures
5657
/benchmark/parse
5758
/benchmark/perfdiff
5859
/benchmark/statisticalmodel
@@ -86,6 +87,9 @@ objs
8687
/tools/jsonstats
8788
/tools/minify
8889

90+
# Don't check in generated examples
91+
/jsonexamples/generated
92+
8993
# C++ ignore from https://github.com/github/gitignore/blob/master/C%2B%2B.gitignore
9094

9195
# Prerequisites

‎Makefile‎

Lines changed: 10 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -126,6 +126,12 @@ run_issue150_sh: allparserscheckfile
126126
run_testjson2json_sh: minify json2json
127127
./scripts/testjson2json.sh
128128

129+
generate_featurejson:
130+
ruby ./benchmark/genfeaturejson.rb
131+
132+
run_benchfeatures: benchfeatures generate_featurejson
133+
./benchfeatures -n 1000
134+
129135
test: run_basictests run_jsoncheck run_numberparsingcheck run_integer_tests run_stringparsingcheck run_jsonstream_test run_pointercheck run_testjson2json_sh run_issue150_sh run_jsoncheck_noavx
130136
@echo "It looks like the code is good!"
131137

@@ -145,9 +151,12 @@ submodules:
145151

146152
$(JSON_INCLUDE) $(SAJSON_INCLUDE) $(RAPIDJSON_INCLUDE) $(JSON11_INCLUDE) $(FASTJSON_INCLUDE) $(GASON_INCLUDE) $(UJSON4C_INCLUDE) $(CJSON_INCLUDE) $(JSMN_INCLUDE) : submodules
147153

148-
parse: benchmark/parse.cpp $(HEADERS) $(LIBFILES)
154+
parse: benchmark/parse.cpp benchmark/json_parser.h benchmark/event_counter.h benchmark/benchmarker.h $(HEADERS) $(LIBFILES)
149155
$(CXX) $(CXXFLAGS) -o parse $(LIBFILES) benchmark/parse.cpp $(LIBFLAGS)
150156

157+
benchfeatures: benchmark/benchfeatures.cpp benchmark/json_parser.h benchmark/event_counter.h benchmark/benchmarker.h $(HEADERS) $(LIBFILES)
158+
$(CXX) $(CXXFLAGS) -o benchfeatures $(LIBFILES) benchmark/benchfeatures.cpp $(LIBFLAGS)
159+
151160
perfdiff: benchmark/perfdiff.cpp
152161
$(CXX) $(CXXFLAGS) -o perfdiff benchmark/perfdiff.cpp $(LIBFLAGS)
153162

‎benchmark/benchfeatures.cpp‎

Lines changed: 326 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,326 @@
1+
#include "json_parser.h"
2+
#include "event_counter.h"
3+
4+
#include <cassert>
5+
#include <cctype>
6+
#ifndef _MSC_VER
7+
#include <dirent.h>
8+
#include <unistd.h>
9+
#endif
10+
#include <cinttypes>
11+
12+
#include <cstdio>
13+
#include <cstdlib>
14+
#include <cstring>
15+
16+
#include <algorithm>
17+
#include <chrono>
18+
#include <cstring>
19+
#include <fstream>
20+
#include <iomanip>
21+
#include <iostream>
22+
#include <map>
23+
#include <set>
24+
#include <sstream>
25+
#include <string>
26+
#include <vector>
27+
28+
#include "linux-perf-events.h"
29+
#ifdef __linux__
30+
#include <libgen.h>
31+
#endif
32+
//#define DEBUG
33+
#include "simdjson/common_defs.h"
34+
#include "simdjson/isadetection.h"
35+
#include "simdjson/jsonioutil.h"
36+
#include "simdjson/jsonparser.h"
37+
#include "simdjson/parsedjson.h"
38+
#include "simdjson/stage1_find_marks.h"
39+
#include "simdjson/stage2_build_tape.h"
40+
41+
#include <functional>
42+
43+
#include "benchmarker.h"
44+
45+
using namespace simdjson;
46+
using std::cerr;
47+
using std::cout;
48+
using std::endl;
49+
using std::string;
50+
using std::to_string;
51+
using std::vector;
52+
using std::ostream;
53+
using std::ofstream;
54+
using std::exception;
55+
56+
// Stash the exe_name in main() for functions to use
57+
char* exe_name;
58+
59+
void print_usage(ostream& out) {
60+
out << "Usage: " << exe_name << " [-v] [-n #] [-s STAGE] [-a ARCH]" << endl;
61+
out << endl;
62+
out << "Runs the parser against jsonexamples/generated json files in a loop, measuring speed and other statistics." << endl;
63+
out << endl;
64+
out << "Options:" << endl;
65+
out << endl;
66+
out << "-n # - Number of iterations per file. Default: 400" << endl;
67+
out << "-i # - Number of times to iterate a single file before moving to the next. Default: 20" << endl;
68+
out << "-v - Verbose output." << endl;
69+
out << "-s STAGE - Stop after the given stage." << endl;
70+
out << " -s stage1 - Stop after find_structural_bits." << endl;
71+
out << " -s all - Run all stages." << endl;
72+
out << "-a ARCH - Use the parser with the designated architecture (HASWELL, WESTMERE" << endl;
73+
out << " or ARM64). By default, detects best supported architecture." << endl;
74+
}
75+
76+
void exit_usage(string message) {
77+
cerr << message << endl;
78+
cerr << endl;
79+
print_usage(cerr);
80+
exit(EXIT_FAILURE);
81+
}
82+
83+
struct option_struct {
84+
Architecture architecture = Architecture::UNSUPPORTED;
85+
bool stage1_only = false;
86+
87+
int32_t iterations = 400;
88+
int32_t iteration_step = 50;
89+
90+
bool verbose = false;
91+
92+
option_struct(int argc, char **argv) {
93+
#ifndef _MSC_VER
94+
int c;
95+
96+
while ((c = getopt(argc, argv, "vtn:i:a:s:")) != -1) {
97+
switch (c) {
98+
case 'n':
99+
iterations = atoi(optarg);
100+
break;
101+
case 'i':
102+
iteration_step = atoi(optarg);
103+
break;
104+
case 'v':
105+
verbose = true;
106+
break;
107+
case 'a':
108+
architecture = parse_architecture(optarg);
109+
if (architecture == Architecture::UNSUPPORTED) {
110+
exit_usage(string("Unsupported option value -a ") + optarg + ": expected -a HASWELL, WESTMERE or ARM64");
111+
}
112+
break;
113+
case 's':
114+
if (!strcmp(optarg, "stage1")) {
115+
stage1_only = true;
116+
} else if (!strcmp(optarg, "all")) {
117+
stage1_only = false;
118+
} else {
119+
exit_usage(string("Unsupported option value -s ") + optarg + ": expected -s stage1 or all");
120+
}
121+
break;
122+
default:
123+
exit_error("Unexpected argument " + c);
124+
}
125+
}
126+
#else
127+
int optind = 1;
128+
#endif
129+
130+
// If architecture is not specified, pick the best supported architecture by default
131+
if (architecture == Architecture::UNSUPPORTED) {
132+
architecture = find_best_supported_architecture();
133+
}
134+
}
135+
};
136+
137+
double actual(const benchmarker& feature) {
138+
return feature.stage1.best.elapsed_ns() / feature.stats->blocks;
139+
}
140+
double diff(const benchmarker& feature, const benchmarker& struct7) {
141+
if (feature.stats->blocks == struct7.stats->blocks) {
142+
return (feature.stage1.best.elapsed_ns() - struct7.stage1.best.elapsed_ns()) / struct7.stats->blocks;
143+
} else {
144+
return (feature.stage1.best.elapsed_ns() / feature.stats->blocks) - (struct7.stage1.best.elapsed_ns() / struct7.stats->blocks);
145+
}
146+
}
147+
double diff_miss(const benchmarker& feature, const benchmarker& struct7) {
148+
// There are roughly 2650 branch mispredicts, so we have to scale it so it represents a per block amount
149+
return diff(feature, struct7) * 10000.0 / 2650.0;
150+
}
151+
152+
struct feature_benchmarker {
153+
benchmarker utf8;
154+
benchmarker utf8_miss;
155+
benchmarker empty;
156+
benchmarker empty_miss;
157+
benchmarker struct7;
158+
benchmarker struct7_miss;
159+
benchmarker struct7_full;
160+
benchmarker struct15;
161+
benchmarker struct15_miss;
162+
benchmarker struct23;
163+
benchmarker struct23_miss;
164+
165+
feature_benchmarker(json_parser& parser, event_collector& collector) :
166+
utf8 ("jsonexamples/generated/utf-8.json", parser, collector),
167+
utf8_miss ("jsonexamples/generated/utf-8-miss.json", parser, collector),
168+
empty ("jsonexamples/generated/0-structurals.json", parser, collector),
169+
empty_miss ("jsonexamples/generated/0-structurals-miss.json", parser, collector),
170+
struct7 ("jsonexamples/generated/7-structurals.json", parser, collector),
171+
struct7_miss ("jsonexamples/generated/7-structurals-miss.json", parser, collector),
172+
struct7_full ("jsonexamples/generated/7-structurals-full.json", parser, collector),
173+
struct15 ("jsonexamples/generated/15-structurals.json", parser, collector),
174+
struct15_miss("jsonexamples/generated/15-structurals-miss.json", parser, collector),
175+
struct23 ("jsonexamples/generated/23-structurals.json", parser, collector),
176+
struct23_miss("jsonexamples/generated/23-structurals-miss.json", parser, collector)
177+
{
178+
179+
}
180+
181+
really_inline void run_iterations(size_t iterations, bool stage1_only=false) {
182+
struct7.run_iterations(iterations, stage1_only);
183+
struct7_miss.run_iterations(iterations, stage1_only);
184+
struct7_full.run_iterations(iterations, stage1_only);
185+
utf8.run_iterations(iterations, stage1_only);
186+
utf8_miss.run_iterations(iterations, stage1_only);
187+
empty.run_iterations(iterations, stage1_only);
188+
empty_miss.run_iterations(iterations, stage1_only);
189+
struct15.run_iterations(iterations, stage1_only);
190+
struct15_miss.run_iterations(iterations, stage1_only);
191+
struct23.run_iterations(iterations, stage1_only);
192+
struct23_miss.run_iterations(iterations, stage1_only);
193+
}
194+
195+
void print() {
196+
printf("base (ns/block)");
197+
printf(",struct 1-7");
198+
printf(",struct 1-7 miss");
199+
printf(",utf-8");
200+
printf(",utf-8 miss");
201+
printf(",struct 8-15");
202+
printf(",struct 8-15 miss");
203+
printf(",struct 16+");
204+
printf(",struct 16+ miss");
205+
printf("\n");
206+
207+
printf("%g", actual(empty));
208+
printf(",%+g", diff(struct7, empty));
209+
printf(",%+g", diff(struct7_miss, struct7));
210+
printf(",%+g", diff(utf8, struct7));
211+
printf(",%+g", diff(utf8_miss, utf8));
212+
printf(",%+g", diff(struct15, struct7));
213+
printf(",%+g", diff(struct15_miss, struct15));
214+
printf(",%+g", diff(struct23, struct15));
215+
printf(",%+g", diff(struct23_miss, struct23));
216+
printf("\n");
217+
}
218+
219+
double cost_per_block(benchmarker& feature, size_t feature_blocks, benchmarker& base) {
220+
return (feature.stage1.best.elapsed_ns() - base.stage1.best.elapsed_ns()) / feature_blocks;
221+
}
222+
223+
// Base cost of any block (including empty ones)
224+
double base_cost() {
225+
return (empty.stage1.best.elapsed_ns() / empty.stats->blocks);
226+
}
227+
// Extra cost of a 1-7 structural block over an empty block
228+
double struct1_7_cost() {
229+
return cost_per_block(struct7, struct7.stats->blocks_with_1_structural, empty);
230+
}
231+
// Extra cost of an 1-7-structural miss
232+
double struct1_7_miss_cost() {
233+
return cost_per_block(struct7_miss, struct7_miss.stats->blocks_with_1_structural, struct7);
234+
}
235+
// Extra cost of an 8-15 structural block over a 1-7 structural block
236+
double struct8_15_cost() {
237+
return cost_per_block(struct15, struct15.stats->blocks_with_8_structurals, struct7);
238+
}
239+
// Extra cost of an 8-15-structural miss over a 1-7 miss
240+
double struct8_15_miss_cost() {
241+
return cost_per_block(struct15_miss, struct15_miss.stats->blocks_with_8_structurals_flipped, struct15);
242+
}
243+
// Extra cost of a 16+-structural block over an 8-15 structural block (actual varies based on # of structurals!)
244+
double struct16_cost() {
245+
return cost_per_block(struct23, struct23.stats->blocks_with_16_structurals, struct15);
246+
}
247+
// Extra cost of a 16-structural miss over an 8-15 miss
248+
double struct16_miss_cost() {
249+
return cost_per_block(struct23_miss, struct23_miss.stats->blocks_with_16_structurals_flipped, struct23);
250+
}
251+
// Extra cost of having UTF-8 in a block
252+
double utf8_cost() {
253+
return cost_per_block(utf8, utf8.stats->blocks_with_utf8, struct7_full);
254+
}
255+
// Extra cost of a UTF-8 miss
256+
double utf8_miss_cost() {
257+
return cost_per_block(utf8_miss, utf8_miss.stats->blocks_with_utf8_flipped, utf8);
258+
}
259+
260+
double calc_expected(benchmarker& file) {
261+
// Expected base ns/block (empty)
262+
json_stats& stats = *file.stats;
263+
double expected = base_cost() * stats.blocks;
264+
expected += struct1_7_cost() * stats.blocks_with_1_structural;
265+
expected += struct1_7_miss_cost() * stats.blocks_with_1_structural_flipped;
266+
expected += utf8_cost() * stats.blocks_with_utf8;
267+
expected += utf8_miss_cost() * stats.blocks_with_utf8_flipped;
268+
expected += struct8_15_cost() * stats.blocks_with_8_structurals;
269+
expected += struct8_15_miss_cost() * stats.blocks_with_8_structurals_flipped;
270+
expected += struct16_cost() * stats.blocks_with_16_structurals;
271+
expected += struct16_miss_cost() * stats.blocks_with_16_structurals_flipped;
272+
return expected / stats.blocks;
273+
}
274+
};
275+
276+
int main(int argc, char *argv[]) {
277+
// Read options
278+
exe_name = argv[0];
279+
option_struct options(argc, argv);
280+
if (options.verbose) {
281+
verbose_stream = &cout;
282+
}
283+
284+
// Initialize the event collector. We put this early so if it prints an error message, it's the
285+
// first thing printed.
286+
event_collector collector;
287+
288+
// Set up benchmarkers by reading all files
289+
json_parser parser(options.architecture);
290+
291+
feature_benchmarker features(parser, collector);
292+
benchmarker gsoc_2018("jsonexamples/gsoc-2018.json", parser, collector);
293+
benchmarker twitter("jsonexamples/twitter.json", parser, collector);
294+
benchmarker random("jsonexamples/random.json", parser, collector);
295+
296+
// Run the benchmarks
297+
progress_bar progress(options.iterations, 100);
298+
// Put the if (options.stage1_only) *outside* the loop so that run_iterations will be optimized
299+
if (options.stage1_only) {
300+
for (int iteration = 0; iteration < options.iterations; iteration += options.iteration_step) {
301+
if (!options.verbose) { progress.print(iteration); }
302+
features.run_iterations(options.iteration_step, true);
303+
gsoc_2018.run_iterations(options.iteration_step, true);
304+
twitter.run_iterations(options.iteration_step, true);
305+
random.run_iterations(options.iteration_step, true);
306+
}
307+
} else {
308+
for (int iteration = 0; iteration < options.iterations; iteration += options.iteration_step) {
309+
if (!options.verbose) { progress.print(iteration); }
310+
features.run_iterations(options.iteration_step, false);
311+
gsoc_2018.run_iterations(options.iteration_step, false);
312+
twitter.run_iterations(options.iteration_step, false);
313+
random.run_iterations(options.iteration_step, false);
314+
}
315+
}
316+
if (!options.verbose) { progress.erase(); }
317+
318+
features.print();
319+
320+
// Gauge effectiveness
321+
printf("gsoc-2018.json expected/actual: %g/%g\n", features.calc_expected(gsoc_2018), actual(gsoc_2018));
322+
printf("twitter.json expected/actual: %g/%g\n", features.calc_expected(twitter), actual(twitter));
323+
printf("random.json expected/actual: %g/%g\n", features.calc_expected(random), actual(random));
324+
325+
return EXIT_SUCCESS;
326+
}

0 commit comments

Comments
 (0)