> Your results are interesting and I'd be curious to know why the grep degrades so badly on that last regex.
I really do think it has to do with grep swapping out regex implementations based on features needed. The last regex matches a variable length string, so it may trigger a much more complex and/or cpu-intensive regex engine to be used.
> If Perl is actually being competitive in the unfair benchmark, the benchmark should be made more fair by actually putting some logic in Perl, and writing the equivalent logic in C. At that point, you would start to see C win again (modulo any inherent inefficiencies in grep's regex engine).
I see your point, but I think it's less relevant than you suppose. Regular expressions are first class citizens in Perl, just as much as Arrays and Hashes. This doesn't just mean that the syntax has some niceties, but you can actually call Perl code within the regex itself[1], and even use this feature to build a more complex regular expression as you parse[2]. Complaining that Perl uses a regex and it isn't Perl is sort of like complaining Perl is using hashes, and any fair benchmark between C and Perl should just stick to Arrays.
> Another way of putting this is: your regex wasn't actually an XML parser. Things that are actually XML parsers were slower. This is not too surprising.
Yes. I didn't want to give the impression a wrote a general purpose XML parser that beat all the C implementations I could find. I still think it's interesting that well formed regular expressions are performant enough in this circumstance to make them a preferred alternative of the many options. I could have written a simple parser in C that would have been faster, but the solution I ended up with is quite fast, robust, and very, very easy to debug.
> That would probably mean that SAX bindings for Perl to a C parser would have to take a full SAX attribute hash and turn it into a Perl attribute hash. Still, 10x is pretty bad.
I think it's more related to the fact that the actions of the regex parsing implementation when optimized sufficiently is very close in implementation to C code that steps through a char array looking for the record beginning and ending indicators, and for the content between them, and then steps through the record looking for data items and saving the key and value for each. The main benefit of using a regex in Perl is that I get what is probably a fairly close approximation (all things considered) of a C implementation of that without having to write any C, and without having to marshal data back and forth to a library to accomplish it, with very simple and concise code.
There are other tasks which obviously aren't going to be nearly as efficient in Perl, but this exchange was spurred by someone talking about Perl being very fast for a Perl-type problem, which this definitely is.
> I really do think it has to do with grep swapping out regex implementations based on features needed.
That wouldn't explain why one regex engine is 5x faster than another. Only looking at the regex engines themselves would tell you that.
> Complaining that Perl uses a regex and it isn't Perl
I'm not complaining that it uses a regex, I'm complaining that it doesn't do anything else.
A representative Perl program would use regexes and contain some logic that processes the results of those regexes.
> I think it's more related to the fact that the actions of the regex parsing implementation when optimized sufficiently is very close in implementation to C code that steps through a char array
I used to think that, but it is really not true unless your regex engine contains a JIT compiler.
Specialized machine code for a text parser (which is what you would get from writing C) is significantly faster than generic NFA/DFA code. In these tests, an average of 65% of runtime was saved when the regex engine included a JIT (ie. the specialized code was over twice as fast): http://sljit.sourceforge.net/pcre.html
> That wouldn't explain why one regex engine is 5x faster than another. Only looking at the regex engines themselves would tell you that.
It could definitely explain it, but it may not be the best explanation given the facts. I'll definitely concede that it's pure conjecture.
> A representative Perl program would use regexes and contain some logic that processes the results of those regexes.
Sure, depending on what you want to show. Nobody is trying to say Perl is as fast or faster than C, just that relatively, it's fast for the development cost it requires.
>> I think it's more related to the fact that the actions of the regex parsing implementation when optimized sufficiently is very close in implementation to C code that steps through a char array
> I used to think that, but it is really not true unless your regex engine contains a JIT compiler.
I think we're referring to different things, which is mostly my fault for being loose with my terminology. I really only meant close to C in a conceptual manner, which yields some performance benefit by keeping a large chunk of the looping and work storing specific chunks of text low level and in the interpreter. I wasn't trying to imply the regex engine's cost was negligible or the actual machine operations we comparable in a large way.
> > regex parsing implementation when optimized sufficiently is very close in implementation to C code
> I used to think that, but it is really not true unless your regex engine contains a JIT compiler.
The P6 Rules engine is written in NQP so it gets JIT'd on the JVM and MoarVM backends.
Of course it'll be many years before the engine is seriously optimized but it's a good start.
It'll be interesting to see if the code gen of this next gen regexen engine gets good enough in 2015 to make its advantages (most notably the grapheme-by-default design) actually pay dividends.
I really do think it has to do with grep swapping out regex implementations based on features needed. The last regex matches a variable length string, so it may trigger a much more complex and/or cpu-intensive regex engine to be used.
> If Perl is actually being competitive in the unfair benchmark, the benchmark should be made more fair by actually putting some logic in Perl, and writing the equivalent logic in C. At that point, you would start to see C win again (modulo any inherent inefficiencies in grep's regex engine).
I see your point, but I think it's less relevant than you suppose. Regular expressions are first class citizens in Perl, just as much as Arrays and Hashes. This doesn't just mean that the syntax has some niceties, but you can actually call Perl code within the regex itself[1], and even use this feature to build a more complex regular expression as you parse[2]. Complaining that Perl uses a regex and it isn't Perl is sort of like complaining Perl is using hashes, and any fair benchmark between C and Perl should just stick to Arrays.
> Another way of putting this is: your regex wasn't actually an XML parser. Things that are actually XML parsers were slower. This is not too surprising.
Yes. I didn't want to give the impression a wrote a general purpose XML parser that beat all the C implementations I could find. I still think it's interesting that well formed regular expressions are performant enough in this circumstance to make them a preferred alternative of the many options. I could have written a simple parser in C that would have been faster, but the solution I ended up with is quite fast, robust, and very, very easy to debug.
> That would probably mean that SAX bindings for Perl to a C parser would have to take a full SAX attribute hash and turn it into a Perl attribute hash. Still, 10x is pretty bad.
I think it's more related to the fact that the actions of the regex parsing implementation when optimized sufficiently is very close in implementation to C code that steps through a char array looking for the record beginning and ending indicators, and for the content between them, and then steps through the record looking for data items and saving the key and value for each. The main benefit of using a regex in Perl is that I get what is probably a fairly close approximation (all things considered) of a C implementation of that without having to write any C, and without having to marshal data back and forth to a library to accomplish it, with very simple and concise code.
There are other tasks which obviously aren't going to be nearly as efficient in Perl, but this exchange was spurred by someone talking about Perl being very fast for a Perl-type problem, which this definitely is.
1: http://perldoc.perl.org/perlre.html#(%3f%7b-code-%7d)
2: http://perldoc.perl.org/perlre.html#(%3f%3f%7b-code-%7d)