441 lines
16 KiB
Bash
Executable File
441 lines
16 KiB
Bash
Executable File
#!/usr/bin/env bash
|
|
#
|
|
# std.sh — shared "standard library" for the fastwc benchmark scripts.
|
|
#
|
|
# Every benchmark script lives in its own directory (benchmarks/files/words,
|
|
# benchmarks/files/lines, benchmarks/stdin/piping) and sets two variables
|
|
# before sourcing this file:
|
|
# SCRIPT_DIR — the benchmark script's own directory (test data lives here)
|
|
# REPO_DIR — the repository root (release binary and tools live here)
|
|
#
|
|
# Provides the helpers every benchmark script needs:
|
|
# checkfastwc() verify a release build of fastwc exists
|
|
# checkwc() locate the coreutils wc implementation
|
|
# createtxt() create (or reuse) a text file with N such lines
|
|
# timeit() run a command once, print elapsed wall time in µs
|
|
# capture_count() print the first whitespace-separated field of output
|
|
# run_case() race fastwc against the reference on a file argument
|
|
# run_stdin_case() same, but feeding the file through standard input
|
|
# run_solo_case() time fastwc alone (no reference) and print throughput
|
|
# run_cases() run run_case for a list of sizes, fail-fast
|
|
# run_stdin_cases() run run_stdin_case for a list of sizes, fail-fast
|
|
# write_failed_report() write the human readable failure report
|
|
#
|
|
# The suites fail fast: the moment fastwc is slower than (or disagrees
|
|
# with) the reference wc, a human readable report is written to
|
|
# FAILED-benchmark.txt next to the suite and it returns non-zero.
|
|
|
|
set -u
|
|
|
|
# Pin the C locale: GNU wc -w silently switches to multibyte decoding under a
|
|
# UTF-8 locale, which would slow the oracle down and mask the documented
|
|
# byte-semantics divergence. Both sides count bytes here.
|
|
export LC_ALL=C
|
|
export LC_CTYPE=C
|
|
|
|
FASTWC="$REPO_DIR/bin/release/fastwc"
|
|
DATA_DIR="$SCRIPT_DIR/.data"
|
|
GENFILE="$REPO_DIR/benchmarks/tools/genfile" # optional C helper, built by test-all.sh
|
|
TIMEIT="$REPO_DIR/benchmarks/tools/timeit" # µs exec timer, built by test-all.sh
|
|
|
|
BENCH_NAME="${BENCH_NAME:-wc}" # set by the caller: coreutils
|
|
BENCH_REPS="${BENCH_REPS:-3}" # interleaved runs per case; minimum is kept
|
|
# A reference wc that finishes under this many µs was really measuring
|
|
# startup, not throughput. Those cases are checked for correctness and
|
|
# reported, but excluded from the averages (see finish_race).
|
|
RACE_FLOOR_US="${RACE_FLOOR_US:-5000}"
|
|
RESULT_ROWS="" # accumulated results table
|
|
|
|
# Per-case speedup ratios accumulate here so the run can end with the
|
|
# average speedup per oracle. test-all.sh overrides this with a shared
|
|
# temp file so every suite feeds the same average; a standalone suite
|
|
# run gets its own file ($$ differs per process).
|
|
: "${RATIOS_FILE:=/tmp/fastwc-ratios-$$.tsv}"
|
|
|
|
WC_CMD=() # filled by checkwc/select_oracle
|
|
TEXT_FILE="" # filled by createtxt()
|
|
|
|
if [[ -z "$BENCH_REPS" || "$BENCH_REPS" -lt 1 ]]; then
|
|
BENCH_REPS=1
|
|
fi
|
|
|
|
# checkfastwc — make sure the release build exists and is executable.
|
|
checkfastwc() {
|
|
printf 'checking for release build fastwc... '
|
|
if [[ -x "$FASTWC" ]]; then
|
|
printf 'yes\n'
|
|
return 0
|
|
fi
|
|
printf 'no\n'
|
|
printf 'configure: error: no release build of fastwc found at %s\n' "$FASTWC" >&2
|
|
printf 'configure: error: run "make release" first to generate one\n' >&2
|
|
exit 1
|
|
}
|
|
|
|
# wc_impl <cmd...> — identify a wc implementation from its --version
|
|
# answer. coreutils, fastwc and toybox respond to --version; busybox
|
|
# does not have the option and names itself in the error it prints
|
|
# instead.
|
|
wc_impl() {
|
|
local out
|
|
out=$("$@" --version 2>&1)
|
|
case "$out" in
|
|
*'GNU coreutils'*) printf 'coreutils\n' ;;
|
|
fastwc*) printf 'fastwc\n' ;;
|
|
toybox*) printf 'toybox\n' ;;
|
|
*BusyBox*) printf 'busybox\n' ;;
|
|
*) printf 'unknown\n' ;;
|
|
esac
|
|
}
|
|
|
|
# checkwc — locate the wc implementations to race against. Walks PATH
|
|
# for every wc binary and identifies each by its --version answer. A wc
|
|
# that answers as fastwc is a symlink somebody made to our own binary —
|
|
# people do symlink wc to fastwc — and is skipped, because racing
|
|
# ourselves proves nothing. Busybox and toybox usually exist only as the
|
|
# multi-call binaries, so those are probed too; they are back in the
|
|
# suite for shits and giggles, not because they are a challenge.
|
|
# Sets COREUTILS_CMD, BUSYBOX_CMD, TOYBOX_CMD (empty if absent) and
|
|
# ORACLES, and points WC_CMD at coreutils. Exits if no coreutils wc is
|
|
# found.
|
|
checkwc() {
|
|
local dir impl
|
|
COREUTILS_CMD=()
|
|
BUSYBOX_CMD=()
|
|
TOYBOX_CMD=()
|
|
ORACLES=''
|
|
|
|
printf 'locating wc implementations... '
|
|
for dir in ${PATH//:/ }; do
|
|
[[ -n "$dir" && -x "$dir/wc" ]] || continue
|
|
impl=$(wc_impl "$dir/wc")
|
|
case "$impl" in
|
|
coreutils)
|
|
if [[ ${#COREUTILS_CMD[@]} -eq 0 ]]; then
|
|
COREUTILS_CMD=("$dir/wc")
|
|
printf 'coreutils %s; ' \
|
|
"$("$dir/wc" --version | head -n1 | sed 's/^wc (GNU coreutils) //')"
|
|
fi
|
|
;;
|
|
fastwc)
|
|
printf 'warning: %s is a fastwc symlink; skipping as oracle\n' \
|
|
"$dir/wc" >&2
|
|
;;
|
|
busybox)
|
|
if [[ ${#BUSYBOX_CMD[@]} -eq 0 ]]; then
|
|
BUSYBOX_CMD=("$dir/wc")
|
|
printf 'busybox; '
|
|
fi
|
|
;;
|
|
toybox)
|
|
if [[ ${#TOYBOX_CMD[@]} -eq 0 ]]; then
|
|
TOYBOX_CMD=("$dir/wc")
|
|
printf 'toybox; '
|
|
fi
|
|
;;
|
|
*) ;;
|
|
esac
|
|
done
|
|
|
|
# busybox is commonly installed as the multi-call binary only
|
|
if [[ ${#BUSYBOX_CMD[@]} -eq 0 ]] && command -v busybox >/dev/null 2>&1 \
|
|
&& [[ "$(wc_impl busybox wc)" == 'busybox' ]]; then
|
|
BUSYBOX_CMD=(busybox wc)
|
|
printf 'busybox; '
|
|
fi
|
|
|
|
# same for toybox
|
|
if [[ ${#TOYBOX_CMD[@]} -eq 0 ]] && command -v toybox >/dev/null 2>&1 \
|
|
&& [[ "$(wc_impl toybox wc)" == 'toybox' ]]; then
|
|
TOYBOX_CMD=(toybox wc)
|
|
printf 'toybox; '
|
|
fi
|
|
|
|
if [[ ${#COREUTILS_CMD[@]} -eq 0 ]]; then
|
|
printf 'none\n'
|
|
printf 'configure: error: no coreutils wc found in PATH\n' >&2
|
|
printf 'configure: error: if you symlinked wc to fastwc, point PATH at a real coreutils first\n' >&2
|
|
exit 1
|
|
fi
|
|
printf '\n'
|
|
|
|
WC_CMD=("${COREUTILS_CMD[@]}")
|
|
ORACLES='coreutils'
|
|
[[ ${#BUSYBOX_CMD[@]} -gt 0 ]] && ORACLES="$ORACLES busybox"
|
|
[[ ${#TOYBOX_CMD[@]} -gt 0 ]] && ORACLES="$ORACLES toybox"
|
|
}
|
|
|
|
# select_oracle <coreutils|busybox|toybox> — point the racing functions
|
|
# at the chosen oracle by setting BENCH_NAME and WC_CMD.
|
|
select_oracle() {
|
|
case "$1" in
|
|
coreutils) BENCH_NAME='coreutils'; WC_CMD=("${COREUTILS_CMD[@]}") ;;
|
|
busybox) BENCH_NAME='busybox'; WC_CMD=("${BUSYBOX_CMD[@]}") ;;
|
|
toybox) BENCH_NAME='toybox'; WC_CMD=("${TOYBOX_CMD[@]}") ;;
|
|
*) return 1 ;;
|
|
esac
|
|
return 0
|
|
}
|
|
|
|
# createrandstr — print one random 10-character alphanumeric string.
|
|
createrandstr() {
|
|
local chars='abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789'
|
|
local out='' i
|
|
for ((i = 0; i < 10; i++)); do
|
|
out+="${chars:$((RANDOM % ${#chars})):1}"
|
|
done
|
|
printf '%s\n' "$out"
|
|
}
|
|
|
|
# createtxt <lines> — make sure a text file with <lines> rows of random
|
|
# 10-character alphanumeric strings exists in this suite's .data directory.
|
|
# A copy generated by a previous run is reused (checked by exact byte size:
|
|
# 10 chars + '\n' per line), so repeated benchmark runs are cheap.
|
|
# Prints the path and sets $TEXT_FILE; returns non-zero if generation fails.
|
|
createtxt() {
|
|
local lines="$1"
|
|
local expect=$((lines * 11))
|
|
local have=0
|
|
|
|
TEXT_FILE="$DATA_DIR/words-$lines.txt"
|
|
|
|
if [[ -f "$TEXT_FILE" ]]; then
|
|
have=$(stat -c '%s' "$TEXT_FILE" 2>/dev/null || printf '0')
|
|
fi
|
|
|
|
if [[ "$have" -ne "$expect" ]]; then
|
|
mkdir -p "$DATA_DIR"
|
|
if [[ -x "$GENFILE" ]]; then
|
|
"$GENFILE" "$lines" > "$TEXT_FILE" || {
|
|
printf 'createtxt: error: failed to generate %s\n' "$TEXT_FILE" >&2
|
|
return 1
|
|
}
|
|
else
|
|
printf 'createtxt: warning: %s not built, using slow shell fallback\n' "$GENFILE" >&2
|
|
printf 'createtxt: warning: run ./test-all.sh to build the helper tools\n' >&2
|
|
: > "$TEXT_FILE"
|
|
for ((i = 0; i < lines; i++)); do
|
|
createrandstr >> "$TEXT_FILE"
|
|
done
|
|
fi
|
|
fi
|
|
|
|
printf '%s\n' "$TEXT_FILE"
|
|
}
|
|
|
|
# timeit <cmd...> — run a command once and print elapsed wall time in µs
|
|
# on stdout, with the command's own output discarded. The clock starts in
|
|
# main(), after timeit's own loader has run, so every binary pays the same
|
|
# bookkeeping and the reading is the child's fork + exec + run + exit.
|
|
timeit() {
|
|
[[ -x "$TIMEIT" ]] || {
|
|
printf 'error: %s not built — run test-all.sh (or "make bench") first\n' \
|
|
"$TIMEIT" >&2
|
|
exit 1
|
|
}
|
|
"$TIMEIT" "$@"
|
|
}
|
|
|
|
# capture_count <cmd...> — print the first whitespace-separated field of a
|
|
# command's output, i.e. the count reported by `wc -w/-l` or `fastwc -w/-l`.
|
|
capture_count() {
|
|
"$@" 2>/dev/null | awk 'NR == 1 { print $1 }'
|
|
}
|
|
|
|
# write_failed_report <label> <reason> <wc_us> <fast_us> — write the
|
|
# human readable failure report to FAILED-benchmark.txt next to the suite.
|
|
write_failed_report() {
|
|
local label="$1" reason="$2" wc_us="$3" fast_us="$4"
|
|
local report="$SCRIPT_DIR/FAILED-benchmark.txt"
|
|
|
|
{
|
|
printf 'fastwc benchmark FAILED\n'
|
|
printf '=======================\n'
|
|
printf 'implementation : %s wc\n' "$BENCH_NAME"
|
|
printf 'failed test : %s\n' "$label"
|
|
printf 'failure : %s\n' "$reason"
|
|
printf '\nresults\n'
|
|
printf '%s\n' '-------'
|
|
printf '%-28s %16s %24s %8s %s\n' 'test' 'wc' 'fastwc (µs)' 'ratio' 'status'
|
|
printf '%s' "$RESULT_ROWS"
|
|
printf '\nfastwc must never be slower than %s wc — benchmark aborted.\n' "$BENCH_NAME"
|
|
} > "$report"
|
|
|
|
printf '\nbenchmark FAILED (%s): %s\n' "$BENCH_NAME" "$reason" >&2
|
|
printf 'full results written to %s\n' "$report" >&2
|
|
}
|
|
|
|
# finish_race <label> <wc_count> <fast_count> <wc_us> <fast_us> — turn the
|
|
# measured counts and times into a verdict. A count mismatch fails
|
|
# outright. A reference that finished under RACE_FLOOR_US was really
|
|
# measuring startup, not throughput: the case is reported as PASS
|
|
# (startup-bound) and left out of the averages. Raced cases pass when
|
|
# fastwc is not slower than the reference beyond a small dead-heat slack
|
|
# (200µs + 2%) that absorbs scheduler jitter on genuinely even races.
|
|
finish_race() {
|
|
local label="$1" wc_count="$2" fast_count="$3" wc_us="$4" fast_us="$5"
|
|
local ratio='-' verdict='PASS' reason='' row slack
|
|
|
|
if [[ "$fast_count" != "$wc_count" ]]; then
|
|
verdict='FAIL'
|
|
reason="output mismatch (fastwc: ${fast_count}, ${BENCH_NAME} wc: ${wc_count})"
|
|
elif (( wc_us < RACE_FLOOR_US )); then
|
|
verdict='PASS (startup-bound)'
|
|
else
|
|
ratio=$(awk -v f="$fast_us" -v w="$wc_us" 'BEGIN { printf "%.2fx", w / f }')
|
|
# feed the end-of-run average speedup (raced rows only)
|
|
printf '%s\t%s\n' "$BENCH_NAME" "${ratio%x}" >> "$RATIOS_FILE"
|
|
slack=$((200 + wc_us / 50))
|
|
if (( fast_us > wc_us + slack )); then
|
|
verdict='FAIL'
|
|
reason="fastwc was slower (fastwc: ${fast_us}µs vs ${BENCH_NAME} wc: ${wc_us}µs)"
|
|
fi
|
|
fi
|
|
|
|
row=$(printf '%-28s %16s %24s %8s %s\n' \
|
|
"$label" "wc: ${wc_us}µs" "fastwc: ${fast_us}µs" "$ratio" "$verdict")
|
|
RESULT_ROWS+="${row}"$'\n'
|
|
printf '%s\n' "$row"
|
|
|
|
if [[ "$verdict" == 'FAIL' ]]; then
|
|
write_failed_report "$label" "$reason" "$wc_us" "$fast_us"
|
|
return 1
|
|
fi
|
|
return 0
|
|
}
|
|
|
|
# run_case <words|lines> <n-lines> <-w|-l> — race the reference wc against
|
|
# fastwc on a file argument. Fails the benchmark the moment fastwc is
|
|
# slower or reports a different count.
|
|
run_case() {
|
|
local mode="$1" lines="$2" flag="$3"
|
|
local noun='lines'; [[ "$lines" -eq 1 ]] && noun='line'
|
|
local label="${mode} (${lines} ${noun})"
|
|
local file wc_count fast_count wc_us fast_us
|
|
local i d
|
|
|
|
file=$(createtxt "$lines") || return 1
|
|
|
|
# correctness: fastwc must report the same count as the reference wc
|
|
wc_count=$(capture_count "${WC_CMD[@]}" "$flag" "$file")
|
|
fast_count=$(capture_count "$FASTWC" "$flag" "$file")
|
|
|
|
# speed: interleaved timing so both commands see identical cache
|
|
# warmth; keep the minimum of $BENCH_REPS runs each
|
|
wc_us=''
|
|
fast_us=''
|
|
for ((i = 0; i < BENCH_REPS; i++)); do
|
|
d=$(timeit "${WC_CMD[@]}" "$flag" "$file")
|
|
[[ -z "$wc_us" || "$d" -lt "$wc_us" ]] && wc_us="$d"
|
|
|
|
d=$(timeit "$FASTWC" "$flag" "$file")
|
|
[[ -z "$fast_us" || "$d" -lt "$fast_us" ]] && fast_us="$d"
|
|
done
|
|
|
|
finish_race "$label" "$wc_count" "$fast_count" "$wc_us" "$fast_us"
|
|
}
|
|
|
|
# run_stdin_case <words|lines> <n-lines> <-w|-l|...> — same race, but the
|
|
# data is fed through standard input with a redirect instead of a file
|
|
# argument. Counts must also agree with the reference's stdin behavior.
|
|
run_stdin_case() {
|
|
local mode="$1" lines="$2" flag="$3"
|
|
local noun='lines'; [[ "$lines" -eq 1 ]] && noun='line'
|
|
local label="stdin ${mode} (${lines} ${noun})"
|
|
local file wc_count fast_count wc_us fast_us
|
|
local i d
|
|
|
|
file=$(createtxt "$lines") || return 1
|
|
|
|
wc_count=$(capture_count "${WC_CMD[@]}" "$flag" < "$file")
|
|
fast_count=$(capture_count "$FASTWC" "$flag" < "$file")
|
|
|
|
wc_us=''
|
|
fast_us=''
|
|
for ((i = 0; i < BENCH_REPS; i++)); do
|
|
d=$(timeit "${WC_CMD[@]}" "$flag" < "$file")
|
|
[[ -z "$wc_us" || "$d" -lt "$wc_us" ]] && wc_us="$d"
|
|
|
|
d=$(timeit "$FASTWC" "$flag" < "$file")
|
|
[[ -z "$fast_us" || "$d" -lt "$fast_us" ]] && fast_us="$d"
|
|
done
|
|
|
|
finish_race "$label" "$wc_count" "$fast_count" "$wc_us" "$fast_us"
|
|
}
|
|
|
|
# run_solo_case <n-lines> <-l|...> — time fastwc alone on <n-lines> of data,
|
|
# no reference to beat. Prints the best time and throughput. A failure to
|
|
# create the data (disk, say) skips the case instead of failing the suite.
|
|
run_solo_case() {
|
|
local lines="$1" flag="$2"
|
|
local noun='lines'; [[ "$lines" -eq 1 ]] && noun='line'
|
|
local label="solo ${lines} ${noun}"
|
|
local file best_us='' best_ms bytes gbps mlps i d
|
|
|
|
file=$(createtxt "$lines") || {
|
|
printf '%-28s %s\n' "$label" 'SKIP (could not create test data)'
|
|
return 0
|
|
}
|
|
|
|
for ((i = 0; i < BENCH_REPS; i++)); do
|
|
d=$(timeit "$FASTWC" "$flag" "$file")
|
|
[[ -z "$best_us" || "$d" -lt "$best_us" ]] && best_us="$d"
|
|
done
|
|
best_ms=$(( best_us / 1000 ))
|
|
|
|
bytes=$((lines * 11))
|
|
gbps=$(awk -v b="$bytes" -v ms="$best_ms" 'BEGIN { if (ms < 1) ms = 1; printf "%.2f", b / ms / 1e6 }')
|
|
mlps=$(awk -v l="$lines" -v ms="$best_ms" 'BEGIN { if (ms < 1) ms = 1; printf "%.1f", l / ms / 1e3 }')
|
|
|
|
printf '%-28s %25s %12s %14s\n' \
|
|
"$label" "fastwc: ${best_ms}ms (${best_us}µs)" "${gbps} GB/s" "${mlps} Mlines/s"
|
|
}
|
|
|
|
# run_cases <words|lines> <-w|-l> <size...> — run run_case for every size,
|
|
# stopping at the first failure. Returns non-zero if any case failed.
|
|
run_cases() {
|
|
local mode="$1" flag="$2"
|
|
shift 2
|
|
local rc=0 size
|
|
for size in "$@"; do
|
|
run_case "$mode" "$size" "$flag" || { rc=1; break; }
|
|
done
|
|
return $rc
|
|
}
|
|
|
|
# run_stdin_cases <words|lines> <-w|-l|...> <size...> — run run_stdin_case
|
|
# for every size, stopping at the first failure.
|
|
run_stdin_cases() {
|
|
local mode="$1" flag="$2"
|
|
shift 2
|
|
local rc=0 size
|
|
for size in "$@"; do
|
|
run_stdin_case "$mode" "$size" "$flag" || { rc=1; break; }
|
|
done
|
|
return $rc
|
|
}
|
|
|
|
# print_averages — average the accumulated speedup ratios (reference time
|
|
# over fastwc time) per oracle and print them. Reads $RATIOS_FILE, which
|
|
# test-all.sh points at a shared temp file across all suites.
|
|
print_averages() {
|
|
local oracle avg n
|
|
|
|
[[ -s "$RATIOS_FILE" ]] || return 0
|
|
|
|
while IFS=$'\t' read -r oracle avg n; do
|
|
[[ -n "$oracle" ]] &&
|
|
printf 'average speedup vs %s wc: %s (%s cases)\n' \
|
|
"$oracle" "$avg" "$n"
|
|
done <<< "$(awk -F'\t' '
|
|
{ sum[$1] += $2; n[$1]++ }
|
|
END {
|
|
if (n["coreutils"])
|
|
printf "coreutils\t%.2fx\t%d\n", sum["coreutils"] / n["coreutils"], n["coreutils"];
|
|
if (n["busybox"])
|
|
printf "busybox\t%.2fx\t%d\n", sum["busybox"] / n["busybox"], n["busybox"];
|
|
if (n["toybox"])
|
|
printf "toybox\t%.2fx\t%d\n", sum["toybox"] / n["toybox"], n["toybox"];
|
|
}' "$RATIOS_FILE")"
|
|
}
|