#環境

OS: Windows 10 Professional 1803 (.NET Framework 4.7.2を含む)
CPU: Core i7-7500U
メモリ: 8GB
正規表現エンジン：.NET準拠（PowerShell 5.1上でベンチマーク）

以下の内容は、処理系（正規表現エンジンの違いなど）により結果が変わってくる可能性があります。

#特定の文字列を含まない行の正規表現（昔：POSIX拡張正規表現）
特定の文字列（たとえば「ABCD」）を含まない行にマッチする正規表現は、否定先読み (?!…) が使えなかった頃は例えば下記のように複雑な形でした。

　 ^([^A]|A+(BC?A+)*([^BA]|B([^CA]|C([^DA]|$)|$)|$))*$
(又は ^([^A]|A+(BC?A+)*([^BA]|B([^CA]|C[^DA])))*(A+(BC?A+)*(BC?)?)?$)

従来型NFAと呼ばれる正規表現エンジンでは、同じパターンを表す正規表現でも書き方により速度が異なります。例えば、上記の正規表現を少し書き換えた下記のの形の方が速いです。

　^[^A]*(A+(BC?A+)*([^BA]|B([^CA]|C([^DA]|$)|$)|$)[^A]*)*$
(又は ^[^A]*(A+(BC?A+)*([^BA]|B([^CA]|C[^DA]))[^A]*)*(A+(BC?A+)*(BC?)?)?$)

上記の正規表現は、対象文字列の長さが１つ増加する毎にその複雑さが増します。また、対象文字列の最初に同じ文字が続く場合、例えば「AACD」を含まない正規表現は単に「B」を「A」に置き換えるだけでは駄目で、例えばは下記の様に修正する必要があるなど難しすぎてあまり実用的ではありません。

　　^[^A]*(A(A+CA)*([^A]|A+([^CA]|C([^DA]|$)|$)|$)[^A]*)*$
(又は^[^A]*(A(A+CA)*([^A]|A+([^CA]|C[^DA]))[^A]*)*(A(A+CA)*(A+C?)?)?$)

#特定の文字列を含まない行の正規表現（今：.NET、PCREなど）
上記のに、PCRE（Perl Compatible Regular Expressions: Perl5互換正規表現ライブラリ）や .NET などの新しい正規表現エンジンで利用可能となっている「否定先読み (?!…)」、「キャプチャ抑止 (?:…)」、「バックトラック抑止 (?>…)」などを活用した以下の６つのバリエーションを加えてベンチマークしてみました。

^(?!.*ABCD).*$
^(?!.*?ABCD).*$
^(?:(?!ABCD).)*$
^(?>[^A]+|A(?!BCD))*$
^(?>[^A]*(?:A(?!BCD)[^A]*)*)$
^(?>[^A]*(?:A+(?:BC?A+)*(?:[^BA]|B(?:[^CA]|C(?:[^DA]|$)|$)|$)[^A]*)*)$

※ 最後のは否定先読みを利用していません（に対してグループのキャプチャ抑止、バックトラックの抑止を適用）。
※ (2023.3.25追記) とをそれぞれ ^(?>(?:(?!ABCD).)*)$、^(?>(?:[^A]+|A(?!BCD))*)$ に変更してみましたがベンチマークの順位が変わる程の変化はありませんでした。

##ベンチマークの方法
以下の PowerShell関数で各正規表現の検索に要する時間（10000回の試行の平均値、単位:ミリ秒）を求めます。

$io = gc "（WikipediaのHTMLソースファイルのパス）" -Raw

Function Test($Regex) {
    $num = 10000
    $pat = '(?s)' + $Regex
    $tot = 0
    for($i=0; $i -lt $num; $i++) {
        $res = Measure-Command {
            $r=@(Select-String -Pattern $pat -InputObject $io)
        }
        $tot += $res.TotalMilliSeconds
    }
    Write-Output $($tot/$num)
    Write-Output $($r.Matches.Length)
}

パフォーマンスの差異を際立たせるために検索対象の文字列（行）をかなり長めに設定しました。具体的には、シングルラインモード（各正規表現の先頭に (?s) を付加し、ピリオド (.) を改行 (\n) にもマッチさせる）で、2018年元旦時点における日本語版Wikipedia の正規表現のページのHTMLソース全体を1つの行として扱います。

##ベンチマーク結果（マッチする場合）

