| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
* win32: fnmatch2 minor refinements (no-op)
With beacket, add '\' to the switch/case, and at fnmatch, pre-calc
the two most used flags (CASEFOLD and PATHNAME) once on init.
Negligible perf impact, and happens to save few bytes in x64.
* win32: actype: trivial refinments (no-op)
NULL was used in actype.h but requires stddef.h - which we don't
include, so use (int*)0 which also expresses it more clearly.
Remove "#include <string.h>" at actype.c, which we don't need anymore.
* scripts/patbench.sh: make executable (chmod +x)
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Few minor improvements:
- Add few valid but edge-case patterns (start with ']' etc).
- Add the expected result for default lines, and report ok/err.
- Disable measurements with -mn (to be measured externally).
Also, the default lines were modified slightly so that the new
edge cases results are largely distinct, so it can be used as
correctness test with -d (and exit code is 1 on errors).
BENCHMARK RESULTS
Below are results of running this script using busybox-w32 on win10,
and using busybox on Alpine linux 3.23.
Observations of busybox-w32 results, which uses old glibc fnmatch:
[10] 129 ms OK (M:12345) '*[hello world, this is a test]*'
[42] 22491 ms OK (M:12-45) '*[0-9A-Za-z]*[0-9A-Za-z]*[0-9A-Za-z]'
The current busybox-w32 implementation is exponential, and while
tests of simple patterns complete in 100-200ms, patterns with 3 '*'
can take 30s or more to complete, way longer with 4 '*', etc.
[12] 192 ms E:1-3-- (M:-----) '*[*'
[13] 201 ms E:1---- (M:-----) '*[]*'
[14] 203 ms E:--3-- (M:-----) '*[!]*'
A bracket which doesn't start a bracket expression is regular char,
and all these are missing the closing bracket (by POSIX rules), and
should be matched literally, but the current fnmatch fails with that.
[35] 1305 ms OK (M:12-45) '*[0-9A-Za-z]*[0-9A-Za-z]'
[36] 1928 ms OK (M:12-45) '*[[:alnum:]]*[[:alnum:]]'
[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:]]'
charclass [:alnum:] is x1.4 slower than an equivalent non-class range,
but [:lower:] is already x2 slower than the equivalent, and [:xdigit:]
is x3 slower than the equivalent. This is because the name is searched
in a list which starts with "alnum" and ends in "xdigit", and the
search duration (and the following switch in the same order) clearly
affects how quickly a pattern can be tested.
There are other issues in busybox-w32 fnmatch, like incorrect
case-insensitivity and more, but which don't manifest in case...esac.
Benchmark results with busybox-w32 on Windows 10 (compiled with gcc):
[ 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 - exponential implementation becomes very slow)
results with busybox on Alpine linux 3.23 (musl-libc has linear-time
fnmatch, using wide-char wctype/iswctype - slightly slower than char):
[ 1] 135 ms OK (M:-----) ''
[ 2] 141 ms OK (M:12345) '*'
[ 3] 139 ms OK (M:-----) '@'
[ 4] 141 ms OK (M:1----) 'Lorem*'
[ 5] 148 ms OK (M:-2---) '*quis'
[ 6] 216 ms OK (M:--3--) '*nisi*'
[ 7] 410 ms OK (M:--3--) '*[fobar]xyz*'
[ 8] 787 ms OK (M:--3--) '*[foobarfoobarfoobarfoobar]xyz*'
[ 9] 844 ms OK (M:-2---) '*[!foobarfoobarfoobarfoobar]xyz*'
[10] 215 ms OK (M:12345) '*[hello world, this is a test]*'
[11] 237 ms OK (M:12345) '*[!hello world, this is a test]*'
[12] 206 ms OK (M:1-3--) '*[*'
[13] 242 ms OK (M:1----) '*[]*'
[14] 220 ms OK (M:--3--) '*[!]*'
[15] 306 ms OK (M:-23-5) '*[!]].*'
[16] 591 ms OK (M:1----) '*[![:print:]]*'
[17] 216 ms OK (M:-23--) '*z*'
[18] 198 ms OK (M:---4-) '*-*'
[19] 286 ms OK (M:---4-) '*[-]*'
[20] 285 ms OK (M:-234-) '*[-z]*'
[21] 291 ms OK (M:-234-) '*[z-]*'
[22] 299 ms OK (M:-234-) '*[-z-]*'
[23] 228 ms OK (M:1-3--) '*]*'
[24] 286 ms OK (M:1-3--) '*[]]*'
[25] 267 ms OK (M:1-34-) '*[]-]*'
[26] 349 ms OK (M:123--) '*[]-_]*'
[27] 292 ms OK (M:1234-) '*[]-_-]*'
[28] 198 ms OK (M:12-45) '*[0-9A-Za-z][0-9A-Za-z]'
[29] 201 ms OK (M:12-45) '*[[:alnum:]][[:alnum:]]'
[30] 179 ms OK (M:12-45) '*[a-z][a-z]'
[31] 217 ms OK (M:12-45) '*[a-bc-de-z][a-bc-de-z]'
[32] 205 ms OK (M:12-45) '*[[:lower:]][[:lower:]]'
[33] 202 ms OK (M:-----) '*[0-9A-Fa-ef][0-9A-Fa-ef]'
[34] 203 ms OK (M:-----) '*[[:xdigit:]][[:xdigit:]]'
[35] 215 ms OK (M:12-45) '*[0-9A-Za-z]*[0-9A-Za-z]'
[36] 213 ms OK (M:12-45) '*[[:alnum:]]*[[:alnum:]]'
[37] 191 ms OK (M:12-45) '*[a-z]*[a-z]'
[38] 219 ms OK (M:12-45) '*[a-bc-de-z]*[a-bc-de-z]'
[39] 224 ms OK (M:12-45) '*[[:lower:]]*[[:lower:]]'
[40] 217 ms OK (M:---4-) '*[0-9A-Fa-ef]*[0-9A-Fa-ef]'
[41] 199 ms OK (M:---4-) '*[[:xdigit:]]*[[:xdigit:]]'
[42] 227 ms OK (M:12-45) '*[0-9A-Za-z]*[0-9A-Za-z]*[0-9A-Za-z]'
[43] 239 ms OK (M:12-45) '*[[:alnum:]]*[[:alnum:]]*[[:alnum:]]'
[44] 204 ms OK (M:12-45) '*[a-z]*[a-z]*[a-z]'
[45] 258 ms OK (M:12-45) '*[a-bc-de-z]*[a-bc-de-z]*[a-bc-de-z]'
[46] 235 ms OK (M:12-45) '*[[:lower:]]*[[:lower:]]*[[:lower:]]'
[47] 247 ms OK (M:---4-) '*[0-9A-Fa-ef]*[0-9A-Fa-ef]*[0-9A-Fa-ef]'
[48] 247 ms OK (M:---4-) '*[[:xdigit:]]*[[:xdigit:]]*[[:xdigit:]]'
[49] 286 ms OK (M:12-45) '*[0-9A-Za-z]*[0-9A-Za-z]*[0-9A-Za-z]*[0-9A-Za-z]'
[50] 262 ms OK (M:12-45) '*[[:alnum:]]*[[:alnum:]]*[[:alnum:]]*[[:alnum:]]'
[51] 219 ms OK (M:12-45) '*[a-z]*[a-z]*[a-z]*[a-z]'
[52] 273 ms OK (M:12-45) '*[a-bc-de-z]*[a-bc-de-z]*[a-bc-de-z]*[a-bc-de-z]'
[53] 274 ms OK (M:12-45) '*[[:lower:]]*[[:lower:]]*[[:lower:]]*[[:lower:]]'
[54] 281 ms OK (M:---4-) '*[0-9A-Fa-ef]*[0-9A-Fa-ef]*[0-9A-Fa-ef]*[0-9A-Fa-ef]'
[55] 296 ms OK (M:---4-) '*[[:xdigit:]]*[[:xdigit:]]*[[:xdigit:]]*[[:xdigit:]]'
|
