diff options
| author | Avi Halachmi (:avih) <avihpit@yahoo.com> | 2026-04-15 19:58:58 +0300 |
|---|---|---|
| committer | Ron Yorston <rmy@pobox.com> | 2026-04-16 10:42:13 +0100 |
| commit | 98e09f1c6221a88fb42fd37019a9e5e8482d2654 (patch) | |
| tree | 638afc33ce57f6d81e164d05cafa8e370f60ed93 /scripts/embedded_scripts | |
| parent | 85f8fb5f2841e732e01cb32340822cc124f63fb7 (diff) | |
| download | busybox-w32-98e09f1c6221a88fb42fd37019a9e5e8482d2654.tar.gz busybox-w32-98e09f1c6221a88fb42fd37019a9e5e8482d2654.tar.bz2 busybox-w32-98e09f1c6221a88fb42fd37019a9e5e8482d2654.zip | |
win32: fnmatch2: replace if-else-... with switch/case
This was done to be more concise, but it also happens to speed up
the two slowest test patterns by about ~ 30%, and without measurable
impact on any of the other test patterns (nor the correctness).
Maybe the stars aligned for compiler optimizations. We'll take it.
Here are results of scripts/patbench.sh with recent iterations of
fnmatch, from most recent to the original old fnmatch:
CURRENT results:
[ 1] 107 ms OK (M:-----) ''
[ 2] 105 ms OK (M:12345) '*'
[ 3] 106 ms OK (M:-----) '@'
[ 4] 111 ms OK (M:1----) 'Lorem*'
[ 5] 122 ms OK (M:-2---) '*quis'
[ 6] 133 ms OK (M:--3--) '*nisi*'
[ 7] 229 ms OK (M:--3--) '*[fobar]xyz*'
[ 8] 451 ms OK (M:--3--) '*[foobarfoobarfoobarfoobar]xyz*'
[ 9] 463 ms OK (M:-2---) '*[!foobarfoobarfoobarfoobar]xyz*'
[10] 136 ms OK (M:12345) '*[hello world, this is a test]*'
[11] 126 ms OK (M:12345) '*[!hello world, this is a test]*'
[12] 169 ms OK (M:1-3--) '*[*'
[13] 175 ms OK (M:1----) '*[]*'
[14] 171 ms OK (M:--3--) '*[!]*'
[15] 162 ms OK (M:-23-5) '*[!]].*'
[16] 243 ms OK (M:1----) '*[![:print:]]*'
[17] 135 ms OK (M:-23--) '*z*'
[18] 131 ms OK (M:---4-) '*-*'
[19] 157 ms OK (M:---4-) '*[-]*'
[20] 165 ms OK (M:-234-) '*[-z]*'
[21] 176 ms OK (M:-234-) '*[z-]*'
[22] 182 ms OK (M:-234-) '*[-z-]*'
[23] 130 ms OK (M:1-3--) '*]*'
[24] 153 ms OK (M:1-3--) '*[]]*'
[25] 164 ms OK (M:1-34-) '*[]-]*'
[26] 167 ms OK (M:123--) '*[]-_]*'
[27] 168 ms OK (M:1234-) '*[]-_-]*'
[28] 122 ms OK (M:12-45) '*[0-9A-Za-z][0-9A-Za-z]'
[29] 126 ms OK (M:12-45) '*[[:alnum:]][[:alnum:]]'
[30] 118 ms OK (M:12-45) '*[a-z][a-z]'
[31] 127 ms OK (M:12-45) '*[a-bc-de-z][a-bc-de-z]'
[32] 131 ms OK (M:12-45) '*[[:lower:]][[:lower:]]'
[33] 136 ms OK (M:-----) '*[0-9A-Fa-ef][0-9A-Fa-ef]'
[34] 124 ms OK (M:-----) '*[[:xdigit:]][[:xdigit:]]'
[35] 128 ms OK (M:12-45) '*[0-9A-Za-z]*[0-9A-Za-z]'
[36] 129 ms OK (M:12-45) '*[[:alnum:]]*[[:alnum:]]'
[37] 127 ms OK (M:12-45) '*[a-z]*[a-z]'
[38] 123 ms OK (M:12-45) '*[a-bc-de-z]*[a-bc-de-z]'
[39] 124 ms OK (M:12-45) '*[[:lower:]]*[[:lower:]]'
[40] 136 ms OK (M:---4-) '*[0-9A-Fa-ef]*[0-9A-Fa-ef]'
[41] 134 ms OK (M:---4-) '*[[:xdigit:]]*[[:xdigit:]]'
[42] 136 ms OK (M:12-45) '*[0-9A-Za-z]*[0-9A-Za-z]*[0-9A-Za-z]'
[43] 131 ms OK (M:12-45) '*[[:alnum:]]*[[:alnum:]]*[[:alnum:]]'
[44] 124 ms OK (M:12-45) '*[a-z]*[a-z]*[a-z]'
[45] 137 ms OK (M:12-45) '*[a-bc-de-z]*[a-bc-de-z]*[a-bc-de-z]'
[46] 129 ms OK (M:12-45) '*[[:lower:]]*[[:lower:]]*[[:lower:]]'
[47] 160 ms OK (M:---4-) '*[0-9A-Fa-ef]*[0-9A-Fa-ef]*[0-9A-Fa-ef]'
[48] 164 ms OK (M:---4-) '*[[:xdigit:]]*[[:xdigit:]]*[[:xdigit:]]'
[49] 152 ms OK (M:12-45) '*[0-9A-Za-z]*[0-9A-Za-z]*[0-9A-Za-z]*[0-9A-Za-z]'
[50] 152 ms OK (M:12-45) '*[[:alnum:]]*[[:alnum:]]*[[:alnum:]]*[[:alnum:]]'
[51] 130 ms OK (M:12-45) '*[a-z]*[a-z]*[a-z]*[a-z]'
[52] 165 ms OK (M:12-45) '*[a-bc-de-z]*[a-bc-de-z]*[a-bc-de-z]*[a-bc-de-z]'
[53] 146 ms OK (M:12-45) '*[[:lower:]]*[[:lower:]]*[[:lower:]]*[[:lower:]]'
[54] 180 ms OK (M:---4-) '*[0-9A-Fa-ef]*[0-9A-Fa-ef]*[0-9A-Fa-ef]*[0-9A-Fa-ef]'
[55] 189 ms OK (M:---4-) '*[[:xdigit:]]*[[:xdigit:]]*[[:xdigit:]]*[[:xdigit:]]'
Previous commit (if-else-...) is mainly slower in patterns 8 and 9:
[ 6] 143 ms OK (M:--3--) '*nisi*'
[ 7] 251 ms OK (M:--3--) '*[fobar]xyz*'
[ 8] 638 ms OK (M:--3--) '*[foobarfoobarfoobarfoobar]xyz*'
[ 9] 651 ms OK (M:-2---) '*[!foobarfoobarfoobarfoobar]xyz*'
[10] 138 ms OK (M:12345) '*[hello world, this is a test]*'
[11] 137 ms OK (M:12345) '*[!hello world, this is a test]*'
Initial fnmatch2 commit (without any optimizations):
[ 1] 101 ms OK (M:-----) ''
[ 2] 123 ms OK (M:12345) '*'
[ 3] 105 ms OK (M:-----) '@'
[ 4] 115 ms OK (M:1----) 'Lorem*'
[ 5] 134 ms OK (M:-2---) '*quis'
[ 6] 131 ms OK (M:--3--) '*nisi*'
[ 7] 235 ms OK (M:--3--) '*[fobar]xyz*'
[ 8] 586 ms OK (M:--3--) '*[foobarfoobarfoobarfoobar]xyz*'
[ 9] 613 ms OK (M:-2---) '*[!foobarfoobarfoobarfoobar]xyz*'
[10] 153 ms OK (M:12345) '*[hello world, this is a test]*'
[11] 160 ms OK (M:12345) '*[!hello world, this is a test]*'
[12] 164 ms OK (M:1-3--) '*[*'
[13] 165 ms OK (M:1----) '*[]*'
[14] 157 ms OK (M:--3--) '*[!]*'
[15] 157 ms OK (M:-23-5) '*[!]].*'
[16] 244 ms OK (M:1----) '*[![:print:]]*'
[17] 132 ms OK (M:-23--) '*z*'
[18] 134 ms OK (M:---4-) '*-*'
[19] 160 ms OK (M:---4-) '*[-]*'
[20] 157 ms OK (M:-234-) '*[-z]*'
[21] 168 ms OK (M:-234-) '*[z-]*'
[22] 166 ms OK (M:-234-) '*[-z-]*'
[23] 130 ms OK (M:1-3--) '*]*'
[24] 150 ms OK (M:1-3--) '*[]]*'
[25] 151 ms OK (M:1-34-) '*[]-]*'
[26] 157 ms OK (M:123--) '*[]-_]*'
[27] 156 ms OK (M:1234-) '*[]-_-]*'
[28] 402 ms OK (M:12-45) '*[0-9A-Za-z][0-9A-Za-z]'
[29] 416 ms OK (M:12-45) '*[[:alnum:]][[:alnum:]]'
[30] 265 ms OK (M:12-45) '*[a-z][a-z]'
[31] 410 ms OK (M:12-45) '*[a-bc-de-z][a-bc-de-z]'
[32] 426 ms OK (M:12-45) '*[[:lower:]][[:lower:]]'
[33] 347 ms OK (M:-----) '*[0-9A-Fa-ef][0-9A-Fa-ef]'
[34] 370 ms OK (M:-----) '*[[:xdigit:]][[:xdigit:]]'
[35] 294 ms OK (M:12-45) '*[0-9A-Za-z]*[0-9A-Za-z]'
[36] 301 ms OK (M:12-45) '*[[:alnum:]]*[[:alnum:]]'
[37] 214 ms OK (M:12-45) '*[a-z]*[a-z]'
[38] 304 ms OK (M:12-45) '*[a-bc-de-z]*[a-bc-de-z]'
[39] 302 ms OK (M:12-45) '*[[:lower:]]*[[:lower:]]'
[40] 306 ms OK (M:---4-) '*[0-9A-Fa-ef]*[0-9A-Fa-ef]'
[41] 291 ms OK (M:---4-) '*[[:xdigit:]]*[[:xdigit:]]'
[42] 291 ms OK (M:12-45) '*[0-9A-Za-z]*[0-9A-Za-z]*[0-9A-Za-z]'
[43] 302 ms OK (M:12-45) '*[[:alnum:]]*[[:alnum:]]*[[:alnum:]]'
[44] 208 ms OK (M:12-45) '*[a-z]*[a-z]*[a-z]'
[45] 314 ms OK (M:12-45) '*[a-bc-de-z]*[a-bc-de-z]*[a-bc-de-z]'
[46] 288 ms OK (M:12-45) '*[[:lower:]]*[[:lower:]]*[[:lower:]]'
[47] 315 ms OK (M:---4-) '*[0-9A-Fa-ef]*[0-9A-Fa-ef]*[0-9A-Fa-ef]'
[48] 340 ms OK (M:---4-) '*[[:xdigit:]]*[[:xdigit:]]*[[:xdigit:]]'
[49] 309 ms OK (M:12-45) '*[0-9A-Za-z]*[0-9A-Za-z]*[0-9A-Za-z]*[0-9A-Za-z]'
[50] 304 ms OK (M:12-45) '*[[:alnum:]]*[[:alnum:]]*[[:alnum:]]*[[:alnum:]]'
[51] 217 ms OK (M:12-45) '*[a-z]*[a-z]*[a-z]*[a-z]'
[52] 317 ms OK (M:12-45) '*[a-bc-de-z]*[a-bc-de-z]*[a-bc-de-z]*[a-bc-de-z]'
[53] 322 ms OK (M:12-45) '*[[:lower:]]*[[:lower:]]*[[:lower:]]*[[:lower:]]'
[54] 315 ms OK (M:---4-) '*[0-9A-Fa-ef]*[0-9A-Fa-ef]*[0-9A-Fa-ef]*[0-9A-Fa-ef]'
[55] 348 ms OK (M:---4-) '*[[:xdigit:]]*[[:xdigit:]]*[[:xdigit:]]*[[:xdigit:]]'
Old fnmatch with actype/isactype in O(1):
[ 1] 103 ms OK (M:-----) ''
[ 2] 116 ms OK (M:12345) '*'
[ 3] 108 ms OK (M:-----) '@'
[ 4] 112 ms OK (M:1----) 'Lorem*'
[ 5] 122 ms OK (M:-2---) '*quis'
[ 6] 123 ms OK (M:--3--) '*nisi*'
[ 7] 270 ms OK (M:--3--) '*[fobar]xyz*'
[ 8] 650 ms OK (M:--3--) '*[foobarfoobarfoobarfoobar]xyz*'
[ 9] 681 ms OK (M:-2---) '*[!foobarfoobarfoobarfoobar]xyz*'
[10] 133 ms OK (M:12345) '*[hello world, this is a test]*'
[11] 135 ms OK (M:12345) '*[!hello world, this is a test]*'
[12] 191 ms E:1-3-- (M:-----) '*[*'
[13] 213 ms E:1---- (M:-----) '*[]*'
[14] 215 ms E:--3-- (M:-----) '*[!]*'
[15] 182 ms OK (M:-23-5) '*[!]].*'
[16] 296 ms OK (M:1----) '*[![:print:]]*'
[17] 121 ms OK (M:-23--) '*z*'
[18] 115 ms OK (M:---4-) '*-*'
[19] 167 ms OK (M:---4-) '*[-]*'
[20] 189 ms OK (M:-234-) '*[-z]*'
[21] 194 ms OK (M:-234-) '*[z-]*'
[22] 203 ms OK (M:-234-) '*[-z-]*'
[23] 122 ms OK (M:1-3--) '*]*'
[24] 166 ms OK (M:1-3--) '*[]]*'
[25] 185 ms OK (M:1-34-) '*[]-]*'
[26] 163 ms OK (M:123--) '*[]-_]*'
[27] 176 ms OK (M:1234-) '*[]-_-]*'
[28] 381 ms OK (M:12-45) '*[0-9A-Za-z][0-9A-Za-z]'
[29] 510 ms OK (M:12-45) '*[[:alnum:]][[:alnum:]]'
[30] 274 ms OK (M:12-45) '*[a-z][a-z]'
[31] 379 ms OK (M:12-45) '*[a-bc-de-z][a-bc-de-z]'
[32] 488 ms OK (M:12-45) '*[[:lower:]][[:lower:]]'
[33] 340 ms OK (M:-----) '*[0-9A-Fa-ef][0-9A-Fa-ef]'
[34] 398 ms OK (M:-----) '*[[:xdigit:]][[:xdigit:]]'
[35] 1402 ms OK (M:12-45) '*[0-9A-Za-z]*[0-9A-Za-z]'
[36] 1962 ms OK (M:12-45) '*[[:alnum:]]*[[:alnum:]]'
[37] 939 ms OK (M:12-45) '*[a-z]*[a-z]'
[38] 1453 ms OK (M:12-45) '*[a-bc-de-z]*[a-bc-de-z]'
[39] 1965 ms OK (M:12-45) '*[[:lower:]]*[[:lower:]]'
[40] 1683 ms OK (M:---4-) '*[0-9A-Fa-ef]*[0-9A-Fa-ef]'
[41] 2117 ms OK (M:---4-) '*[[:xdigit:]]*[[:xdigit:]]'
(aborted manually due to exponential slowness)
Old fnmatch (before actype/isactype):
[ 1] 107 ms OK (M:-----) ''
[ 2] 108 ms OK (M:12345) '*'
[ 3] 104 ms OK (M:-----) '@'
[ 4] 112 ms OK (M:1----) 'Lorem*'
[ 5] 120 ms OK (M:-2---) '*quis'
[ 6] 127 ms OK (M:--3--) '*nisi*'
[ 7] 244 ms OK (M:--3--) '*[fobar]xyz*'
[ 8] 544 ms OK (M:--3--) '*[foobarfoobarfoobarfoobar]xyz*'
[ 9] 588 ms OK (M:-2---) '*[!foobarfoobarfoobarfoobar]xyz*'
[10] 129 ms OK (M:12345) '*[hello world, this is a test]*'
[11] 136 ms OK (M:12345) '*[!hello world, this is a test]*'
[12] 192 ms E:1-3-- (M:-----) '*[*'
[13] 201 ms E:1---- (M:-----) '*[]*'
[14] 203 ms E:--3-- (M:-----) '*[!]*'
[15] 182 ms OK (M:-23-5) '*[!]].*'
[16] 454 ms OK (M:1----) '*[![:print:]]*'
[17] 124 ms OK (M:-23--) '*z*'
[18] 123 ms OK (M:---4-) '*-*'
[19] 160 ms OK (M:---4-) '*[-]*'
[20] 175 ms OK (M:-234-) '*[-z]*'
[21] 177 ms OK (M:-234-) '*[z-]*'
[22] 197 ms OK (M:-234-) '*[-z-]*'
[23] 126 ms OK (M:1-3--) '*]*'
[24] 168 ms OK (M:1-3--) '*[]]*'
[25] 173 ms OK (M:1-34-) '*[]-]*'
[26] 168 ms OK (M:123--) '*[]-_]*'
[27] 170 ms OK (M:1234-) '*[]-_-]*'
[28] 365 ms OK (M:12-45) '*[0-9A-Za-z][0-9A-Za-z]'
[29] 513 ms OK (M:12-45) '*[[:alnum:]][[:alnum:]]'
[30] 263 ms OK (M:12-45) '*[a-z][a-z]'
[31] 376 ms OK (M:12-45) '*[a-bc-de-z][a-bc-de-z]'
[32] 815 ms OK (M:12-45) '*[[:lower:]][[:lower:]]'
[33] 311 ms OK (M:-----) '*[0-9A-Fa-ef][0-9A-Fa-ef]'
[34] 756 ms OK (M:-----) '*[[:xdigit:]][[:xdigit:]]'
[35] 1305 ms OK (M:12-45) '*[0-9A-Za-z]*[0-9A-Za-z]'
[36] 1928 ms OK (M:12-45) '*[[:alnum:]]*[[:alnum:]]'
[37] 919 ms OK (M:12-45) '*[a-z]*[a-z]'
[38] 1446 ms OK (M:12-45) '*[a-bc-de-z]*[a-bc-de-z]'
[39] 3192 ms OK (M:12-45) '*[[:lower:]]*[[:lower:]]'
[40] 1586 ms OK (M:---4-) '*[0-9A-Fa-ef]*[0-9A-Fa-ef]'
[41] 4601 ms OK (M:---4-) '*[[:xdigit:]]*[[:xdigit:]]'
[42] 22491 ms OK (M:12-45) '*[0-9A-Za-z]*[0-9A-Za-z]*[0-9A-Za-z]'
(aborted manually due to exponential slowness)
Diffstat (limited to 'scripts/embedded_scripts')
0 files changed, 0 insertions, 0 deletions