◆ 正規表現で検索(固定文字列)では全然遅くならないです
◆ むしろ indexOf が遅い

indexOf と search (正規表現の先頭だけと全体) と startsWith でマッチのある場合とない場合で速度比較してみます

計測コード

var longlongstring = "aiueo".repeat(4194304)
console.log("indexOf-Match")
console.time("indexOf-Match")
longlongstring.indexOf("aiueo")
console.timeEnd("indexOf-Match")

console.log("indexOf-NoMatch")
console.time("indexOf-NoMatch")
longlongstring.indexOf("aiue0")
console.timeEnd("indexOf-NoMatch")

console.log("search-Match")
console.time("search-Match")
longlongstring.search(/aiueo/)
console.timeEnd("search-Match")

console.log("search-NoMatch")
console.time("search-NoMatch")
longlongstring.search(/aiue0/)
console.timeEnd("search-NoMatch")

console.log("searchF-Match")
console.time("searchF-Match")
longlongstring.search(/^aiueo/)
console.timeEnd("searchF-Match")

console.log("searchF-NoMatch")
console.time("searchF-NoMatch")
longlongstring.search(/^aiue0/)
console.timeEnd("searchF-NoMatch")

console.log("startsWith-Match")
console.time("startsWith-Match")
longlongstring.startsWith("aiueo")
console.timeEnd("startsWith-Match")

console.log("startsWith-NoMatch")
console.time("startsWith-NoMatch")
longlongstring.startsWith("aiue0")
console.timeEnd("startsWith-NoMatch")

結果

JavaScript なので実行するごとに変化が大きいですがだいたいこんなものになりました

Chrome
indexOf-Match
indexOf-Match: 108.550ms
indexOf-NoMatch
indexOf-NoMatch: 48.244ms
search-Match
search-Match: 0.041ms
search-NoMatch
search-NoMatch: 47.810ms
searchF-Match
searchF-Match: 0.075ms
searchF-NoMatch
searchF-NoMatch: 0.039ms
startsWith-Match
startsWith-Match: 0.020ms
startsWith-NoMatch
startsWith-NoMatch: 46.129ms

indexOf がマッチしたほうが遅いという意外な結果に
マッチしないと最後まで繰り返すことになって遅そうなのに

そして 正規表現の search
早い!!

先頭の一致だけと制限しなくても indexOf より早いです
先頭だけ一致のと制限があるとマッチしなかった時がすごく早いです

startsWith は専用の関数なので indexOf みたいに最後まで探索しないので早いはず と思ったのですがマッチしなかった時は遅いです
indexOf と大差ないのでもしかすると内部は indexOf の結果が 0 以上とかだったり?

Firefox
indexOf-Match
indexOf-Match: タイマー開始
indexOf-Match: 11.85ms
indexOf-NoMatch
indexOf-NoMatch: タイマー開始
indexOf-NoMatch: 66.34ms
search-Match
search-Match: タイマー開始
search-Match: 0.76ms
search-NoMatch
search-NoMatch: タイマー開始
search-NoMatch: 61.44ms
searchF-Match
searchF-Match: タイマー開始
searchF-Match: 0.43ms
searchF-NoMatch
searchF-NoMatch: タイマー開始
searchF-NoMatch: 1.02ms
startsWith-Match
startsWith-Match: タイマー開始
startsWith-Match: 0.34ms
startsWith-NoMatch
startsWith-NoMatch: タイマー開始
startsWith-NoMatch: 0.33ms

こっちは素直な結果です
想像通りって感じ

最近は JavaScript の速度は Firefox も早くなってきてますね
それなのになんか全体的な動きが遅い印象なんですが JavaScript エンジンじゃなくてブラウザ本体が重いのかな

まとめ

正規表現にしたから極端に遅くなったりはしないようです
. とか * などで複雑なことをしなければですが

Chrome は相変わらず早いのですが 予想通りな結果になってくれないです

追記

Chrome 48 で試してみると startsWith はマッチしなくても早くなってました
indexOf-Match
indexOf-Match: 122.543ms
indexOf-NoMatch
indexOf-NoMatch: 51.323ms
search-Match
search-Match: 0.032ms
search-NoMatch
search-NoMatch: 51.094ms
searchF-Match
searchF-Match: 0.047ms
searchF-NoMatch
searchF-NoMatch: 0.044ms
startsWith-Match
startsWith-Match: 0.008ms
startsWith-NoMatch
startsWith-NoMatch: 0.003ms