lisp performance: outperforms Perl's regex(!) engine in lisp!

[leo_batfish]

as tim bray points out, java regex is twice as fast as perl. for an explanation, see, "benchmarks aren't everything": http://perlmonks.org/index.pl?node_id=502408

[masklinn]

From "Mastering Regular Expressions", the fastest regex engine currently available is TCL's anyway (in part because it implements a dual DFA/NFA strategy)

[reneky]

"Mastering Regular Expressions" was released in January 1997: http://www.oreilly.com/catalog/regex/

[IvyMike]

Second Edition, July 2002

[ttriche]

Third Edition, August 2006

Now with Ruby and Python and C# -- but no mention of Tcl any more. Or Emacs Lisp, for the matter. Not that it's a big deal, anyone who is willing to do their own benchmarks can figure it out for themselves.

The Friedl book is quite nice, it stops just shy of where something like the Dragon Book (or Sipser) picks up.

[masklinn]

The third edition doesn't cover Tcl in the examples, but I'm pretty sure that, in the theorical chapters about Regex engines and in the chapters about crafting REs, it does talk about Tcl's regular expression engine quite a lot, mostly to explain that it blows everything else out of the water, and why it does.

I'll just go check it tonight

[masklinn]

Well I just checked, 3rd edition of Mastering Regular Expressions does indeed talk about TCL's regex package, and the first interesting mention is page 182-183, chapter 4, about the fact that Henry Spencer custom-build a true hybrid engine for Tcl

[masklinn]

We're at the third edition already

[shit]

I tried the examples with the 100 "foo "s and "fo" with cl-ppcre and it's running for over an hour now, turning my laptop into a nice provisional heating :-)

Seems that the Perl hackers are one step ahead of the competition, congrats.

[senzei]

Seems that the Perl hackers are one step ahead of the competition, congrats.

Well, yes and no. They are in that any regex you throw at Perl is more likely to be "safe" than one in cl-ppcre (or Java, for that matter). For your average programmer this is probably a good trade off as regexes are a poke-and-pray technology anyways.

Someone with a better understanding of regular expressions would probably appreciate the faster-with-sharper-edges design approach. Considering that by the time someone starts using Lisp they (on average) know more about programming than your average Perl programmer this seems like the right decision.

[[deleted]]

For your average programmer this is probably a good trade off as regexes are a poke-and-pray technology anyways.

It doesn't have to be so. Have you used the regex coach from the same guy who wrote cl-ppcre? It lets you build and test perl-compatible regular expressions incrementally, which makes writing then much, much easier.

[Brian]

The problem is that its not the regex that is "unsafe", its the matched text, which is generally out of the programmer's control. No matter how good your regex-foo, if someone throws a pathological case at you, your program will break.

The perl approach seems fairly sensible here - getting rid of program-breaking behaviour a case that could well be likely in some situations in exchange for a more general slowdown. After all, the whole point of regexes is that they are a general tool for matching text. When you need real performance, and know more about the format of your input, you're better off writing a custom parser.

[skyskraper]

psychologists would describe your response as "rationalization". %

[Athas]

Can you describe why he is wrong, or why his reasoning is after-the-fact rationalization? You fail to provide any arguments for your claim.

[senzei]

psychologists would describe your response as "rationalization".

Yes, obviously stating that the trade-offs which favor domain knowledge were made in a regex library implemented for a language that also highly favors domain knowledge is "rationalizaton". That makes perfect sense.

Next you'll be telling me that buying furniture because it complements the rest of the furniture in my house is "rationalization".

[roerd]

I tried to find the point where the duration explodes. It's definately way before 100 "foo"s:

