Why is `\s+` so much faster than `\s\s*` in this Perl regex?
<p>Why does replacing <code>\s*</code> (or even <code>\s\s*</code>) with <code>\s+</code> result in such a speedup for this input?</p>

<pre><code>use Benchmark qw(:all);
$x=(" " x 100000) . "_\n";
$count = 100;
timethese($count, {
    '/\s\s*\n/' =&gt; sub { $x =~ /\s\s*\n/ },
    '/\s+\n/' =&gt; sub { $x =~ /\s+\n/ },
});
</code></pre>

<p><a href="http://rextester.com/QQYBD22619" rel="nofollow noreferrer">Link to online version</a></p>

<p>I noticed a slow regex <code>s/\s*\n\s*/\n/g</code> in my code - when given a 450KB input file consisting of lots of spaces with a few non-spaces here and there, and a final newline at the end - the regex hung and never finished.</p>

<p>I intuitively replaced the regex with <code>s/\s+\n/\n/g; s/\n\s+/\n/g;</code> and all was well.</p>

<p>But why is it so much faster? After using <code>re Debug =&gt; "EXECUTE"</code> I noticed the <code>\s+</code> version is somehow optimised to run in only one iteration: <a href="http://pastebin.com/0Ug6xPiQ" rel="nofollow noreferrer">http://pastebin.com/0Ug6xPiQ</a></p>

<pre class="lang-none prettyprint-override"><code>Matching REx "\s*\n" against "       _%n"
Matching stclass ANYOF{i}[\x09\x0a\x0c\x0d ][{non-utf8-latin1-all}{unicode_all}] against "       _%n" (9 bytes)
   0 &lt;&gt; &lt;       _%n&gt;         |  1:STAR(3)
                                  SPACE can match 7 times out of 2147483647...
                                  failed...
   1 &lt; &gt; &lt;      _%n&gt;         |  1:STAR(3)
                                  SPACE can match 6 times out of 2147483647...
                                  failed...
   2 &lt;  &gt; &lt;     _%n&gt;         |  1:STAR(3)
                                  SPACE can match 5 times out of 2147483647...
                                  failed...
   3 &lt;   &gt; &lt;    _%n&gt;         |  1:STAR(3)
                                  SPACE can match 4 times out of 2147483647...
                                  failed...
   4 &lt;    &gt; &lt;   _%n&gt;         |  1:STAR(3)
                                  SPACE can match 3 times out of 2147483647...
                                  failed...
   5 &lt;     &gt; &lt;  _%n&gt;         |  1:STAR(3)
                                  SPACE can match 2 times out of 2147483647...
                                  failed...
   6 &lt;      &gt; &lt; _%n&gt;         |  1:STAR(3)
                                  SPACE can match 1 times out of 2147483647...
                                  failed...
   8 &lt;       _&gt; &lt;%n&gt;         |  1:STAR(3)
                                  SPACE can match 1 times out of 2147483647...
   8 &lt;       _&gt; &lt;%n&gt;         |  3:  EXACT &lt;\n&gt;(5)
   9 &lt;       _%n&gt; &lt;&gt;         |  5:  END(0)
Match successful!
</code></pre>

<pre class="lang-none prettyprint-override"><code>Matching REx "\s+\n" against "       _%n"
Matching stclass SPACE against "       _" (8 bytes)
   0 &lt;&gt; &lt;       _%n&gt;         |  1:PLUS(3)
                                  SPACE can match 7 times out of 2147483647...
                                  failed...
</code></pre>

<p>I know Perl 5.10+ will immediately fail the regex (without running it) if a newline is not present. I suspect it is using the location of the newline to reduce the amount of searching it does. For all cases above it seems to cleverly reduce the backtracking involved (usually <code>/\s*\n/</code> against a string of spaces would take exponential-time). Can anyone offer insight into why the <code>\s+</code> version is so much faster?</p>

<p>Also note that <code>\s*?</code> does not offer any speedup.</p>