Dominique Pellé <[email protected]> wrote: > > Hi > > > > The regexp .\{1,9000} is very slow with the new regexp engine > > compared to the old engine. Compare the timing of those 2 > > commands where the only difference is set re=1 vs set re=2: > > > > $ time vim -X -u NONE \ > > -c 'set re=1' \ > > -c 'call feedkeys("ihello\<esc>/.\\{1,9000}\<cr>:q!\<cr>")' > > > > real 0m0.004s > > user 0m0.000s > > sys 0m0.004s > > > > > > $ time vim -X -u NONE \ > > -c 'set re=2' \ > > -c 'call feedkeys("ihello\<esc>/.\\{1,9000}\<cr>:q!\<cr>")' > > > > real 0m6.499s > > user 0m6.432s > > sys 0m0.020s > > > > => new regexp engine is 1624x times times slower here. > > > > Is this a known limitation of the new NFA regexp engine? > > > > Regards > > Dominique > > > Changing the value of n in the regexp .\{1,n} > I see that the time it takes to match quadruples > when doubling n with the new regexp engine. > > => This means that complexity is O(n^2): > > With the old regexp engine, the time is constant. > > regexp re=1 re=2 > ------------------------------ > .\{1,1000} 0.004s 0.064s > .\{1,2000} 0.005s 0.305s > .\{1,4000} 0.005s 1.230s > .\{1,8000} 0.005s 4.799s > .\{1,16000} 0.005s 20.902s > > This was measured using for n=16000 for example using: > > $ time vim -X -u NONE -c 'set re=2' \ > -c 'call feedkeys("ihello\<esc>/.\\{1,16000}\<cr>:q!\<cr>")'
Is this specific for matching with "."? I would expect the old engine to be slower when what's being matched may fail. The problem is that the engine tries to find the longest match, which may start at any character. Thus for every character there is another state to be kept. It's not so easy to think of a way that works better and works in general. There are two special cases here: - Matching dot, which matches everywhere. If it would be more specific, such as "[abc]" there wouldn't so many states. - Nothing follows, thus the match that started first will always win. If something follows the old engine is probably much slower. -- A meeting is an event at which the minutes are kept and the hours are lost. /// Bram Moolenaar -- [email protected] -- http://www.Moolenaar.net \\\ /// sponsor Vim, vote for features -- http://www.Vim.org/sponsor/ \\\ \\\ an exciting new programming language -- http://www.Zimbu.org /// \\\ help me help AIDS victims -- http://ICCF-Holland.org /// -- -- You received this message from the "vim_dev" maillist. Do not top-post! Type your reply below the text you are replying to. For more information, visit http://www.vim.org/maillist.php --- You received this message because you are subscribed to the Google Groups "vim_dev" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/d/optout.
