OILS / benchmarks / osh-parser.sh View on Github | oils.pub

524 lines, 299 significant
1#!/usr/bin/env bash
2#
3# Measure how fast the OSH parser is.
4#
5# Usage:
6# benchmarks/osh-parser.sh <function name>
7#
8# Examples:
9# benchmarks/osh-parser.sh soil-run
10# QUICKLY=1 benchmarks/osh-parser.sh soil-run
11
12set -o nounset
13set -o pipefail
14set -o errexit
15
16REPO_ROOT=$(cd "$(dirname $0)/.."; pwd) # tsv-lib.sh uses this
17readonly REPO_ROOT
18
19source benchmarks/common.sh # die
20source benchmarks/cachegrind.sh # with-cachgrind
21source test/tsv-lib.sh # tsv2html
22source test/common.sh # die
23
24# TODO: The raw files should be published. In both
25# ~/git/oilshell/benchmarks-data and also in the /release/ hierarchy?
26readonly BASE_DIR=_tmp/osh-parser
27readonly SORTED=$BASE_DIR/tmp/sorted.txt
28
29write-sorted-manifest() {
30 local files=${1:-benchmarks/osh-parser-files.txt}
31 local counts=$BASE_DIR/tmp/line-counts.txt
32 local csv_out=$2
33 local sep=${3:-','} # CSV or TSV
34
35 # Remove comments and sort by line count
36 grep -v '^#' $files | xargs wc -l | sort -n > $counts
37
38 # Raw list of paths
39 cat $counts | awk '$2 != "total" { print $2 }' > $SORTED
40
41 # Make a CSV file from wc output
42 cat $counts | awk -v sep="$sep" '
43 BEGIN { print "num_lines" sep "path" }
44 $2 != "total" { print $1 sep $2 }' \
45 > $csv_out
46}
47
48# Called by xargs with a task row.
49parser-task() {
50 local out_dir=$1 # output
51 local job_id=$2
52 local host=$3
53 local host_hash=$4
54 local sh_path=$5
55 local shell_hash=$6
56 local script_path=$7
57
58 echo "--- TIME $sh_path $script_path ---"
59
60 local times_out="$out_dir/$host.$job_id.times.csv"
61
62 local shell_name
63 case $sh_path in
64 _bin/*/mycpp-souffle/*)
65 shell_name=osh-native-souffle
66 ;;
67 *)
68 shell_name=$(basename $sh_path)
69 ;;
70 esac
71
72 # Can't use array because of set -u bug!!! Only fixed in bash 4.4.
73 extra_args=''
74 case "$shell_name" in
75 osh*|oils-for-unix.*)
76 extra_args='--ast-format none'
77 ;;
78 esac
79
80 # exit code, time in seconds, host_hash, shell_hash, path. \0
81 # would have been nice here!
82 # TODO: TSV
83 benchmarks/time_.py \
84 --append \
85 --output $times_out \
86 --rusage \
87 --field "$host" --field "$host_hash" \
88 --field "$shell_name" --field "$shell_hash" \
89 --field "$script_path" -- \
90 "$sh_path" -n $extra_args "$script_path" || echo FAILED
91}
92
93# Called by xargs with a task row.
94# NOTE: This is very similar to the function above, except that we add
95# cachegrind. We could probably conslidate these.
96cachegrind-task() {
97 local out_dir=$1 # output
98 local job_id=$2
99 local host_name=$3
100 local unused2=$4
101 local sh_path=$5
102 local shell_hash=$6
103 local script_path=$7
104
105 echo "--- CACHEGRIND $sh_path $script_path ---"
106
107 local host_job_id="$host_name.$job_id"
108
109 # NOTE: This has to match the path that the header was written to
110 local times_out="$out_dir/$host_job_id.cachegrind.tsv"
111
112 local cachegrind_out_dir="$host_job_id.cachegrind"
113 mkdir -p $out_dir/$cachegrind_out_dir
114
115 local shell_name
116 case $sh_path in
117 _bin/*/mycpp-souffle/*)
118 shell_name=osh-native-souffle
119 ;;
120 *)
121 shell_name=$(basename $sh_path)
122 ;;
123 esac
124
125 local script_name
126 script_name=$(basename $script_path)
127
128 # RELATIVE PATH
129 local cachegrind_out_path="${cachegrind_out_dir}/${shell_name}-${shell_hash}__${script_name}.txt"
130
131 # Can't use array because of set -u bug!!! Only fixed in bash 4.4.
132 extra_args=''
133 case "$shell_name" in
134 osh*|oils-for-unix.*)
135 extra_args="--ast-format none"
136 ;;
137 esac
138
139 benchmarks/time_.py \
140 --tsv \
141 --append \
142 --output $times_out \
143 --rusage \
144 --field "$shell_name" --field "$shell_hash" \
145 --field "$script_path" \
146 --field $cachegrind_out_path \
147 -- \
148 $0 with-cachegrind $out_dir/$cachegrind_out_path \
149 "$sh_path" -n $extra_args "$script_path" || echo FAILED
150}
151
152# For each shell, print 10 script paths.
153print-tasks() {
154 local provenance=$1
155 shift
156 # rest are shells
157
158 # Add 1 field for each of 5 fields.
159 cat $provenance | filter-provenance "$@" |
160 while read fields; do
161 if test -n "${QUICKLY:-}"; then
162 # Quick test
163 head -n 2 $SORTED | xargs -n 1 -- echo "$fields"
164 else
165 cat $SORTED | xargs -n 1 -- echo "$fields"
166 fi
167 done
168}
169
170cachegrind-parse-configure-coreutils() {
171 ### Similar to benchmarks/gc, benchmarks/uftrace
172
173 local bin=_bin/cxx-opt/oils-for-unix
174 ninja $bin
175 local out=_tmp/parse.configure-coreutils.txt
176
177 local -a cmd=(
178 $bin --ast-format none -n
179 benchmarks/testdata/configure-coreutils )
180
181 time "${cmd[@]}"
182
183 time cachegrind $out "${cmd[@]}"
184
185 echo
186 cat $out
187}
188
189cachegrind-demo() {
190 #local sh=bash
191 local sh=zsh
192
193 local out_dir=_tmp/cachegrind
194
195 mkdir -p $out_dir
196
197 # notes:
198 # - not passing --trace-children (follow execvpe)
199 # - passing --xml=yes gives error: cachegrind doesn't support XML
200 # - there is a log out and a details out
201
202 valgrind --tool=cachegrind \
203 --log-file=$out_dir/log.txt \
204 --cachegrind-out-file=$out_dir/details.txt \
205 -- $sh -c 'echo hi'
206
207 echo
208 head -n 20 $out_dir/*.txt
209}
210
211readonly NUM_TASK_COLS=6 # input columns: 5 from provenance, 1 for file
212
213# Figure out all tasks to run, and run them. When called from auto.sh, $2
214# should be the ../benchmarks-data repo.
215measure() {
216 local provenance=$1
217 local host_job_id=$2
218 local out_dir=${3:-$BASE_DIR/raw}
219 shift 3
220 local -a osh_cpp=( "${@:-$OSH_CPP_BENCHMARK_DATA}" )
221
222 local times_out="$out_dir/$host_job_id.times.csv"
223 local lines_out="$out_dir/$host_job_id.lines.csv"
224
225 mkdir -p $BASE_DIR/{tmp,raw,stage1} $out_dir
226
227 # Files that we should measure. Exploded into tasks.
228 write-sorted-manifest '' $lines_out
229
230 # Write Header of the CSV file that is appended to.
231 # TODO: TSV
232 benchmarks/time_.py --print-header \
233 --rusage \
234 --field host_name --field host_hash \
235 --field shell_name --field shell_hash \
236 --field path \
237 > $times_out
238
239 local tasks=$BASE_DIR/tasks.txt
240 print-tasks $provenance "${SHELLS[@]}" "${osh_cpp[@]}" > $tasks
241
242 # Run them all
243 cat $tasks | xargs -n $NUM_TASK_COLS -- $0 parser-task $out_dir
244}
245
246measure-cachegrind() {
247 local provenance=$1
248 local host_job_id=$2
249 local out_dir=${3:-$BASE_DIR/raw}
250 shift 3
251 local -a osh_cpp=( "${@:-$OSH_CPP_BENCHMARK_DATA}" )
252
253 local cachegrind_tsv="$out_dir/$host_job_id.cachegrind.tsv"
254 local lines_out="$out_dir/$host_job_id.lines.tsv"
255
256 mkdir -p $BASE_DIR/{tmp,raw,stage1} $out_dir
257
258 write-sorted-manifest '' $lines_out $'\t' # TSV
259
260 # TODO: This header is fragile. Every task should print its own file with a
261 # header, and then we can run them in parallel, and join them with
262 # devtools/csv_concat.py
263
264 benchmarks/time_.py --tsv --print-header \
265 --rusage \
266 --field shell_name --field shell_hash \
267 --field path \
268 --field cachegrind_out_path \
269 > $cachegrind_tsv
270
271 local ctasks=$BASE_DIR/cachegrind-tasks.txt
272
273 # zsh weirdly forks during zsh -n, which complicates our cachegrind
274 # measurement. So just ignore it. (This can be seen with
275 # strace -e fork -f -- zsh -n $file)
276 print-tasks $provenance bash dash mksh "${osh_cpp[@]}" > $ctasks
277
278 cat $ctasks | xargs -n $NUM_TASK_COLS -- $0 cachegrind-task $out_dir
279}
280
281#
282# Data Preparation and Analysis
283#
284
285stage1-cachegrind() {
286 local raw_dir=$1
287 local single_machine=$2
288 local out_dir=$3
289 local raw_data_csv=$4
290
291 local maybe_host
292 if test -n "$single_machine"; then
293 # CI: _tmp/osh-parser/raw.no-host.$job_id
294 maybe_host='no-host'
295 else
296 # release: ../benchmark-data/osh-parser/raw.lenny.$job_id
297 #maybe_host=$(hostname)
298 maybe_host=$MACHINE1 # lenny
299 fi
300
301 # Only runs on one machine
302 local -a sorted=( $raw_dir/$maybe_host.*.cachegrind.tsv )
303 local tsv_in=${sorted[-1]} # latest one
304
305 devtools/tsv_column_from_files.py \
306 --new-column irefs \
307 --path-column cachegrind_out_path \
308 --extract-group-1 'I[ ]*refs:[ ]*([\d,]+)' \
309 --remove-commas \
310 $tsv_in > $out_dir/cachegrind.tsv
311
312 echo $tsv_in >> $raw_data_csv
313}
314
315stage1() {
316 local raw_dir=${1:-$BASE_DIR/raw}
317 local single_machine=${2:-}
318
319 local out=$BASE_DIR/stage1
320 mkdir -p $out
321
322 # Construct a one-column CSV file
323 local raw_data_csv=$out/raw-data.csv
324 echo 'path' > $raw_data_csv
325
326 stage1-cachegrind $raw_dir "$single_machine" $out $raw_data_csv
327
328 local lines_csv=$out/lines.csv
329
330 local -a raw=()
331 if test -n "$single_machine"; then
332 local -a a=($raw_dir/$single_machine.*.times.csv)
333 raw+=( ${a[-1]} )
334 echo ${a[-1]} >> $raw_data_csv
335
336 # They are the same, output one of them.
337 cat $raw_dir/$single_machine.*.lines.csv > $lines_csv
338 else
339 # Globs are in lexicographical order, which works for our dates.
340 local -a a=($raw_dir/$MACHINE1.*.times.csv)
341 local -a b=($raw_dir/$MACHINE2.*.times.csv)
342
343 raw+=( ${a[-1]} ${b[-1]} )
344 {
345 echo ${a[-1]}
346 echo ${b[-1]}
347 } >> $raw_data_csv
348
349
350 # Verify that the files are equal, and pass one of them.
351 local -a c=($raw_dir/$MACHINE1.*.lines.csv)
352 local -a d=($raw_dir/$MACHINE2.*.lines.csv)
353
354 local left=${c[-1]}
355 local right=${d[-1]}
356
357 if ! diff $left $right; then
358 die "Benchmarks were run on different files ($left != $right)"
359 fi
360
361 # They are the same, output one of them.
362 cat $left > $lines_csv
363 fi
364
365 local times_csv=$out/times.csv
366 csv-concat "${raw[@]}" > $times_csv
367
368 head $out/*
369 wc -l $out/*
370}
371
372# TODO:
373# - maybe rowspan for hosts: flanders/lenny
374# - does that interfere with sorting?
375#
376# NOTE: not bothering to make it sortable now. Just using the CSS.
377
378print-report() {
379 local in_dir=$1
380
381 benchmark-html-head 'OSH Parser Performance'
382
383 cat <<EOF
384 <body class="width60">
385 <p id="home-link">
386 <a href="/">oils.pub</a>
387 </p>
388EOF
389
390 cmark <<'EOF'
391## OSH Parser Performance
392
393We time `$sh -n $file` for various files under various shells, and repeat then
394run under cachegrind for stable metrics.
395
396Source code: [oil/benchmarks/osh-parser.sh](https://github.com/oilshell/oil/tree/master/benchmarks/osh-parser.sh)
397
398[Raw files](-wwz-index)
399
400### Summary
401
402#### Instructions Per Line (via cachegrind)
403
404Lower numbers are generally better, but each shell recognizes a different
405language, and OSH uses a more thorough parsing algorithm. In **thousands** of
406"I refs".
407
408EOF
409 tsv2html $in_dir/cachegrind_summary.tsv
410
411 cmark <<'EOF'
412
413(zsh isn't measured because `zsh -n` unexpectedly forks.)
414
415#### Average Parsing Rate, Measured on Two Machines (lines/ms)
416
417Shell startup time is included in the elapsed time measurements, but long files
418are chosen to minimize its effect.
419EOF
420 csv2html $in_dir/summary.csv
421
422 cmark <<< '### Per-File Measurements'
423 echo
424
425 # Flat tables for CI
426 if test -f $in_dir/times_flat.tsv; then
427 cmark <<< '#### Time and Memory'
428 echo
429
430 tsv2html $in_dir/times_flat.tsv
431 fi
432 if test -f $in_dir/cachegrind_flat.tsv; then
433 cmark <<< '#### Instruction Counts'
434 echo
435
436 tsv2html $in_dir/cachegrind_flat.tsv
437 fi
438
439 # Breakdowns for release
440 if test -f $in_dir/instructions.tsv; then
441 cmark <<< '#### Instructions Per Line (in thousands)'
442 echo
443 tsv2html $in_dir/instructions.tsv
444 fi
445
446 if test -f $in_dir/elapsed.csv; then
447 cmark <<< '#### Elapsed Time (milliseconds)'
448 echo
449 csv2html $in_dir/elapsed.csv
450 fi
451
452 if test -f $in_dir/rate.csv; then
453 cmark <<< '#### Parsing Rate (lines/ms)'
454 echo
455 csv2html $in_dir/rate.csv
456 fi
457
458 if test -f $in_dir/max_rss.csv; then
459 cmark <<'EOF'
460### Memory Usage (Max Resident Set Size in MB)
461
462Again, OSH uses a **different algorithm** (and language) than POSIX shells. It
463builds an AST in memory rather than just validating the code line-by-line.
464
465EOF
466 csv2html $in_dir/max_rss.csv
467 fi
468
469 cmark <<EOF
470### Shell and Host Details
471EOF
472 csv2html $in_dir/shells.csv
473 csv2html $in_dir/hosts.csv
474
475 cmark <<EOF
476### Raw Data
477EOF
478 csv2html $in_dir/raw-data.csv
479
480 cmark << 'EOF'
481
482 </body>
483</html>
484EOF
485}
486
487soil-run() {
488 ### Run it on just this machine, and make a report
489
490 rm -r -f $BASE_DIR
491 mkdir -p $BASE_DIR
492
493 local -a osh_bin=( $OSH_CPP_NINJA_BUILD $OSH_SOUFFLE_CPP_NINJA_BUILD )
494 ninja "${osh_bin[@]}"
495
496 local single_machine='no-host'
497
498 local job_id
499 job_id=$(benchmarks/id.sh print-job-id)
500
501 benchmarks/id.sh shell-provenance-2 \
502 $single_machine $job_id _tmp \
503 bash dash bin/osh "${osh_bin[@]}"
504
505 # TODO: measure* should use print-tasks | run-tasks
506 local provenance=_tmp/provenance.txt
507 local host_job_id="$single_machine.$job_id"
508
509 measure $provenance $host_job_id '' $OSH_CPP_NINJA_BUILD $OSH_SOUFFLE_CPP_NINJA_BUILD
510
511 measure-cachegrind $provenance $host_job_id '' $OSH_CPP_NINJA_BUILD $OSH_SOUFFLE_CPP_NINJA_BUILD
512
513 # TODO: R can use this TSV file
514 cp -v _tmp/provenance.tsv $BASE_DIR/stage1/provenance.tsv
515
516 # Trivial concatenation for 1 machine
517 stage1 '' $single_machine
518
519 benchmarks/report.sh stage2 $BASE_DIR
520
521 benchmarks/report.sh stage3 $BASE_DIR
522}
523
524"$@"