regexps aren't regular, so most "proper" engines also do backtracking.

Indeed, if you stick with the regular subset, you can be really fast:

http://swtch.com/~rsc/regexp/regexp1.html