Title: Add C accelerator for `fnmatch` · Issue #121445 · python/cpython · GitHub
Open Graph Title: Add C accelerator for `fnmatch` · Issue #121445 · python/cpython
X Title: Add C accelerator for `fnmatch` · Issue #121445 · python/cpython
Description: Enhancement By adding a C accelerator, it is possible to improve the running time of fnmatch.filter and fnmatch.translate (the previous proposal is no longer correct since fnmatch(3) does not produce the same results as Python) by 1.1x a...
Open Graph Description: Enhancement By adding a C accelerator, it is possible to improve the running time of fnmatch.filter and fnmatch.translate (the previous proposal is no longer correct since fnmatch(3) does not produ...
X Description: Enhancement By adding a C accelerator, it is possible to improve the running time of fnmatch.filter and fnmatch.translate (the previous proposal is no longer correct since fnmatch(3) does not produ...
Opengraph URL: https://github.com/python/cpython/issues/121445
X: @github
Domain: github.com
{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"Add C accelerator for `fnmatch` ","articleBody":"# Enhancement \r\n\r\nBy adding a C accelerator, it is possible to improve the running time of `fnmatch.filter` and `fnmatch.translate` (the previous proposal is no longer correct since `fnmatch(3)` does not produce the same results as Python) by 1.1x and 6.5x respectively.\r\n\r\nMachine specs:\r\n\r\n```text\r\nOS: openSUSE Leap 15.5 x86_64\r\nKernel: 5.14.21-150500.55.68-default\r\nCPU: 13th Gen Intel i9-13980HX (32) @ 5.400GHz\r\ngcc (SUSE Linux) 7.5.0\r\n```\r\n\r\n### `fnmatch.translate`\r\n\r\n\u003cdetails>\r\n\u003csummary>Without \u003ccode>--with-pydebug\u003c/code>\u003c/summary>\r\n\r\n```text\r\n+------------------------------------------+-----------------------+-----------------------+\r\n| Benchmark | fnmatch-translate-ref | fnmatch-translate-c |\r\n+==========================================+=======================+=======================+\r\n| abc/[!]b-ac-z9-1]/def/\\*?/*/**c/?*[][!] | 6.09 us | 1.26 us: 4.84x faster |\r\n+------------------------------------------+-----------------------+-----------------------+\r\n| !abc/[!]b-ac-z9-1]/def/\\*?/*/**c/?*[][!] | 6.40 us | 1.29 us: 4.97x faster |\r\n+------------------------------------------+-----------------------+-----------------------+\r\n| a**?**cd**?**??k*** | 2.17 us | 303 ns: 7.16x faster |\r\n+------------------------------------------+-----------------------+-----------------------+\r\n| a/**/b/**/c | 2.00 us | 286 ns: 7.00x faster |\r\n+------------------------------------------+-----------------------+-----------------------+\r\n| man/man1/bash.1 | 3.04 us | 459 ns: 6.63x faster |\r\n+------------------------------------------+-----------------------+-----------------------+\r\n| a*b*c*d*e*f*g*h*i*j*k*l*m*n*o** | 5.14 us | 685 ns: 7.50x faster |\r\n+------------------------------------------+-----------------------+-----------------------+\r\n| Geometric mean | (ref) | 6.26x faster |\r\n+------------------------------------------+-----------------------+-----------------------+\r\n``` \r\n\u003c/details>\r\n\r\n\u003cdetails>\r\n\u003csummary>With \u003ccode>--enable-optimizations\u003c/code>\u003c/summary>\r\n\r\n```text\r\n+------------------------------------------+-----------------------+-----------------------+\r\n| Benchmark | fnmatch-translate-ref | fnmatch-translate-c |\r\n+==========================================+=======================+=======================+\r\n| abc/[!]b-ac-z9-1]/def/\\*?/*/**c/?*[][!] | 6.15 us | 1.21 us: 5.07x faster |\r\n+------------------------------------------+-----------------------+-----------------------+\r\n| !abc/[!]b-ac-z9-1]/def/\\*?/*/**c/?*[][!] | 6.45 us | 1.24 us: 5.19x faster |\r\n+------------------------------------------+-----------------------+-----------------------+\r\n| a**?**cd**?**??k*** | 2.15 us | 287 ns: 7.49x faster |\r\n+------------------------------------------+-----------------------+-----------------------+\r\n| a/**/b/**/c | 1.94 us | 269 ns: 7.21x faster |\r\n+------------------------------------------+-----------------------+-----------------------+\r\n| man/man1/bash.1 | 3.00 us | 427 ns: 7.03x faster |\r\n+------------------------------------------+-----------------------+-----------------------+\r\n| a*b*c*d*e*f*g*h*i*j*k*l*m*n*o** | 5.07 us | 636 ns: 7.98x faster |\r\n+------------------------------------------+-----------------------+-----------------------+\r\n| Geometric mean | (ref) | 6.56x faster |\r\n+------------------------------------------+-----------------------+-----------------------+\r\n```\r\n\u003c/details>\r\n\r\n\u003cdetails>\r\n\u003csummary>Benchmark script\u003c/summary>\r\n\r\n```python\r\nimport pyperf\r\n\r\nimport _fnmatch\r\nfrom fnmatch import _translate, _join_translated_parts\r\n\r\ndef translate_py(pattern):\r\n STAR = object()\r\n parts = _translate(pattern, STAR, '.')\r\n return _join_translated_parts(parts, STAR)\r\n\r\ndef translate_ref(loops, pattern):\r\n __ = range(loops)\r\n t0 = pyperf.perf_counter()\r\n for _ in __:\r\n translated = translate_py(pattern)\r\n return pyperf.perf_counter() - t0\r\n\r\ndef translate_c(loops, pattern):\r\n __ = range(loops)\r\n t0 = pyperf.perf_counter()\r\n for _ in __:\r\n res = _fnmatch.translate(pattern)\r\n return pyperf.perf_counter() - t0\r\n\r\nPATTERNS = [\r\n 'abc/[!]b-ac-z9-1]/def/\\\\*?/*/**c/?*[][!]',\r\n '!abc/[!]b-ac-z9-1]/def/\\\\*?/*/**c/?*[][!]',\r\n 'a**?**cd**?**??k***',\r\n 'a/**/b/**/c',\r\n 'man/man1/bash.1',\r\n 'a*b*c*d*e*f*g*h*i*j*k*l*m*n*o**',\r\n]\r\n\r\ndef bench(runner, func):\r\n for pattern in PATTERNS:\r\n runner.bench_time_func(pattern, func, pattern)\r\n\r\ndef add_cmdline_args(cmd, args):\r\n cmd.append(args.impl)\r\n\r\nif __name__ == '__main__':\r\n runner = pyperf.Runner(add_cmdline_args=add_cmdline_args)\r\n runner.argparser.add_argument('impl', choices=['ref', 'c'])\r\n args = runner.parse_args()\r\n\r\n if args.impl == 'ref':\r\n bench(runner, translate_ref)\r\n elif args.impl == 'c':\r\n bench(runner, translate_c)\r\n```\r\n\u003c/details>\r\n\r\n### `fnmatch.filter` (POSIX)\r\n\r\nHere are the true timings for using `fnmatch.filter`. I think we can change the Python implementation as well but I did not bother doing it in the PR (too lazy...). By the way, the timings are for POSIX platforms. On non-posix platforms `os.path.normcase` is called on every name before performing the match, but if the POSIX implementation is faster, I doubt the non-posix one would be slower (the code is essentially the same). I did not include the DEBUG builds since they are not really of interest to us.\r\n\r\n\u003cdetails>\r\n\u003csummary>Without \u003ccode>--with-pydebug\u003c/code>\u003c/summary>\r\n\r\n```text\r\n+-------------------+--------------------+-----------------------+-----------------------+\r\n| Benchmark | fnmatch-filter-ref | fnmatch-filter-py | fnmatch-filter-c |\r\n+===================+====================+=======================+=======================+\r\n| small_match_none | 353 ns | 432 ns: 1.22x slower | 383 ns: 1.08x slower |\r\n+-------------------+--------------------+-----------------------+-----------------------+\r\n| small_match_some | 429 ns | 480 ns: 1.12x slower | 440 ns: 1.03x slower |\r\n+-------------------+--------------------+-----------------------+-----------------------+\r\n| small_match_all | 485 ns | 525 ns: 1.08x slower | not significant |\r\n+-------------------+--------------------+-----------------------+-----------------------+\r\n| medium_match_none | 2.46 us | 2.36 us: 1.04x faster | 2.28 us: 1.08x faster |\r\n+-------------------+--------------------+-----------------------+-----------------------+\r\n| medium_match_some | 3.22 us | 2.90 us: 1.11x faster | 2.76 us: 1.16x faster |\r\n+-------------------+--------------------+-----------------------+-----------------------+\r\n| medium_match_all | 3.89 us | 3.51 us: 1.11x faster | 3.33 us: 1.17x faster |\r\n+-------------------+--------------------+-----------------------+-----------------------+\r\n| large_match_none | 25.5 us | 22.6 us: 1.13x faster | 22.1 us: 1.16x faster |\r\n+-------------------+--------------------+-----------------------+-----------------------+\r\n| large_match_some | 32.3 us | 27.5 us: 1.18x faster | 26.8 us: 1.20x faster |\r\n+-------------------+--------------------+-----------------------+-----------------------+\r\n| large_match_all | 38.8 us | 33.0 us: 1.18x faster | 32.1 us: 1.21x faster |\r\n+-------------------+--------------------+-----------------------+-----------------------+\r\n| Geometric mean | (ref) | 1.03x faster | 1.09x faster |\r\n+-------------------+--------------------+-----------------------+-----------------------+\r\n```\r\n\u003c/details>\r\n\r\n\u003cdetails>\r\n\u003csummary>With \u003ccode>--enable-optimizations\u003c/code>\u003c/summary>\r\n\r\n```text\r\n+-------------------+--------------------+-----------------------+-----------------------+\r\n| Benchmark | fnmatch-filter-ref | fnmatch-filter-py | fnmatch-filter-c |\r\n+===================+====================+=======================+=======================+\r\n| small_match_none | 355 ns | 427 ns: 1.20x slower | 364 ns: 1.03x slower |\r\n+-------------------+--------------------+-----------------------+-----------------------+\r\n| small_match_some | 437 ns | 475 ns: 1.09x slower | 427 ns: 1.02x faster |\r\n+-------------------+--------------------+-----------------------+-----------------------+\r\n| small_match_all | 476 ns | 520 ns: 1.09x slower | 468 ns: 1.02x faster |\r\n+-------------------+--------------------+-----------------------+-----------------------+\r\n| medium_match_none | 2.50 us | 2.37 us: 1.05x faster | 2.20 us: 1.14x faster |\r\n+-------------------+--------------------+-----------------------+-----------------------+\r\n| medium_match_some | 3.17 us | 2.79 us: 1.14x faster | 2.71 us: 1.17x faster |\r\n+-------------------+--------------------+-----------------------+-----------------------+\r\n| medium_match_all | 3.68 us | 3.29 us: 1.12x faster | 3.11 us: 1.18x faster |\r\n+-------------------+--------------------+-----------------------+-----------------------+\r\n| large_match_none | 24.9 us | 21.5 us: 1.15x faster | 20.8 us: 1.20x faster |\r\n+-------------------+--------------------+-----------------------+-----------------------+\r\n| large_match_some | 30.6 us | 24.8 us: 1.23x faster | 24.5 us: 1.25x faster |\r\n+-------------------+--------------------+-----------------------+-----------------------+\r\n| large_match_all | 35.8 us | 29.6 us: 1.21x faster | 27.6 us: 1.30x faster |\r\n+-------------------+--------------------+-----------------------+-----------------------+\r\n| Geometric mean | (ref) | 1.06x faster | 1.13x faster |\r\n+-------------------+--------------------+-----------------------+-----------------------+\r\n``` \r\n\u003c/details>\r\n\r\n\u003cdetails>\r\n\u003csummary>Benchmark script\u003c/summary>\r\n\r\n```python\r\nimport pyperf\r\n\r\nimport _fnmatch\r\nimport os\r\nfrom fnmatch import _compile_pattern\r\n\r\ndef fnmatch_ref(loops, names, pat0):\r\n __ = range(loops)\r\n t0 = pyperf.perf_counter()\r\n for _ in __:\r\n result = []\r\n pat = os.path.normcase(pat0)\r\n match = _compile_pattern(pat)\r\n for name in names:\r\n if match(name):\r\n result.append(name)\r\n return pyperf.perf_counter() - t0\r\n\r\ndef fnmatch_py(loops, names, pat0):\r\n __ = range(loops)\r\n t0 = pyperf.perf_counter()\r\n for _ in __:\r\n pat = os.path.normcase(pat0)\r\n match = _compile_pattern(pat)\r\n res = list(filter(match, names))\r\n return pyperf.perf_counter() - t0\r\n\r\ndef fnmatch_c(loops, names, pat0):\r\n __ = range(loops)\r\n t0 = pyperf.perf_counter()\r\n for _ in __:\r\n res = _fnmatch.filter(names, pat0)\r\n return pyperf.perf_counter() - t0\r\n\r\ndef bench(runner, func):\r\n base_data = ['Python', 'Ruby', 'Perl', 'Tcl']\r\n multipliers = [('small', 1), ('medium', 10), ('large', 100)]\r\n patterns = [('none', 'A*'), ('some', 'P*'), ('all', '*')]\r\n for data_label, data_size in multipliers:\r\n for pat_label, pattern in patterns:\r\n name = f'{data_label}_match_{pat_label}'\r\n data = base_data * data_size\r\n _compile_pattern.cache_clear()\r\n runner.bench_time_func(name, func, data, pattern)\r\n\r\ndef add_cmdline_args(cmd, args):\r\n cmd.append(args.impl)\r\n\r\nif __name__ == '__main__':\r\n runner = pyperf.Runner(add_cmdline_args=add_cmdline_args)\r\n runner.argparser.add_argument('impl', choices=['ref', 'py', 'c'])\r\n args = runner.parse_args()\r\n\r\n if args.impl == 'ref':\r\n bench(runner, fnmatch_ref)\r\n elif args.impl == 'py':\r\n bench(runner, fnmatch_py)\r\n elif args.impl == 'c':\r\n bench(runner, fnmatch_c)\r\n```\r\n\u003c/details>\r\n\r\n\r\n\u003c!-- gh-linked-prs -->\r\n### Linked PRs\r\n* gh-121446\r\n* gh-123181\n\u003c!-- /gh-linked-prs -->\r\n","author":{"url":"https://github.com/picnixz","@type":"Person","name":"picnixz"},"datePublished":"2024-07-06T19:26:57Z","url":"https://github.com/python/cpython/issues/121445"}
| react-profiling | 0 |
| react-import-map | react,react-dom,react-dom/client,react-dom/profiling,react-is,react/compiler-runtime,react/jsx-dev-runtime,react/jsx-runtime,scheduler@b8488ee2c322 |
| route-pattern | /_view_fragments/issues/show/:user_id/:repository/:id/issue_layout(.:format) |
| route-controller | voltron_issues_fragments |
| route-action | issue_layout |
| fetch-nonce | v2:8d602448-649a-a202-adae-18dbe2d9f6de |
| current-catalog-service-hash | 81bb79d38c15960b92d99bca9288a9108c7a47b18f2423d0f6438c5b7bcd2114 |
| request-id | D81C:20AA01:4094907:51F13B4:6B02086F |
| html-safe-nonce | e25f6af32c27162a6c682c1d660f78f42707cca32746f90d8be8704c0ab1a5e8 |
| visitor-payload | eyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiJEODFDOjIwQUEwMTo0MDk0OTA3OjUxRjEzQjQ6NkIwMjA4NkYiLCJ2aXNpdG9yX2lkIjoiMTUwNDM4MzcwMTA1MDU5MTM0MyIsInJlZ2lvbl9lZGdlIjoiaWFkIiwicmVnaW9uX3JlbmRlciI6ImlhZCJ9 |
| visitor-hmac | 49c1f33398546a4a7d1e28c6e67fd900323f741282225a57d767e2b3eb9e450b |
| hovercard-subject-tag | issue:2393683048 |
| github-keyboard-shortcuts | repository,issues,copilot |
| google-site-verification | Apib7-x98H0j5cPqHWwSMm6dNU4GmODRoqxLiDzdx9I |
| octolytics-url | https://collector.github.com/github/collect |
| analytics-location | / |
| fb:app_id | 1401488693436528 |
| apple-itunes-app | app-id=1477376905, app-argument=https://github.com/_view_fragments/issues/show/python/cpython/121445/issue_layout |
| twitter:image | https://opengraph.githubassets.com/24c6e725d087ae0e9ecb9545aa732ea1a33b40ad65c7742b53730db51f5a24cd/python/cpython/issues/121445 |
| twitter:card | summary_large_image |
| og:image | https://opengraph.githubassets.com/24c6e725d087ae0e9ecb9545aa732ea1a33b40ad65c7742b53730db51f5a24cd/python/cpython/issues/121445 |
| og:image:alt | Enhancement By adding a C accelerator, it is possible to improve the running time of fnmatch.filter and fnmatch.translate (the previous proposal is no longer correct since fnmatch(3) does not produ... |
| og:image:width | 1200 |
| og:image:height | 600 |
| og:site_name | GitHub |
| og:type | object |
| og:author:username | picnixz |
| hostname | github.com |
| expected-hostname | github.com |
| None | 87e774ee7c6b3bee0490394e4d3e57ec9dbc956f74b87ea685dc8996c1676456 |
| turbo-cache-control | no-preview |
| go-import | github.com/python/cpython git https://github.com/python/cpython.git |
| octolytics-dimension-user_id | 1525981 |
| octolytics-dimension-user_login | python |
| octolytics-dimension-repository_id | 81598961 |
| octolytics-dimension-repository_nwo | python/cpython |
| octolytics-dimension-repository_public | true |
| octolytics-dimension-repository_is_fork | false |
| octolytics-dimension-repository_network_root_id | 81598961 |
| octolytics-dimension-repository_network_root_nwo | python/cpython |
| turbo-body-classes | logged-out env-production page-responsive |
| disable-turbo | false |
| browser-stats-url | https://api.github.com/_private/browser/stats |
| browser-errors-url | https://api.github.com/_private/browser/errors |
| release | 423dbb54c5e7bfecc838eb387c1435eb3d0e760d |
| ui-target | full |
| theme-color | #1e2327 |
| color-scheme | light dark |
| react-app-name | issues |
Links:
Viewport: width=device-width