title: Backtracking in regexp faster than expected
body: <p>According to <a href="http://perldoc.perl.org/perlre.html#%28?%3Epattern%29">perlre</a>, the following code should take several seconds to execute:</p>
  
  <pre><code>$ time perl -E '$_="((()" . ("a") x 18;  say "ok" if m{ \(([^()]+|\( [^()]* \))+\)}x;'
  
  real    0m0.006s
  user    0m0.000s
  sys 0m0.005s
  </code></pre>
  
  <p>The documentation says:</p>
  
  <blockquote>
    <p>Consider how the pattern above detects no-match on
    <code>((()aaaaaaaaaaaaaaaaaa</code> in several seconds, but that each extra
    letter doubles this time.</p>
  </blockquote>
  
  <p>As seen, it only takes a fraction of a second on my laptop..
  Even running with a million <code>a</code>'s completes in half a second:</p>
  
  <pre><code>$ time perl -E '$_="((()" . ("a") x 1000000;  say "ok" if m{ \(([^()]+|\( [^()]* \))+\)}x;'
  
  real    0m0.454s
  user    0m0.446s
  sys 0m0.008s
  </code></pre>
  
  <p>What am I missing here?</p>