ash ${str/find/repl} performance

dietmar.schindler at manrolandgoss.com dietmar.schindler at manrolandgoss.com
Wed Jul 21 08:41:12 UTC 2021


> From: busybox <busybox-bounces at busybox.net> On Behalf Of Alin Mr
> Sent: Monday, July 19, 2021 9:21 PM
>
> 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^?)

I think the "sed" command gets no input, so its timing result is not relevant. Still your observation regarding the time complexity of "${x//:/|}" is valid.

--
Best regards,
Dietmar Schindler
________________________________
manroland Goss web systems GmbH | Managing Director: Franz Kriechbaum
Registered Office: Augsburg | Trade Register: AG Augsburg | HRB-No.: 32609 | VAT: DE815764857

Confidentiality note:
This message and any attached documents may contain confidential or proprietary information of manroland|Goss. These materials are intended only for the use of the intended recipient. If you are not the intended recipient of this transmission, you are hereby notified that any distribution, disclosure, printing, copying, storage, modification or the taking of any action in reliance upon this transmission is strictly prohibited. Delivery of this message to any person other than the intended recipient shall not compromise or waive such confidentiality, privilege or exemption from disclosure as to this communication. If you have received this communication in error, please immediately notify the sender and delete the message from your system. All liability for viruses is excluded to the fullest extent permitted by law.
________________________________


More information about the busybox mailing list