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