OILS / benchmarks / compute.sh View on Github | oilshell.org

614 lines, 305 significant
1#!/usr/bin/env bash
2#
3# Compare operations on data structures, with little I/O: strings, array,
4# associative arrays, integers.
5#
6# Usage:
7# benchmarks/compute.sh <function name>
8#
9# List of benchmarks:
10#
11# - fib: integer, loop, assignment (shells don't have real integers
12# - word_freq: hash table / assoc array (OSH uses a vector<pair<>> now!)
13# also integer counter
14# - bubble_sort: indexed array (bash uses a linked list?)
15# - palindrome: string, slicing, unicode
16# - parse_help: realistic shell-only string processing, which I didn't write.
17#
18# TODO:
19# - vary problem size, which is different than iters
20# - bubble sort: array length, to test complexity of array indexing
21# - palindrome: longer lines, to test complexity of unicode/byte slicing
22# - word_freq: more unique words, to test complexity of assoc array
23# - write awk versions of each benchmark (could be contributed)
24# - assert that stdout is identical
25# - create data frames and publish results
26# - leave holes for Python, other shells, etc.
27
28set -o nounset
29set -o pipefail
30set -o errexit
31
32REPO_ROOT=$(cd $(dirname $0)/.. && pwd)
33readonly REPO_ROOT
34
35source benchmarks/common.sh # filter-provenance
36source test/tsv-lib.sh # tsv2html
37
38readonly BASE_DIR=_tmp/compute
39
40# Stabilize 'sort' output across machines (ugh locales!)
41export LC_ALL=C
42
43TIMEFORMAT='%U'
44
45# task_name,iter,args
46hello-tasks() {
47 local provenance=$1
48
49 # Add 1 field for each of 5 fields.
50 cat $provenance | filter-provenance python2 bash dash "$OSH_CPP_REGEX" |
51 while read fields; do
52 echo 'hello _ _' | xargs -n 3 -- echo "$fields"
53 done
54}
55
56# task_name,iter,args
57fib-tasks() {
58 local provenance=$1
59
60 # Add 1 field for each of 5 fields.
61 cat $provenance | filter-provenance python2 bash dash "$OSH_CPP_REGEX" |
62 while read fields; do
63 echo 'fib 200 44' | xargs -n 3 -- echo "$fields"
64 done
65}
66
67word_freq-tasks() {
68 local provenance=$1
69
70 cat $provenance | filter-provenance python2 bash "$OSH_CPP_REGEX" |
71 while read fields; do
72 # BUG: oils-for-unix differs on these two. Looks like it's related to
73 # backslashes!
74 #echo 'word_freq 10 benchmarks/testdata/abuild' | xargs -n 3 -- echo "$fields"
75 #echo 'word_freq 2 benchmarks/testdata/ltmain.sh' | xargs -n 3 -- echo "$fields"
76 echo 'word_freq 10 configure' | xargs -n 3 -- echo "$fields"
77 done
78}
79
80assoc_array-tasks() {
81 local provenance=$1
82
83 cat $provenance | filter-provenance python2 bash "$OSH_CPP_REGEX" |
84 while read fields; do
85 for n in 1000 2000 3000; do
86 echo "word_freq 10 $n" | xargs -n 3 -- echo "$fields"
87 done
88 done
89}
90
91bubble_sort-tasks() {
92 # Note: this is quadratic, but bubble sort itself is quadratic!
93 local provenance=$1
94
95 cat $provenance | filter-provenance python2 bash "$OSH_CPP_REGEX" |
96 while read fields; do
97 echo 'bubble_sort int 200' | xargs -n 3 -- echo "$fields"
98 echo 'bubble_sort bytes 200' | xargs -n 3 -- echo "$fields"
99 done
100}
101
102# Arrays are doubly linked lists in bash! With a LASTREF hack to avoid being
103# quadratic.
104#
105# See array_reference() in array.c in bash. It searches both back and
106# forward. Every cell has its index, a value, a forward pointer, and a back
107# pointer.
108#
109# You need pretty high N to see the quadratic behavior though!
110
111# NOTE: osh is also slower with linear access, but not superlinear!
112
113array_ref-tasks() {
114 local provenance=$1
115
116 cat $provenance | filter-provenance bash |
117 while read fields; do
118 for mode in seq random; do
119 for n in 10000 20000 30000 40000; do
120 echo "array_ref $mode $n" | xargs -n 3 -- echo "$fields"
121 done
122 done
123 done
124
125#array_ref $OSH_CC seq 5000
126#array_ref $OSH_CC seq 10000
127#array_ref $OSH_CC random 5000
128#array_ref $OSH_CC random 10000
129#EOF
130}
131
132palindrome-tasks() {
133 local provenance=$1
134
135 cat $provenance | filter-provenance python2 bash "$OSH_CPP_REGEX" |
136 while read fields; do
137 echo 'palindrome unicode _' | xargs -n 3 -- echo "$fields"
138 echo 'palindrome bytes _' | xargs -n 3 -- echo "$fields"
139 done
140}
141
142parse_help-tasks() {
143 local provenance=$1
144
145 cat $provenance | filter-provenance bash "$OSH_CPP_REGEX" |
146 while read fields; do
147 echo 'parse_help ls-short _' | xargs -n 3 -- echo "$fields"
148 echo 'parse_help ls _' | xargs -n 3 -- echo "$fields"
149 echo 'parse_help mypy _' | xargs -n 3 -- echo "$fields"
150 done
151}
152
153ext() {
154 local ext
155 case $runtime in
156 (python2)
157 echo 'py'
158 ;;
159 (*sh | *osh*)
160 echo 'sh'
161 ;;
162 esac
163}
164
165word_freq-one() {
166 ### Run one word_freq task (hash tables)
167
168 local name=${1:-word_freq}
169 local runtime=$2
170
171 local iters=${3:-10}
172 local in=${4:-configure} # input
173
174 $runtime benchmarks/compute/word_freq.$(ext $runtime) $iters < $in | sort -n
175}
176
177assoc_array-one() {
178 ### Run word_freq with seq
179
180 local name=${1:-word_freq}
181 local runtime=$2
182
183 local iters=${3:-10}
184 local n=${4:-10}
185
186 # shuf so we don't get the bash optimization
187 seq $n | shuf |
188 $runtime benchmarks/compute/word_freq.$(ext $runtime) $iters | sort -n
189}
190
191bubble_sort-one() {
192 ### Run one bubble_sort task (arrays)
193
194 local name=${1:-bubble_sort}
195 local runtime=$2
196 local mode=${3:-int}
197 local n=${4:-100}
198
199 $runtime benchmarks/compute/bubble_sort.$(ext $runtime) $mode \
200 < $BASE_DIR/tmp/$name/testdata-$n.txt
201}
202
203# OSH is like 10x faster here!
204array_ref-one() {
205 ### Run one array_ref task (arrays)
206
207 local name=${1:-bubble_sort}
208 local runtime=$2
209 local mode=${3:-seq}
210 local n=${4:-100}
211
212 seq $n | shuf | $runtime benchmarks/compute/array_ref.$(ext $runtime) $mode
213}
214
215palindrome-one() {
216 ### Run one palindrome task (strings)
217
218 local name=${1:-palindrome}
219 local runtime=$2
220 local mode=${3:-unicode}
221
222 $runtime benchmarks/compute/palindrome.$(ext $runtime) $mode \
223 < $BASE_DIR/tmp/$name/testdata.txt
224}
225
226parse_help-one() {
227 ### Run one palindrome task (strings, real code)
228
229 local name=${1:-parse_help}
230 local runtime=$2
231 local workload=${3:-}
232
233 $runtime benchmarks/parse-help/pure-excerpt.sh _parse_help - \
234 < benchmarks/parse-help/$workload.txt
235}
236
237#
238# Helpers
239#
240
241hello-all() { task-all hello "$@"; }
242fib-all() { task-all fib "$@"; }
243word_freq-all() { task-all word_freq "$@"; }
244assoc_array-all() { task-all assoc_array "$@"; }
245
246# TODO: Fix the OSH comparison operator! It gives the wrong answer and
247# completes quickly.
248bubble_sort-all() { task-all bubble_sort "$@"; }
249
250# Array that is not quadratic
251array_ref-all() { task-all array_ref "$@"; }
252
253# Hm osh is a little slower here
254palindrome-all() { task-all palindrome "$@"; }
255
256parse_help-all() { task-all parse_help "$@"; }
257
258task-all() {
259 local task_name=$1
260 local provenance=$2
261 local host_job_id=$3
262 local out_dir=$4 # put files to save in benchmarks-data repo here
263
264 local tmp_dir=$BASE_DIR/tmp/$task_name
265
266 local times_tsv=$out_dir/$task_name/$host_job_id.times.tsv
267 rm -f $times_tsv
268
269 mkdir -p $tmp_dir $out_dir/$task_name
270
271 # header
272 tsv-row \
273 status elapsed_secs user_secs sys_secs max_rss_KiB \
274 stdout_md5sum \
275 host_name host_hash \
276 runtime_name runtime_hash \
277 task_name arg1 arg2 stdout_filename > $times_tsv
278
279 local task_id=0
280
281 ${task_name}-tasks $provenance > $tmp_dir/tasks.txt
282
283 cat $tmp_dir/tasks.txt |
284 while read _ host host_hash runtime runtime_hash _ arg1 arg2; do
285 local file
286 case $runtime in
287 (python2)
288 file='py'
289 ;;
290 (*sh | *osh*)
291 file=$(basename $runtime)
292 ;;
293 esac
294
295 #log "runtime=$runtime args=$args"
296
297 local stdout_filename="stdout-$file-$arg1-$(basename $arg2).txt"
298
299 # Measurement BUG! This makes dash have the memory usage of bash!
300 # It's better to get argv into the shell.
301
302 local -a cmd
303 case $task_name in
304 (hello|fib)
305 # Run it DIRECTLY, do not run $0. Because we do NOT want to fork bash
306 # then dash, because bash uses more memory.
307 cmd=($runtime benchmarks/compute/$task_name.$(ext $runtime) "$arg1" "$arg2")
308 ;;
309 (*)
310 cmd=($0 ${task_name}-one "$task_name" "$runtime" "$arg1" "$arg2")
311 ;;
312 esac
313
314 # join args into a single field
315 time-tsv -o $times_tsv --append \
316 --stdout $tmp_dir/$stdout_filename \
317 --rusage \
318 --field "$host" --field "$host_hash" \
319 --field $runtime --field $runtime_hash \
320 --field "$task_name" --field "$arg1" --field "$arg2" \
321 --field "$stdout_filename" -- \
322 "${cmd[@]}"
323
324 task_id=$((task_id + 1))
325 done
326
327 #wc -l _tmp/compute/word_freq/*
328 maybe-tree $tmp_dir
329 cat $times_tsv
330}
331
332#
333# Testdata
334#
335
336bubble_sort-testdata() {
337 local out=$BASE_DIR/tmp/bubble_sort
338 mkdir -p $out
339
340 # TODO: Make these deterministic for more stable benchmarks?
341 for n in 100 200 300 400; do
342 seq $n | shuf > $out/testdata-$n.txt
343 done
344
345 wc -l $out/testdata-*.txt
346}
347
348palindrome-testdata() {
349 local out=$BASE_DIR/tmp/palindrome
350 mkdir -p $out
351
352 # TODO: Use iters?
353
354 for i in $(seq 500); do
355 cat <<EOF
356foo
357a
358tat
359cat
360
361noon
362amanaplanacanalpanama
363
364μ
365-μ-
366EOF
367
368 done > $out/testdata.txt
369
370 wc -l $out/testdata.txt
371}
372
373measure() {
374 local provenance=$1
375 local host_job_id=$2
376 local out_dir=${3:-$BASE_DIR/raw} # ../benchmark-data/compute
377
378 mkdir -p $BASE_DIR/{tmp,raw,stage1} $out_dir
379
380 # set -x
381 hello-all $provenance $host_job_id $out_dir
382 fib-all $provenance $host_job_id $out_dir
383
384 # TODO: doesn't work because we would need duplicate logic in stage1
385 #if test -n "${QUICKLY:-}"; then
386 # return
387 #fi
388
389 word_freq-all $provenance $host_job_id $out_dir
390 parse_help-all $provenance $host_job_id $out_dir
391
392 bubble_sort-testdata
393 palindrome-testdata
394
395 bubble_sort-all $provenance $host_job_id $out_dir
396
397 # INCORRECT, but still run it
398 palindrome-all $provenance $host_job_id $out_dir
399
400 # array_ref takes too long to show quadratic behavior, and that's only
401 # necessary on 1 machine. I think I will make a separate blog post,
402 # if anything.
403
404 maybe-tree $out_dir
405}
406
407soil-run() {
408 ### Run it on just this machine, and make a report
409
410 rm -r -f $BASE_DIR
411 mkdir -p $BASE_DIR
412
413 # Test the one that's IN TREE, NOT in ../benchmark-data
414 local -a osh_bin=( $OSH_CPP_NINJA_BUILD _bin/cxx-opt+bumpleak/osh)
415 ninja "${osh_bin[@]}"
416
417 local single_machine='no-host'
418
419 local job_id
420 job_id=$(benchmarks/id.sh print-job-id)
421
422 # Only measure what's in the Docker image
423 # - The Soil 'benchmarks' job uses the 'cpp' Docker image, which doesn't have
424 # layer-cpython, ../oil_DEPS/cpython-full
425 # - It also doesn't have mksh or zsh
426
427 benchmarks/id.sh shell-provenance-2 \
428 $single_machine $job_id _tmp \
429 bash dash python2 "${osh_bin[@]}"
430
431 local provenance=_tmp/provenance.txt
432 local host_job_id="$single_machine.$job_id"
433
434 measure $provenance $host_job_id
435
436 # Make it run on one machine
437 stage1 '' $single_machine
438
439 benchmarks/report.sh stage2 $BASE_DIR
440 benchmarks/report.sh stage3 $BASE_DIR
441}
442
443
444test-report() {
445 # Make it run on one machine
446 stage1 '' no-host
447
448 benchmarks/report.sh stage2 $BASE_DIR
449 benchmarks/report.sh stage3 $BASE_DIR
450}
451
452stage1() {
453 local raw_dir=${1:-$BASE_DIR/raw}
454
455 # This report works even if we only have one machine
456 local single_machine=${2:-}
457
458 local out_dir=$BASE_DIR/stage1
459 mkdir -p $out_dir
460
461 local times_tsv=$out_dir/times.tsv
462
463 local -a raw=()
464
465 # TODO: We should respect QUICKLY=1
466 for metric in hello fib word_freq parse_help bubble_sort palindrome; do
467 local dir=$raw_dir/$metric
468
469 if test -n "$single_machine"; then
470 local -a a=($dir/$single_machine.*.times.tsv)
471 raw+=(${a[-1]})
472 else
473 # Globs are in lexicographical order, which works for our dates.
474 local -a a=($dir/$MACHINE1.*.times.tsv)
475 local -a b=($dir/$MACHINE2.*.times.tsv) # HACK for now
476
477 # take the latest file
478 raw+=(${a[-1]} ${b[-1]})
479 fi
480
481 done
482 csv-concat ${raw[@]} > $times_tsv
483 wc -l $times_tsv
484}
485
486print-report() {
487 local in_dir=$1
488
489 benchmark-html-head 'OSH Compute Performance'
490
491 cat <<EOF
492 <body class="width60">
493 <p id="home-link">
494 <a href="/">oilshell.org</a>
495 </p>
496EOF
497 cmark <<EOF
498
499## OSH Compute Performance
500
501Running time and memory usage of programs that test data structures (as opposed
502to I/O).
503
504Memory usage is measured in MB (powers of 10), not MiB (powers of 2).
505
506Source code: [oil/benchmarks/compute](https://github.com/oilshell/oil/tree/master/benchmarks/compute)
507
508EOF
509
510 cmark <<EOF
511### hello (minimal startup)
512
513EOF
514
515 tsv2html $in_dir/hello.tsv
516
517 cmark <<EOF
518### fibonacci (integers)
519
520- arg1: number of repetitions
521- arg2: the N in fib(N)
522EOF
523
524 tsv2html $in_dir/fib.tsv
525
526 cmark <<EOF
527### word_freq (associative arrays / hash tables)
528
529- arg1: number of repetitions
530- arg2: the file (varies size of hash table)
531EOF
532
533 tsv2html $in_dir/word_freq.tsv
534
535 cmark <<EOF
536### parse_help (strings, real code)
537
538- arg1: file to parse
539EOF
540
541 tsv2html $in_dir/parse_help.tsv
542
543 cmark <<EOF
544### bubble_sort (array of integers, arrays of strings)
545
546- arg1: type of array
547- arg2: length of array
548EOF
549
550 tsv2html $in_dir/bubble_sort.tsv
551
552 # Comment out until checksum is fixed
553
554if false; then
555 cmark <<EOF
556### palindrome (byte strings, unicode strings)
557
558- arg1: type of string
559- arg2: TODO: length of string
560EOF
561
562 tsv2html $in_dir/palindrome.tsv
563
564fi
565
566 cmark <<EOF
567### Interpreter and Host Details
568EOF
569
570 tsv2html $in_dir/shells.tsv
571 tsv2html $in_dir/hosts.tsv
572
573 cmark <<EOF
574### Details
575EOF
576
577 tsv2html $in_dir/details.tsv
578
579 cmark <<EOF
580### Stdout Files
581EOF
582
583 tsv2html $in_dir/stdout_files.tsv
584
585
586 cat <<EOF
587 </body>
588</html>
589EOF
590}
591
592
593control-flow() {
594 local osh=_bin/cxx-opt/osh
595 #set -x
596
597 ninja $osh
598
599 # do_neither: dash 296 ms, bash 922, osh 993. Not bad
600 #
601
602 for func in do_neither do_continue do_break; do
603 echo "=== $func"
604 echo
605 for sh in dash bash $osh; do
606 echo "--- $sh"
607 # TIMEFORMAT above
608 time $sh benchmarks/compute/control_flow.sh $func 500
609 echo
610 done
611 done
612}
613
614"$@"