Tady už optimalizovali jiní...
Někteří autoři knihoven regexpů jdou tak daleko, že využívají vestavěného kompilátoru jazyka a kompilují stavový automat definovaný regulárním výrazem rovnou do nativního kódu. Výsledky jsou znát:
http://www.weitz.de/cl-ppcre/#performance
Když se nad tím zamyslím, tak to je docela pochopitelné. Vytvoření objektu v Pythonu nejspíš není úplně levná záležitost a volání .match() nad objektem téměř celé proběhne v C.