Google RE2
Regular expressions (regex) provide a means for matching text, whether characters, words, or patterns. They can be infinitely expressive and yet typically compact. An example is "[hc]at", which would match "hat" and "cat".
The implementation of regular expressions in almost all programming languages today allow for backreferences. Backreferences allow you to reuse part of the regex match later in the regular expression. For example "<([A-Z][A-Z0-9]*)\b[^>]*>.*?</\1>" would match any opening and closing html tag and the text in-between. The "\1" is used to reference the part of the regex in parenthesis, in this case, the type of tag we're trying to match. Thus, we can ensure that the we get the same type of beginning and ending tags.
Backtracking sounds really cool, but we run into a problem. Regular expressions containing backreferences have a potential for exponential run time and unbounded stack (memory) usage. Unbounded stack usage in typical regular expression implementations leads to stack overflows and server crashes and all sorts of terrible things. That is to say, under certain circumstances, evaluating a regular expression over a large enough input could hang forever, use up all memory allocated to it, or both. This is a very important problem in Google's case.
Enter bright computer scientists. Basing their approach on automata and computational theory (I took that class!), Google researchers have created RE2, a "principled approach to regular expressions". It claims the implementation guarantees that searches complete in linear time with respect to the size of the input and won't overflow the stack space. They have limited the worst case runtime by removing support for backexpressions, however.
In his paper "Regular Expression Matching Can Be Simple And Fast", Russ Cox, the Google engineer who also authored the press release, writes, "Given a choice between an implementation with a predictable, consistent, fast running time on all inputs or one that usually runs quickly but can take years of CPU time (or more) on some inputs, the decision should be easy." For Google, yes. For those who like fancy syntactic sugar, it's still great to have another option.
Sources and Further Reading:
Google RE2 Press Release
Wikipedia
The Command Line
regular-expressions.info
Code Repository: RE2 on Google Code
SpaceShipTwo Takes Off →
Yes, I know health care just passed. Yes, I know there's unrest in Jerusalem and Thailand. Yes, I know Greece is taking the world economy down with it. But this is so much cooler.
Oh, Foxtrot. Thank you.
The Secret Origin of Windows →
The history of the Windows 1.0 and 2.0 releases from the perspective of program manager Tandy Trower.
How often have I said to you that when you have eliminated the impossible, whatever remains, however improbable, must be the truth?
— Sherlock Holmes, A Study in Scarlet
Can you send that logo over in electron form, at the highest granularity you have.
— (via clientsfromhell)
How a Web Design Goes Straight to Hell →
And that's why I don't do web design for anyone but myself.
Anything that is in the world when you're born is normal and ordinary and is just a natural part of the way the world works. Anything that's invented between when you're fifteen and thirty-five is new and exciting and revolutionary and you can probably get a career in it. Anything invented after you're thirty-five is against the natural order of things.
— Douglas Adams
Things are rarely just crazy enough to work, but they're frequently crazy enough to fail hilariously.
— http://xkcd.com/580/ (hovertext)
Packing a Firearm →
A wonderful social engineering hack on how to ensure that expensive things actually get to where they're going with no additional screening when flying.