Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...)
September 24, 2007
Very interesting article about the relative speed of regexp implementations in popular libraries as opposed to those in grep and awk:
Regular expression matching can be simple and fast, using finite automata-based techniques that have been known for decades. In contrast, Perl, PCRE, Python, Ruby, Java, and many other languages have regular expression implementations based on recursive backtracking that are simple but can be excruciatingly slow. With the exception of backreferences, the features provided by the slow backtracking implementations can be provided by the automata-based implementations at dramatically faster, more consistent speeds.
[via Patrick Logan]
About
This page contains a single entry from Stefan Tilkov's Random Stuff posted on September 24, 2007 11:29 PM. The previous post in this blog was Steve Vinoski Does Erlang, Too. The next post in this blog is HTTP Errors Poster. Many more can be found on the main index page or by looking through the archives.