日本語版Wikipediaの正規表現のページのHTMLソースファイルには、「ABCD」という文字列は含まれません。したがって、上記～の正規表現でこのファイルを検索するとマッチします。その検索に要した時間の平均値は下記の通りです。

正規表現	所要時間 [msec]
	41
	9.1
	27
	30
	42
	9.2
	7.6
	8.5

上記の結果より、除外対象文字列「ABCD」の先頭の文字「A」が見つかった場合に後続の文字列が「BCD」でないことをテストするが最も速いという結果となりました。はよく利用されるやより 3倍以上速いです。また、否定先読みを利用しないが健闘しているのが分かります。との結果の差に、グループのキャプチャがもたらすオーバヘッドが表れています。

##ベンチマーク結果（マッチしない場合）
検索対象の文字列（行）の先頭部分に位置する「<htm」と末尾部分に位置する「</ht」のそれぞれの文字列について、それらを含まない検索をした結果を下記に示します（実際には含まれるためマッチしません）¹。

正規表現	所要時間（"ABCD" → "<htm"）[msec]	所要時間（"ABCD" → "</ht"）[msec]
	0.07	74
	0.07	44
	19	8.5
	0.06	22
	0.06	56
	0.06	5.8
	0.06	4.8
	0.07	5.6

やはり～が速く、よく使われるやより10～100倍以上も早い場合があることが分かります。との結果を比較すると、(?>…)でバックトラックを抑止した効果が大きいことが分かります。
　ちなみに、のみ左側の数値の方が右側より大きくなっている理由は、否定先読みにおいて、検索対象文字列の末尾から前方に向かって除外対象の文字列が見つかるか先頭に達してマッチに失敗するまでバックトラックが発生するためです（除外対象の文字列が後方にあるほどバックトラックの回数が少ない）。欲張りでない（non-greedy）量指定子（ *? ）を使ったは、とは１文字違いですが、除外対象の文字列を先頭から探すためベンチマーク結果に大きな差が出ています²。今回のベンチマークでは非常に長い文字列を検索対象としておりにはやや不利な条件でした。

ベストパフォーマンス賞

複雑すぎず、どんなケースでも速いという意味で、今回調べた中での勝者はとなりました。

開始・終了を示す文字列で囲まれた範囲にマッチする正規表現

「BEGIN」と「END」の２つの文字列で囲まれた（最も内側の）領域にマッチする正規表現を考えると、その２つの文字列の間には「BEGIN」や「END」の文字が含まれてはなりません。これを、よく使われるに似た正規表現で表すと

BEGIN((?:(?!BEGIN|END).)*)END

となり、上のベンチマークで最速であったに似た正規表現で表すと

BEGIN([^BE]*(?:(B(?!EGIN)|E(?!ND))[^BE]*)*)END

となります。

HTMLタグのペアで囲まれた最も内側の範囲にマッチする正規表現は、開始と終了を示す文字列が似ているので少し形が変わります。<div…> と </div> のペアの場合は、に似た正規表現では

<div(?:"(?:[^"\\]|\\.)*"|'(?:[^'\\]|\\.)*'|[^'">])*>((?:(?!</?div)[\S\s])*)</div>

ですが、に似た正規表現では

<div(?:"(?:[^"\\]|\\.)*"|'(?:[^'\\]|\\.)*'|[^'">])*>([^<]*(?:<(?!/?div)[^<]*)*)</div>

となり数倍速くなります³。

注：正規表現全体を一重（または二重）引用符で囲む場合は、上記の一重（二重）引用符は2個ずつ必要になります。
　
　
2019.02.13更新（HTMLタグのペアで囲まれた最も内側の範囲にマッチする正規表現の誤りを修正）
　
クリエイティブ・コモンズ表示 - 継承 4.0 国際

今回のベンチマークでは、バックトラックの影響を確認するために非常に長い文字列を検索対象としています。検索対象の文字列の長さが短い場合には「</ht」を含まない文字列検索のベンチマーク結果は「<htm」を含まない文字列検索の結果に近い値になることが予想されます（以外）。は検索対象の文字列の長さが短くなると、両方（「<htm」と「</ht」）の所要時間が短くなります。 ↩
否定先読みを利用しない裏技的な ^(?>(?:.*ABCD)?)^.*$ や ^(?>(?:.*?ABCD)?)^.*$ のベンチマーク結果はとほぼ同じになります。 ↩
1～52桁までは開始タグに対応するパターンです（引用符の考慮のために長くなっています）。 ↩