I wrote:
>It would be possible to use a more efficient approach when the pattern
>is known to have no special characters. But that would require more
>code.
To quantify this I made a patch which handles the special case of
patterns that don't require globbing. The feature is controlled by
the ASH_OPTIMIZE_FOR_SIZE configuration option so it isn't enabled
in the default build (where ASH_OPTIMIZE_FOR_SIZE is enabled).
When it is enabled it adds 183 bytes.
Benchmarks with the feature enabled follow. This command uses a
bracket expression so globbing is required:
hyperfine -L n 10,15,20,30 -S ./ash -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 ± σ): 36.9 ms ± 0.6 ms [User: 36.3 ms, System: 1.1 ms]
Range (min … max): 36.2 ms … 38.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 ± σ): 104.6 ms ± 1.4 ms [User: 104.0 ms, System: 1.0 ms]
Range (min … max): 103.1 ms … 107.6 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 ± σ): 241.3 ms ± 2.7 ms [User: 240.5 ms, System: 1.1 ms]
Range (min … max): 238.2 ms … 246.7 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 ± σ): 697.1 ms ± 4.0 ms [User: 695.6 ms, System: 1.0 ms]
Range (min … max): 691.8 ms … 701.8 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.84 ± 0.06 times faster than '
x=$(cat /etc/passwd /etc/passwd /etc/passwd | head -15);
for i in $(seq 1 20); do echo "${x//[:]/|}"; done'
6.54 ± 0.14 times faster than '
x=$(cat /etc/passwd /etc/passwd /etc/passwd | head -20);
for i in $(seq 1 20); do echo "${x//[:]/|}"; done'
18.90 ± 0.35 times faster than '
x=$(cat /etc/passwd /etc/passwd /etc/passwd | head -30);
for i in $(seq 1 20); do echo "${x//[:]/|}"; done'
The elapsed times and the increase in time with variable length are
similar to the results reported previously.
This command uses a literal search string:
hyperfine -L n 10,15,20,30 -S ./ash -w 2 -r 10 -s basic '
x=$(cat /etc/passwd /etc/passwd /etc/passwd | head -{n});
for i in $(seq 1 1000); do echo "${x//:/|}"; done'
Benchmark #1:
x=$(cat /etc/passwd /etc/passwd /etc/passwd | head -10);
for i in $(seq 1 1000); do echo "${x//:/|}"; done
Time (mean ± σ): 9.0 ms ± 0.6 ms [User: 8.4 ms, System: 1.2 ms]
Range (min … max): 8.5 ms … 10.5 ms 10 runs
Benchmark #2:
x=$(cat /etc/passwd /etc/passwd /etc/passwd | head -15);
for i in $(seq 1 1000); do echo "${x//:/|}"; done
Time (mean ± σ): 12.5 ms ± 0.1 ms [User: 11.6 ms, System: 1.5 ms]
Range (min … max): 12.4 ms … 12.7 ms 10 runs
Benchmark #3:
x=$(cat /etc/passwd /etc/passwd /etc/passwd | head -20);
for i in $(seq 1 1000); do echo "${x//:/|}"; done
Time (mean ± σ): 17.9 ms ± 1.1 ms [User: 17.6 ms, System: 0.9 ms]
Range (min … max): 17.0 ms … 19.5 ms 10 runs
Benchmark #4:
x=$(cat /etc/passwd /etc/passwd /etc/passwd | head -30);
for i in $(seq 1 1000); do echo "${x//:/|}"; done
Time (mean ± σ): 27.2 ms ± 0.9 ms [User: 26.7 ms, System: 1.1 ms]
Range (min … max): 26.0 ms … 28.4 ms 10 runs
Summary
'
x=$(cat /etc/passwd /etc/passwd /etc/passwd | head -10);
for i in $(seq 1 1000); do echo "${x//:/|}"; done' ran
1.39 ± 0.09 times faster than '
x=$(cat /etc/passwd /etc/passwd /etc/passwd | head -15);
for i in $(seq 1 1000); do echo "${x//:/|}"; done'
1.99 ± 0.18 times faster than '
x=$(cat /etc/passwd /etc/passwd /etc/passwd | head -20);
for i in $(seq 1 1000); do echo "${x//:/|}"; done'
3.03 ± 0.22 times faster than '
x=$(cat /etc/passwd /etc/passwd /etc/passwd | head -30);
for i in $(seq 1 1000); do echo "${x//:/|}"; done'
The elapsed times are much shorter: I had to increase the number of
iterations from 20 to 1000 to get reliable measurements. The increase
in time with variable length is linear.
Ron
_______________________________________________
busybox mailing list
[email protected]
http://lists.busybox.net/mailman/listinfo/busybox
