ash ${str/find/repl} performance

[Alin Mr]

It seems that bash-like pattern substitution is surprisingly slow. Tested with busybox 1_33_stable, 1_32_stable, master, Debian/buster busybox-static (all having the applet-bias features configured, i.e. FEATURE_SH_STANDALONE, FEATURE_PREFER_APPLETS, STATIC)

== ${} vs built-in sed

x=$(cat /etc/passwd /etc/passwd /etc/passwd | head -30) \
  hyperfine -s basic -w 2 -r 10 -S /tmp/bbox-1.33/sh \
  'for i in $(seq 1 20); do echo "${x//:/|}"; done' \
  'for i in $(seq 1 50); do sed -e "s/:/|/g"; done'

Benchmark #1: for i in $(seq 1 20); do echo "${x//:/|}"; done

  Time (mean ± σ):     829.9 ms ±  12.8 ms    [User: 829.6 ms, System: 0.4 ms]
  Range (min … max):   820.9 ms … 863.6 ms    10 runs
 
Benchmark #2: for i in $(seq 1 50); do sed -e "s/:/|/g"; done
  Time (mean ± σ):      40.6 ms ±   0.3 ms    [User: 29.8 ms, System: 12.0 ms]
  Range (min … max):    39.9 ms …  40.9 ms    10 runs
 
Summary
  'for i in $(seq 1 50); do sed -e "s/:/|/g"; done' ran
   20.46 ± 0.35 times faster than 'for i in $(seq 1 20); do echo "${x//:/|}"; done'

== O(n^?)

hyperfine -L n 10,15,20,30 -S /tmp/bbox-1.33/sh -w 2 -r 10 -s basic 'x=$(cat /etc/passwd /etc/passwd /etc/passwd | head -{n}); for i in $(seq 1 20); do echo "${x//:/|}"; done'
Benchmark #1: x=$(cat /etc/passwd /etc/passwd /etc/passwd | head -10); for i in $(seq 1 20); do echo "${x//:/|}"; done
  Time (mean ± σ):      47.8 ms ±   2.8 ms    [User: 47.6 ms, System: 0.9 ms]
  Range (min … max):    44.6 ms …  50.4 ms    10 runs
 
Benchmark #2: x=$(cat /etc/passwd /etc/passwd /etc/passwd | head -15); for i in $(seq 1 20); do echo "${x//:/|}"; done
  Time (mean ± σ):     125.0 ms ±   4.1 ms    [User: 125.4 ms, System: 0.2 ms]
  Range (min … max):   121.4 ms … 133.1 ms    10 runs
 
Benchmark #3: x=$(cat /etc/passwd /etc/passwd /etc/passwd | head -20); for i in $(seq 1 20); do echo "${x//:/|}"; done
  Time (mean ± σ):     302.5 ms ±   5.3 ms    [User: 302.2 ms, System: 0.9 ms]
  Range (min … max):   296.0 ms … 313.3 ms    10 runs
 
Benchmark #4: x=$(cat /etc/passwd /etc/passwd /etc/passwd | head -30); for i in $(seq 1 20); do echo "${x//:/|}"; done
  Time (mean ± σ):     833.6 ms ±   7.9 ms    [User: 833.3 ms, System: 0.9 ms]
  Range (min … max):   821.0 ms … 843.7 ms    10 runs
 
Summary
  'x=$(cat /etc/passwd /etc/passwd /etc/passwd | head -10); for i in $(seq 1 20); do echo "${x//:/|}"; done' ran
    2.61 ± 0.17 times faster than 'x=$(cat /etc/passwd /etc/passwd /etc/passwd | head -15); for i in $(seq 1 20); do echo "${x//:/|}"; done'
    6.32 ± 0.38 times faster than 'x=$(cat /etc/passwd /etc/passwd /etc/passwd | head -20); for i in $(seq 1 20); do echo "${x//:/|}"; done'
   17.43 ± 1.02 times faster than 'x=$(cat /etc/passwd /etc/passwd /etc/passwd | head -30); for i in $(seq 1 20); do echo "${x//:/|}"; done'