git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: git diff looping?

From
Paolo Bonzini <paolo.bonzini@gmail.com>
Date
Jun 17, 2009, 11:02 UTC
Message-ID
<4A38CD33.9020402@gmail.com>
In-Reply-To
<20090617102332.GA32353@coredump.intra.peff.net>
Show 9 quoted lines
>   system,  orig:   0.22s
>   system, paolo:   0.22s
>   system,   ".":   0.15s
>   compat,  orig: 150.88s
>   compat, paolo:   0.43s
>   compat,   ".":   0.15s
> 
> Besides the exponential behavior on the original regex, it is still
> about twice as slow as the system one.

The reason is that the glibc regex is a DFA-based matcher. It is much slower on regexes with backreferences, but otherwise it is faster.

>   1. Replace the builtin diff.java.xfuncname pattern with what Paolo
>      suggested (though I haven't verified its correctness beyond a
>      cursory look at the results).
I checked it a bit harder, but still it is not easy to check because of 
the false positives in the original regex.  I'm pretty sure it's correct 
  though; I find it even easier to read (though longer) than the 
original one.
>      I haven't looked at how large or how portable the glibc
>      implementation is.

Decently portable, but I don't think it's worth it. Users that write regexes so complex should know of the exponential behavior, I think.

Paolo
Previous: Jeff KingNext: Andreas Ericsson
Message 24 of 37 in “git diff looping?”
  1. John BitoJun 16, 2009
  2. Jeff EplerJun 16, 2009
  3. John BitoJun 16, 2009
  4. Jeff KingJun 16, 2009
  5. Jeff KingJun 16, 2009
  6. 1/2 Makefile: refactor regex compat supportJeff King, Jun 16, 2009
  7. Johannes SixtJun 16, 2009
  8. Jeff KingJun 16, 2009
  9. 1/2 Makefile: refactor regex compat supportJeff King, Jun 16, 2009
  10. 2/2 Makefile: use compat regex on SolarisJeff King, Jun 16, 2009
  11. Brandon CaseyJun 16, 2009
  12. Mike RalphsonJun 17, 2009
  13. Mike RalphsonJun 17, 2009
  14. 2/2 Makefile: use compat regex on SolarisJeff King, Jun 16, 2009
  15. John BitoJun 16, 2009
  16. Junio C HamanoJun 16, 2009
  17. Jeff KingJun 16, 2009
  18. Brandon CaseyJun 16, 2009
  19. John BitoJun 16, 2009
  20. Jeff KingJun 16, 2009
  21. Brandon CaseyJun 16, 2009
  22. Paolo BonziniJun 17, 2009
  23. Jeff KingJun 17, 2009
  24. Paolo BonziniJun 17, 2009
  25. Andreas EricssonJun 17, 2009
  26. Paolo BonziniJun 17, 2009
  27. Andreas EricssonJun 17, 2009
  28. Paolo BonziniJun 17, 2009
  29. avoid exponential regex match for java and objc function namesPaolo Bonzini, Jun 17, 2009
  30. demerphqJun 17, 2009
  31. Jeff KingJun 17, 2009
  32. demerphqJun 17, 2009
  33. Paolo BonziniJun 17, 2009
  34. Junio C HamanoJun 17, 2009
  35. Paolo BonziniJun 18, 2009
  36. John BitoJun 16, 2009
  37. Jeff KingJun 16, 2009

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.