On Fr, 03 Okt 2014, Bram Moolenaar wrote: > Christian wrote: > > > Bram, > > here is patch, that will switch from the NFA engine to the BT regular > > expression engine when there are too many states encountered. I have > > tested it on some input on which the NFA engine was slow (issue #164) > > and it worked. I made it so, that when verbose is set, Vim outputs > > whenever it switches the engines. This will however only be done, when > > 're' is set to 0 > > > > I am however not sure, what a good measure is, when to abort the NFA > > engine and switch to the old engine, but that could easily be switched. > > Interesting idea. I think the limit on the number of states is just a > first guess. Some states are cheap (e.g. matching one specific > character), some are expensive (e.g. when doing recursive stuff). At > some point this can be tuned. Please move the decision to one central > function.
Which decision? It is already at one central state (though not in a separate function, but that would just change one if condition by another). > Some things in the BT engine are also expensive, such as two multis in a > row: ".*a*". There are many alternatives to try then. > > I consider this a start to make the choice of engine more clever. > We also need some kind of benchmark to be able to tune the choice. Updated patch includes a test, that creates a benchmark.out text file which uses issue# 164 provided file and pattern to measure performance of each 're' engine. Please note, it uses a search() call with a timout value of 10,000 milliseconds to avoid having the benchmark run forever. Unfortunately, that parameter does not help at all. We might have another bug here. Here is some sample output for my machine: chrisbra@debian ~/code/vim/src/testdir (hg)-[default]- % make test_zzz_benchmark_re.out rm -rf test_zzz_benchmark_re.failed test.ok test.out X* viminfo cp test_zzz_benchmark_re.ok test.ok # Sleep a moment to avoid that the xterm title is messed up. # 200 msec is sufficient, but only modern sleep supports a fraction of # a second, fall back to a second if it fails. VIMRUNTIME=../../runtime; export VIMRUNTIME; ../vim -u unix.vim -U NONE --noplugin -s dotest.in test_zzz_benchmark_re.in " Benchmark_results: file: samples/re.freeze.txt, re: 0, time: 2.088939 file: samples/re.freeze.txt, re: 1, time: 2.079487 file: samples/re.freeze.txt, re: 2, time: 14.093581 Best, Christian -- Hallo Trockenföner! -- -- 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.
