Say you have a document with an essay written. You want to parse this essay to only select certain words. Cool.

Is using a regular expression faster than parsing the file line by line and word by word looking for a match? If so, how does it work? How can you go faster than looking at each word?

  • 6
    You assume (implying zero evidence) that a regular expression will be quicker but you don't know why it is? Maybe you should reconsider your assumption then.
    – pdr
    Nov 30, 2011 at 4:22
  • 4
    thus, the assumption. if i had evidence, it wouldn't be one, right?
    – lazeR
    Nov 30, 2011 at 4:27
  • 4
    That's not the point. The point is what led you to that assumption... You don't need evidence for your questions, but you do need reasoning for your assumptions.
    – yannis
    Nov 30, 2011 at 4:32
  • 1
    err, aren't every character of input string just moving a state machine to next state. I don't see how anyone could get that operation slow...
    – tp1
    Nov 30, 2011 at 4:56
  • 2
    I'm not sure about quicker, but my main reason for using regular expressions is due to the elegance of complex matching patterns, you simply won't find a better way to articulate it in a coding environment.
    – Mantorok
    Nov 30, 2011 at 10:54

7 Answers 7


How does it work?

Take a look at automata theory

In short, each regular expression has an equivalent finite automaton and can be compiled and optimized to a finite automaton. The involved algorithms can be found in many compiler books. These algorithms are used by unix programs like awk and grep.

However, most modern programming languages (Perl, Python, Ruby, Java (and JVM based languages), C#) do not use this approach. They use a recursive backtracking approach, which compiles a regular expression into a tree or a sequence of constructs representing various sub-chunks of the regular expression. Most modern "regular expression" syntaxes offer backreferences which are outside the group of regular languages (they have no representation in finite automata), which are trivially implementable in recursive backtracking approach.

The optimization does usually yield a more efficient state machine. For example: consider aaaab|aaaac|aaaad, a normal programmer can get the simple but less efficient search implementation (comparing three strings separately) right in ten minutes; but realizing it is equivalent to aaaa[bcd], a better search can be done by searching first four 'a' then test the 5th character against [b,c,d]. The process of optimization was one of my compiler home work many years ago so I assume it is also in most modern regular expression engines.

On the other hand, state machines do have some advantage when they are accepting strings because they use more space compared to a "trivial implementation". Consider a program to un-escape quotation on SQL strings, that is: 1) starts and ends with single quotation marks; 2) single quotation marks are escaped by two consecutive single quotations. So: input ['a'''] should yield output [a']. With a state machine, the consecutive single quotation marks are handled by two states. These two states serve the purpose of remembering the input history such that each input character is processed exactly only once, as the following illustrated:

S1->*->S1, output *, * can be any other character 
S2->'->S1, output '
S2->*->END, end the current string

So, in my opinion, regular expression may be slower in some trivial cases, but usually faster than a manually crafted search algorithm, given the fact that the optimization cannot be reliably done by human.

(Even in trivial cases like searching a string, a smart engine can recognize the single path in the state map and reduce that part to a simple string comparison and avoid managing states.)

A particular engine from a framework/library may be slow because the engine does a bunch of other things a programmer usually don't need. Example: the Regex class in .NET create a bunch of objects including Match, Groups and Captures.

  • 2
    I could not have said it better myself. The only thing I would add: Regular Expressions can also make up for lazy programmers. In the example you mentioned aaaab|aaaac|aaaad vs. aaaa[bcd]. It is worth explicitly stating that the two are mathematically equivalent and produce the same DFA, thus giving programmers more freedom to represent a regular expression in a way that makes sense (not that this is common practice, but...y'know)...
    – riwalk
    Nov 30, 2011 at 23:30
  • Thanks, this actually made sense thanks to the automata class that i took
    – lazeR
    Dec 1, 2011 at 2:30
  • Is this an example of a trivial problem where regex is overkill?: stackoverflow.com/questions/18955099/…
    – Menelaos
    Sep 23, 2013 at 9:03

Regular expressions just look fast because you have fast computers.

Back in the 1980's when 1 MIPS was a fast computer, regular expressions were a fairly big area of worry, concern and research because they were slow and ugly and compute intensive. Clever algorithm development followed and helped - but for all practical purposes these days you are seeing the miracle of fast machines papering over the cracks.

  • 2
    If you are just looking for a single word both methods are the same (or regexp is slightly slower). But given a complex expression (and text of a reasonably large size) the regular expression will probably be faster than a simple search (assuming you write the simple search simply (you can always write a complex search that is as fast)). Now weather it is significant is too general a question and you will have to look at it on a case by case basis. Nov 30, 2011 at 4:52
  • 3
    -1. The theory of regular expression dates back to the 50's and was instrumental in creating lexical analyzers (and by extension, compilers). They create very efficient state machines that (provably) use the fewest number of states possible. The resulting state machines can match complex patterns much faster than anything you could write by hand. They look fast because they are fast.
    – riwalk
    Nov 30, 2011 at 23:36
  • Might have missed my point a bit. They may be "fast" but thats all relative - there is still a bunch of work to do. Some of the other answers here bear reading as well. Dec 4, 2011 at 7:48
  • Is this answer relevant to the question ? and how 13 upvotes ?
    – Sadanand
    Jun 28, 2015 at 2:23

Why do you think they are quicker than searching the document?

There are some tricks you can do, eg. if you are searching for a 10letter word beginning with A and ending with B then if you find a A and the character 9 positions further on isn't B then you can skip some. see Knuth–Morris–Pratt algorithm


RegEx's are comparably faster to code you might write because most libraries are the result of many developers spending many years optimizing them to squeak out every last bit of performance possible. Its difficult for a single individual to duplicate that in their own search code.


What makes a regular expression fast?

Actually, they're not. Not that much. It's just that they're not slow enough for most of us to notice. Back in the 'old slow days, it was much more noticeable.

They're also not the right tool for every job - the hammer.

  • +1 Thanks for reminding me of that particular work of art...
    – yannis
    Nov 30, 2011 at 4:34

Your basic premise is wrong.

Regular expressions are not always faster than a simple search. It all depends on context. It depends on the complexity of the expression, the length of the document being searched, and a whole host of factors.

What happens is that the regular expression will be compiled into a simple parser (which takes time). Thus, if the document is small, this extra time will outweigh any advantage. Also, if the expression is simple, then the regular expression will not give you any advantage.

If the expression is complex and the document large enough, then you can gain some benefit. Whether this is significant enough to consider regular expressions to be faster will depend a lot on how much effort you want to put into the search (also regular expressions may have some optimizations that a library could provide that you would not have thought of yourself).

What I am trying to say is that there is no generalized, blanket answer. If you had a specific expression (and a known document size), then you could say derive a yes/no answer of whether the expression will be quicker than a simple search (and why).

The real advantage of regular expressions is that once you understand how to write them, the ability to express a complex search in a concise way. Because it is a generalized form, you can then build tools that allow searches in a way that is useful in the general case; it is usually at least as fast as a simple search (on documents of minimum size; on documents smaller than this it would not matter since even if it is slower, it is still fast enough).


It is plausible that in some high-level languages (perhaps javascript), using a regex library implemented in a low-level language (perhaps C) would be faster than writing parser logic in the high-level language.

Plausible - I have no idea if this is ever actually the case.

  • Nice one! That is something I too have considered. But with today's processors way faster than its predecessors, I can safely say if you write code efficiently, you will rarely be able to tell the diff. I am actually on the whole not really gaga over the entire regular expression faster hypothesis! ;-) Oct 11, 2019 at 8:22

Not the answer you're looking for? Browse other questions tagged or ask your own question.