ash ${str/find/repl} performance

Alin Mr almr.oss at outlook.com
Mon Jul 19 20:59:09 UTC 2021


It seems that even with a non-existent pattern, and even with ${str/once/repl}, and even if repl == find, the behavior is still O(n^??). ${str##*X} and others don't exhibit this.

So the problem with the replacement code is more fundamental. Or I'm messing something up (but I don't think so).

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 ± σ):      48.3 ms ±   2.5 ms    [User: 48.2 ms, System: 0.8 ms]
  Range (min … max):    44.8 ms …  51.1 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 ± σ):     127.6 ms ±   3.6 ms    [User: 127.4 ms, System: 0.8 ms]
  Range (min … max):   122.1 ms … 133.4 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 ± σ):     303.6 ms ±   3.8 ms    [User: 303.7 ms, System: 0.5 ms]
  Range (min … max):   300.9 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 ± σ):     834.5 ms ±   8.6 ms    [User: 835.1 ms, System: 0.0 ms]
  Range (min … max):   824.4 ms … 853.4 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.64 ± 0.16 times faster than 'x=$(cat /etc/passwd /etc/passwd /etc/passwd | head -15); for i in $(seq 1 20); do echo "${x/~/~}"; done'
    6.28 ± 0.34 times faster than 'x=$(cat /etc/passwd /etc/passwd /etc/passwd | head -20); for i in $(seq 1 20); do echo "${x/~/~}"; done'
   17.27 ± 0.92 times faster than 'x=$(cat /etc/passwd /etc/passwd /etc/passwd | head -30); for i in $(seq 1 20); do echo "${x/~/~}"; done'


More information about the busybox mailing list