4 ms·

I have not looked at the other linear-time implementations to see what they do, but I expect they all use one of these two approaches. Python's glob() (fnmatch

• rsc 10y ago
  Thanks for pointing this out. I wrote a Python test program but forgot to run that test in the data collection for the graphs. I will update them once the tests finish running. Ironically, Python must be passing the glob to an exponential-time regexp library, since Python is on the slow side of the fence.
  • willvarfar 10y ago
    Russ, while you're around, thanks for re2! RE2::Set especially! But why is RE2::Set so underdocumented and underpromoted? All regex libraries need this functionality.
    • rsc 10y ago
      You're welcome. I think basically all of RE2 is underdocumented and underpromoted. Why should RE2::Set be any different? Seriously, though, it was a bit of an afterthought. A team at Google was |ing together a ton of regexps and came to me for something better, so I wrote RE2::Set. I'm glad it helps others too.
  • js2 10y ago
    Your previous article on regex engines I think indicated that Python's is backtracking and with poor performance.
    • rsc 10y ago
      Indeed, I just didn't want to presume that nothing had changed in the past 10 years (but apparently not).
  • dom0 10y ago
    Yep, Python's "re" is the usual PCRE+X story.
    • js2 10y ago
      Python has its own engine which is not based on PCRE AFAIK: https://github.com/python-git/python/blob/715a6e5035bb21ac49382772076ec4c630d6e960/Modules/_sre.c https://github.com/python-git/python/blob/715a6e5035bb21ac49...
      • xapata 10y ago
        I noticed you linked to python-git instead of the main Python repo. The whole project has been moved as of a couple months. https://github.com/python/cpython https://github.com/python/cpython
        • js2 10y ago
          Yeah, that was a mistake on my part but by the time somone pointed it out I couldn't edit my comment anymore. Sorry. :-(
  • ot 10y ago
    Python's regex library compiles the regex to a sequence of opcodes and then does recursive descent, so yes, it's exponential.
• orf 10y ago
  That implementation looks pretty inefficient, creating lots of strings that are thrown away immediately. Could it not be refactored into a generator combined with a string.join?
  • dom0 10y ago
    Usual use would be "translate pattern once, compile it and then match 1000 file names against it".
    • orf 10y ago
      Ahh yes, it's cached in fnmatchcase. It's pretty fast as well, <10µs for a basic match.
      • bluetech 10y ago
        A cache without any eviction! Probably should not expose `fnmatch` to the network where the pattern varies.
        • dom0 10y ago
          The RE engine here is only used as a fast VM; so the pathological cases from the article should still apply. So apart from the memory use issues there's also that.
        • orf 10y ago
          It should be updated with a functools.lru_cache decorator I think.
        • benhoyt 10y ago
          That's an old version of Python source from a mirror. It uses functools.lru_cache with a maxsize of 256 now: https://github.com/python/cpython/blob/fcfe80ec2592fed8b3941c79056a8737abef7d3b/Lib/fnmatch.py#L38 https://github.com/python/cpython/blob/fcfe80ec2592fed8b3941...
• dom0 10y ago
  Here is the same but with star and doublestar for handling slashes: https://github.com/borgbackup/borg/blob/master/src/borg/shellpattern.py#L5 https://github.com/borgbackup/borg/blob/master/src/borg/shel... http://borgbackup.readthedocs.io/en/stable/usage.html#borg-help-patterns http://borgbackup.readthedocs.io/en/stable/usage.html#borg-h... ("Shell-style patterns, selector sh:")