New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Speed lost on /^(foo|bar|baz)$/ match #9461
Comments
From @schwernCreated by @schwernI was testing out an efficiency claim and discovered that 5.10 and #!/usr/bin/perl -w use strict; use Benchmark qw(cmpthese); my $token = "open"; cmpthese(shift || -3, { $ bleadperl ~/tmp/bug.plx 5000000 $ perl5.8.8 ~/tmp/bug.plx 5000000 $ perl5.10.0 ~/tmp/bug.plx 5000000 Can anyone duplicate? Perl Info
|
From @smpetersOn Fri Aug 22 15:28:29 2008, schwern wrote:
Yes, I can duplicate. The first is 5.8.8. The second is bleadperl. Steve Peters steve@picard:~/perl-current$ perl bench.pl 5000000 |
The RT System itself - Status changed from 'new' to 'open' |
From nospam-abuse@bloodgate.comMoin, On Wednesday 27 August 2008 05:16:12 Steve Peters via RT wrote:
What I find interesting is that the "eq" case got faster :) All the best, Tels -- "Never offend people with style when you can offend them with -- Sam Brown |
From @demerphqGiven the pattern involved at first look it seems this is related to the With perl 5.8: demerphq@dromedary:blead:~/perl$ perl bug58280.pl With blead: demerphq@dromedary:blead:~/perl$ ./perl -Ilib bug58280.pl This is with the trie optimisation disabled: From this I assume that the majority of the slowdown comes from the So then what happens when we change the token being matched? After all 'open'=~/^(open|close|read)$/ Which is a benchmark which is virtually designed to make the old With 5.8 we see the expected slowdown: demerphq@dromedary:blead:~/perl$ perl bug58280.pl With blead we see the expected unchanged performance of a trie: demerphq@dromedary:blead:~/perl$ ./perl -Ilib bug58280.pl So now, if we add a bunch more terms to the test: #!/usr/bin/perl -w use strict; use Benchmark qw(cmpthese); my $token = "read"; cmpthese(shift || -3, { We see perl 5.8's performance continue to fall off: demerphq@dromedary:blead:~/perl$ perl bug58280.pl And we see perl 5.10's performance again stay more or less static: demerphq@dromedary:blead:~/perl$ ./perl -Ilib bug58280.pl Also, the performance difference of the 'eq' cases suggests that perl as Anyway, my conclusion is that this isnt really a bug. Its a place where I view this more as a notice that we could spend some time making regex Yves |
From @schwernFWIW it got worse. perl5.10.1 here is the latest maint5.10. $ time perl5.10.0 ~/tmp/bench.plx 5000000 real 0m21.322s $ time perl5.10.1 ~/tmp/bench.plx 5000000 real 0m23.734s Even so, I don't think this should be holding up 5.10.1. |
From @obraOn Tue Jul 07 19:34:55 2009, schwern wrote:
I'm removing this performance issue as a 5.12 blocker as it's not a |
From @jkeenanOn Tue Jul 07 19:34:55 2009, schwern wrote:
FWIW, here are some comparisons: Linux/i386: $ /usr/bin/perl 58280.pl 5000000 $ /usr/local/bin/perl5.12.0 58280.pl 5000000 $ perl 58280.pl 5000000 Darwin/PPC: $ /usr/bin/perl 58280.pl 5000000 $ /usr/local/bin/perl5.12.0 58280.pl 5000000 $ perl 58280.pl 5000000 It appears that things improved on both OSes between 5.12 and 5.14. Does this ticket have to remain open? Thank you very much. |
From @iabynOn Tue, May 01, 2012 at 06:22:00PM -0700, James E Keenan via RT wrote:
It shows that things have got better, but still not as good as under In the meantime I suggest keeping the ticket open. -- |
From @khwilliamsonHere are the 5.19.10+ blead numbers on a Linux box: Rate regex regex_opt eq And if we change $token to 'read', we get Rate regex regex_opt eq -- |
From [Unknown Contact. See original ticket]Here are the 5.19.10+ blead numbers on a Linux box: Rate regex regex_opt eq And if we change $token to 'read', we get Rate regex regex_opt eq -- |
From @iabynOn Sat, Mar 29, 2014 at 08:29:46PM -0700, Karl Williamson via RT wrote:
I think the important thing is how much slower the trie optimisation is for 5.008009 regex 10526316/s And here's the same with TRIEs disabled (${^RE_TRIE_MAXBUF} = -1): 5.008009 regex 10309278/s and with TRIEs enabled and $token as 'read', i.e. $token matches the third 5.008009 regex 8438819/s and with TRIEs enabled and with Yves modification, i.e. $token matches the 5.008009 regex 4807692/s What I conclude from the above is that: * as with all such micro benchmarks, a certain amount of the variation is -- |
From @demerphqOn 1 April 2014 17:40, Dave Mitchell <davem@iabyn.com> wrote:
Pretty much the same thing I concluded too. :-)
It definitely can be. Unusually we trade speed for space in the trie If I get time I will look at changing the trie/aho code to use the
I also agree here. Yves |
@demerphq, ping |
I am not sure what to do about this. We use a compressed state transition table that means each transition is more expensive than it could be, but which gracefully handles large alphabet patterns. We actually have two construction methods however, one using a fixed width uncompressed "standard" table, and one using a more complex list representation for large alphabets, at the end of construction we convert both of those formats into a final compressed format. The idea behind the compressed format is from the "red dragon book". You can see it in action below.
We build a map table that converts the unique characters into ids, which are then represented by columns in the tables. The first table shows the "native construction" (tabular), the second shows the same table in compressed form. The idea behind the compression is to overlay states on top of each other so they can use each other "fail transitions" for their own "real transitions", by using a "check" value for each transition. When a state looks at a transition that it doesn't own, it knows it is actually a fail transition. This means each state has its own offset into the transition blob. Notice that in the typical state transition table there are many states that only have one transition, in fact besides the initial state most of the state transitions are fails. This means that where the typical dfa loop would be something like:
we have code more like this:
I would guess this extra bookkeeping accounts for some of the slowdown, but it is also what makes it possible to have patterns with thousands of distinct characters in them without blowing out ram too much. The other thing is each trie opcode has a fairly high setup cost in the regex engine itself. We have to initialize various vars to have the right tables, etc. It is certainly possible we could rethink things so that we can use a more efficient loop, and reduce the setup costs. I am not sure I am up to the task in the short term. But i thought would dump this here for feedback. |
Migrated from rt.perl.org#58280 (status was 'open')
Searchable as RT58280$
The text was updated successfully, but these errors were encountered: