¿Por qué /^(.+)+Q$/.test("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX ") tarda tanto?

Question

Cuando corro

/^(.+)+Q$/.test("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX") 

en Chrome o IE, se tarda unos 10 segundos en completarse. (Firefox puede evaluarlo casi al instante.)

¿Por qué tarda tanto? (¿Y por qué/cómo Firefox puede hacerlo tan rápido?)

(Por supuesto, nunca hubiera ejecutado esta expresión regular en particular, pero estoy llegando a un problema similar con la expresión regular de URL en http://daringfireball.net/2010/07/improved_regex_for_matching_urls y parece se reducen a esto, es decir, hay ciertas direcciones URL que hará que el navegador se bloquee)

por ejemplo:

var re = /\b((?:https?:\/\/|www\d{0,3}[.]|[a-z0-9.\-]+[.][a-z]{2,4}\/)(?:[^\s()<>]+|\(([^\s()<>]+|(\([^\s()<>]+\)))*\))+(?:\(([^\s()<>]+|(\([^\s()<>]+\)))*\)|[^\s`!()\[\]{};:'".,<>?«»“”‘’]))/i; 
re.test("http://google.com/?q=(AAAAAAAAAAAAAAAAAAAAAAAAAAAAA") 

Answer 1

como se indica por thg435, suena como respaldo de seguimiento catastrófica. Hay un excelente artículo sobre esto, Regular Expression Matching Can Be Simple And Fast.

Describe un enfoque eficiente conocido como Thompson NFA. Como se señaló, sin embargo, esto no es compatible con todas las características de las expresiones regulares modernas. Por ejemplo, no puede hacer referencias retrospectivas. Sin embargo, como se sugiere en el artículo:.

"A pesar de ello, sería razonable utilizar la simulación NFA de Thompson para expresiones más regulares, y sólo poner de manifiesto el retroceso cuando es necesitaba una aplicación especialmente inteligente podría combinar los dos, recurriendo a retroceder solo para acomodar las referencias inversas ".

Sospecho que Firefox puede estar haciendo esto.