@Tim: the regex module includes some extra checks to reduce the chance of excessive backtracking. In the case of the OP's example, they seem to be working. However, it's difficult to know when adding such checks will help, and your example is one case where they are being done but aren't helping, with the result that it's slower.