Регулярные выражения в Python неожиданно замедляются

Рассмотрим следующий код Python:

import timeit
import re

def one():
        any(s in mystring for s in ('foo', 'bar', 'hello'))

r = re.compile('(foo|bar|hello)')
def two():
        r.search(mystring)


mystring="hello"*1000
print([timeit.timeit(k, number=10000) for k in (one, two)])
mystring="goodbye"*1000
print([timeit.timeit(k, number=10000) for k in (one, two)])

По сути, я тестирую два способа проверки существования одной из нескольких подстрок в большой строке.

Что я здесь получаю (Python 3.2.3) такой вывод:

[0.36678314208984375, 0.03450202941894531]
[0.6672089099884033, 3.7519450187683105]

В первом случае регулярное выражение легко побеждает выражение any- регулярное выражение сразу находит подстроку, в то время как anyдолжно проверять всю строку пару раз, прежде чем она доберется до правильной подстроки.

Но что происходит во втором примере? В случае, когда подстрока отсутствует, регулярное выражение работает на удивление медленно! Это меня удивляет, так как теоретически регулярное выражение должно пройти по строке только один раз, в то время как выражение anyдолжно пройти по строке 3 раза. Что здесь не так? Есть ли проблема с моим регулярным выражением, или в этом случае регулярные выражения Python просто медленные?