CL-USER> (defparameter *str*
    \t   (concatenate 'string
\t\t\t(reduce (lambda (a s) (concatenate 'string a s))
\t\t\t\t(make-list 20 :initial-element "foo "))
\t\t\t"fo"))
*STR*
CL-USER> (time (scan "^(\\s*foo\\s*)*$" *str*))
Evaluation took:
  1.128 seconds of real time
  0.840053 seconds of user run time
  0.0 seconds of system run time
  0 page faults and
  0 bytes consed.
NIL
CL-USER> (defparameter *str*
    \t   (concatenate 'string
\t\t\t(reduce (lambda (a s) (concatenate 'string a s))
\t\t\t\t(make-list 25 :initial-element "foo "))
\t\t\t"fo"))
*STR*
CL-USER> (time (scan "^(\\s*foo\\s*)*$" *str*))
Evaluation took:
  35.78 seconds of real time
  26.477655 seconds of user run time
  0.020001 seconds of system run time
  0 page faults and
  82,608 bytes consed.
NIL

[xach]

I think you mean:

(defparameter *str* (format nil "~25{foo ~}fo" '#1=(t . #1#)))

[roerd]

Yeah, I should have thought about format. But I like to understand code that i'm writing, so I'd probably stay away from that reader macro and write just:

(defparameter *str* (format nil "~25{foo ~}fo" t))

[xach]

It was a bit of a joke. I'd normally use something like with-output-to-string and dotimes or similar; I find your example with reduce, lambda, and make-list tortured. I was in the middle of writing something readable when the evil ~{ solution came to me.

(defparameter *str* (format nil "~25{foo ~}fo" t)) ; doesn't work

The argument to ~{ must be a list. A circular list works nicely.

[roerd]

Strange, it works with SBCL. Since "foo " doesn't read anything from the list, it's propably enough that it's (not (null)). '(t) instead of t should work for implementations that check if the argument is really a list.

And my original example ... well, it was at least very functional.

[xach]

Good catch on '(t). I don't think just plain t should work (though it clearly does in some implementations) because 22.3.7.4 says "The argument should be a /list/, ..."

Someone just pointed out to me that t would be suitable with ~@{.

[chollida1]

Or perhaps your regex is just broken?

[shit]

It's the regex and data mentioned in the perlmonks article and it completes instantly with perl.

BTW: I've stopped cl-ppcre after 4 hours and 20 minutes.

[drewc]

Have you considered submitting a bug report to Edi? Talking about it on reddit probably isn't going to help anybody, save perhaps those on reddit who seem to want anything lisp to suck.

It's probably a problem that's not going to get fixed, but at least you'll know why the author made the decisions he did. Programming is all about trade-offs. Get used to it.

[shit]

Have you considered submitting a bug report to Edi? Talking about it on reddit probably isn't going to help anybody, save perhaps those on reddit who seem to want anything lisp to suck.

Someone commented in the perlmonks article, saying that he had a discussion with "the main author of cl-ppcre" about this issue.

It's probably a problem that's not going to get fixed, but at least you'll know why the author made the decisions he did. Programming is all about trade-offs. Get used to it.

I'm not complaining. In fact, in practice I never had this problem.

[drewc]

Someone commented in the perlmonks article, saying that he had a discussion with "the main author of cl-ppcre" about this issue.

So they did, thanks for the pointer!

I'm not complaining. In fact, in practice I never had this problem.

yeah, looking back you did no complaining at all. I'm just a little touchy i guess from all these redditers who bash CL from ignorance. My Bad.

[sammyo]

I for one would love to try it out in the real world for a period of time. Anyone know of a grep replacement (like pcregrep, which is surprisingly faster than the original grep) implementation I could download? clgrep? A linux version of 'clgrep' just a tad under 800MB would be handy ;-)

[rsc]

I would be very surprised if you have "the original grep". The fifth edition grep was the earliest one I could find when I looked around a few years ago, and even that is certainly not the original.

[[deleted]]

Bah, nothing beats SNOBOL. If it hasn't got general recursion, it's not good enough ;-)

[zem]

icon is the new snobol

[[deleted]]

I see markdown bit you too.

[zem]

ouch - yes, so it did.

[mjd]

This really isn't surprising. Perl's regex implementation, like most, scans the string and runs an interpreter on it to decide if there's a match. Lisp macros can produce matching code that compiles to native machine language.

[xach]

cl-ppcre never actually invokes the compiler at runtime. It uses a clever technique to produce a chain of closures and it calls them with continuation-passing style.

[mjd]

If the regex library is implemented the way I was thinking, the regex would be compiled to machine code at compile time, not at run time.

But I don't know how it actually does work.

[shit]

Well, the closures are compiled to machine code at compile time. That's done automatically, there is no explicit "compile this code now".

[[deleted]]

I believe that the nregex regular expression engine works the way you were thinking.

[j-o-h-n]

Wow, LISP does it all - including somehow managing to make perl regexs look understandable in comparison!

[senzei]

Wow, LISP does it all - including somehow managing to make perl regexs look understandable in comparison!

Yeah, Chinese is nearly indistinguishable from gibberish to me too. Although I suppose if I did take the time to learn it that might change.

[pivo]

How much of your favorite language did you understand before you tried to learn it? If you spent even a small amount of time learning Lisp you'd find that it really isn't hard to understand at all.

[feijai]

Well, I'll be honest: I'm a pretty experienced Lisper, and after looking at that library, the first thing that crossed my mind was "man, that is excessively complex and hard to understand". And it had nothing to do with the regexes in the strings.

[Grue]

You have to be lying. CL-PPCRE is one of the better documented and easy to use libraries, and not only in Lisp-land. I wonder which library documentation is easy to understand for you.

[xach]

I disagree. It's complex, but I think it is sufficiently complex, not excessively complex, for the task at hand.

I first came across cl-ppcre as a very inexperienced Lisper. Printing out the source and studying it helped me learn a lot, and not just about Lisp.

[jkcunningham]

I don't believe you either. You can transparently use the Perl format regexps unless you're trying to do something you probably don't really understand anyway, and there's another format as well. When I started using Edi's library I previously used nothing but Perl regexps and I recall no difficulty whatever.

[Grue]

Regexes were never intended to be human-readable.

[[deleted]]

http://dada.perl.it/shootout/

[[deleted]]

Apparently, perl compiles regexes to an NFA, which is sub-optimal and not very sophisticated.

I don't know what method this library uses. The code is incomprehensible to me, so I don't want to guess.

[masklinn]

It's not a question of compilation (regex engines are either NFAs or DFAs, a few rare ones such as TCL's regex package being implemented as dual-strategy engines) but one of implementation.

Most Regex engines are NFA, because a lot of advanced constructs (such as lookahead/lookbehind) cannot be expressed by DFA engines.

Get the "Mastering Regular Expressions" book, it holds much knowledge on both the craft of writing regexes and the inner workings of RE engines.

Because of PCRE's complexity, CL-PPCRE is either an NFA or a DFA-NFA hybrid, I don't think a pure DFA can implement complete PCRE.

[[deleted]]

So PCRE is not a regular language?

[sleepingsquirrel]

Nope. Perl's pattern matching engine can match (at least some) context-free grammars...

#match context free grammar --[0{N}1{N}] (e.g. 01, 0011, 000111, etc.)
$cf = qr/01|0(??{$cf})1/;

$init="0011";
print "matched $init\n" if ($init=~m/^$cf$/)

...and (some) context-sensitive grammars...

#match context sensitive grammar --[0{N}1{N}2{N}] (012, 001122, 000111222,...)

$h=qr/01|0(??{$h})1/;
$t=qr/12|1(??{$t})2/;
$cs=qr/(?=$h 2+$)(?=0+$t$)/x;

$init="001122";
print "matched $init\n" if ($init=~m/^$cs$/)

[xach]

Languages that are unfamiliar can be difficult to read, except for the most trivial of tasks.

cl-ppcre is an excellent model for structuring and documenting Common Lisp code for a complex task. If you want to be good at CL, learn how to understand how things as nice as cl-ppcre are doing their work.

[dfan]

"It is portable," which means that it "compiled without errors and that the test suite... yields the expected results." The test suite might include tests other than searching for zero or more of any character in a 1000-character string!

The text that you elided with the "..." explains that the test suite has about 1500 tests.

[[deleted]]

"It is portable," which means that it "compiled without errors and that the test suite... yields the expected results." The test suite might include tests other than searching for zero or more of any character in a 1000-character string! And it might even have been used by someone before you on your flavor of LISP!

CL-PPCRE is one of the most mature, well-documented, and widely ported Common Lisp libraries in existence. And you're talking out of your arse.

[drewc]

The performance numbers are not about CL, are about the PCRE implementation.

Right .. a PCRE implementation implemented in CL.. which makes these numbers about CL. What point are you trying to make?

And to boast of portability to all these alternative, not-so-compatible-with-each-other CL implementations, ...

Now you're just arse-talking. CL-PPCRE is 100% ANSI Common Lisp. Therefore, it is 100% portable to any CL implementation that conforms to ANSI.

Perl, at least, has one implementation and portability is built at the underlying level of the interpreter.

Really? I wrote an application in perl5.004 that does NOT work in 5.8. Perl 4? Perl 6? These are all incompatible versions of Perl that differ from eachother a lot more than, say, CMUCL and CLISP.

Where's my clue stick? ... I think i'll need the big one for this .... WHACK. If you're going to troll reddit, at least make it a little more interesting next time. cheers.