（1）はこちら、（⁠2）はこちらから。

データ構造

本節では、主に複数の文字列を保持するデータ構造について、配列を中心に比較します。前節では文字列単体の照合や書き換えを行っていましたが、複数の文字列を扱う場合は、どのようなデータ構造を使うのが高速か、効率的かについてベンチマークを取ります。

ある値が一覧に含まれるかはexists()を使う

ある文字列が一覧で定義した文字列と一致するかどうかを確認することは多いでしょう。たとえば、ドロップダウンリストから選択された値が有効であることや、URLやメールアドレスのドメイン部分が自社保有のドメイン名であることを検査する、などです。

次のコードでは、メールのReply-Toヘッダが一覧に含まれることの確認方法を、メールヘッダ名を要素として持つ配列に対するgrep()関数と、キーとして持つハッシュに対するexists()関数で比べたものです。

my $A = ['From', 'Reply-To', 'To'];
my $H = {'From' => 1, 'Reply-To' => 1, 'To' => 1};
sub usegrep {
    my $v = 'Reply-To';
    return 1 if grep { $v eq $_ } @$A;
}
sub hashkey {
    my $v = 'Reply-To';
    return 1 if exists $H->{ $v };
}

考察：exists()がgrep()に快勝

表6に示すとおり、ハッシュのキーとしてデータを持つほうが1.8倍も高速でした。

では、要素数がもっと多い場合はどうでしょうか。誌面には掲載していませんが、本誌サポートサイトで配布するサンプルコードのgrep-list-vs-exists-hash-100.plに、要素数を100個にした場合のベンチマークを載せています。100要素の場合はさらに大差となり、exists()関数でハッシュのキーを調べる方法が20倍ほど高速でした。

このように大きな差が生まれる理由は、計算量の違いによるものです。ソートされていない配列に対するgrep()関数[2]の計算量はO(n)です。つまり、入力データnの量に比例して計算時間が増えます。一方、exists()関数でハッシュのキーを確認する方法は計算量がO(1)です。つまり、ハッシュのサイズに関係なく計算量は一定です。よって、データ量が多ければ多いほど、要素の一覧をハッシュのキーとして持つほうが高速になります。

さて、配列とハッシュで異なるデータ構造の比較ですので、それぞれのメモリ使用量も確認しましょう。メモリ使用量は、変数が使用しているメモリサイズを調べるDevel::Sizeモジュールを使うと、バイト単位で得られます。同モジュールのtotal_sizeで計測したメモリサイズは、配列$Aが214バイト、ハッシュ$Hが380バイトでした。表7に示すとおり、ハッシュは配列に比べメモリ使用量が1.3倍程度です。このくらいの増加であれば、ハッシュを使うほうが速度面での利点が大きく、効率的でしょう。

要素数の少ないデータには配列を使う

前項のベンチマークでは配列よりもハッシュのキーが圧倒的に速かったため、配列は使いどころがない印象を持つかもしれませんが、そうではありません。適材適所です。

たとえばPerlのコアモジュールであるTime::Pieceは内部で日付データを配列として保持[3]しているとおり、要素数が少ないデータを保持するには配列のほうが高速です。

次のコードは、バウンスメールに現れる、送信できなかった宛先を示す項目Final-Recipient:の3要素を配列とハッシュで定義し、戻り値がFinal-Recipient:neko@nyaan.jpとなるコードを、それぞれ比べたものです。

my $A = ['final-recipient', 'rfc822', '[email protected]'];
my $H = {
    'field' => 'final-recipient',
    'type' => 'rfc822',
    'value' => '[email protected]'
};
sub ar { return $A->[0].': '.$A->[2] }
sub hs { return $H->{'field'}.': '.$H->{'value'} }

考察：配列がハッシュに快勝

表8に示すとおり、配列が1.3倍高速でした。いずれの計算量もO(1)なので大差はつきませんが、要素数が少なく、ほとんど変更がなく、何度も参照される変数ならば、配列として保持する選択は効率面からしても十分検討に値するでしょう。

エラーメッセージの照合には配列を使う

バウンスメールに現れるエラーメッセージは多種多様です。メールサーバソフトウェアごと、メールサービスごと、そしてエラーの種類ごとに、エラーメッセージのパターンが種々雑多に存在します。

次のコードは、あるエラーメッセージがSMTP接続時に拒否されたものであるかどうかを、配列とx修飾子[4]指定の正規表現で比較したものです。前者は複数のエラーメッセージを文字列として保持する配列に対するgrep()関数とindex()関数で、後者はパターンとして保持する正規表現に対する照合で比べています。

my $Fa = 'Delivery failed, blacklisted by rbl';
my $Re = qr{(?>
    access[ ]denied[.][ ]ip[ ]name[ ]lookup[ ]failed
    |... # エラーメッセージパターンの正規表現がいくつか
    |blacklisted[ ]by
    )
}x;
my $Ar = [
    'access denied. ip name lookup failed',
    ..., # エラーメッセージ文字列がいくつか
    'blacklisted by',
];
sub regex { return 1 if $Fa =~ $Re } # 正規表現で照合
sub grep1 {
    # 配列に対するgrep()で照合
    return 1 if grep { index($Fa, $_) > -1 } @$Ar;
}

考察：配列に対するgrep()が正規表現に圧勝

表9に示すとおり、配列に対してgrep()関数で回してindex()関数で照合するほうが、正規表現より2.7倍も高速でした。ただし、これは多くが固定文字列で構成される正規表現であったからこそ、配列に書き換えられた一例です。数値や文字を範囲としてとらえる必要があるなら、正規表現を使わないのは非効率的です。

正規表現と配列、まったく違うデータ構造を比較していますので、メモリの使用量も見てみましょう。Devel::Sizeモジュールのtotal_sizeで計測したメモリサイズは、正規表現$Reは216バイト、配列$Arは457バイトでした。メモリ使用量は2倍以上の差ですが、定数のように扱われる変数であり、プログラム全体が使うメモリ量からすると誤差の範囲です。そして読みやすさも向上しています。この例は、速度と保守性が両立する有用な書き換えだと筆者は考えます。

配列の末尾を参照するには負の添え字を使う

本項は、本節の主題であるデータ構造の比較ではありませんが、すべてのベンチマークで登場した配列について触れます。配列の末尾の要素を参照する方法は、配列の最後の添え字を得る$#配列名よりも、負の添え字を使うほうが速いと広く知られていますが、どの程度の差があるのかを確認するためにも紹介します。

次のコードは、$#配列名を使った例と負の添え字を使った例で、1から100までの数字を入れた配列に対して、それぞれ配列の末尾の値（100）と、末尾から2番目の値（99）を足して返すサブルーチンで比較します。

my @A = (1..100);
sub ds { return ($A[$#A] + $A[$#A - 1]) }
sub ni { return ($A[-1] + $A[-2]) }

考察：負の添え字が$#に楽勝

表10のように、やはり負の添え字を使ったほうが高速でした。2倍以上の差がありますし、記号の連続よりも読みやすい表記であることから、配列の末尾を参照するには負の添え字で$v[-1]と書きましょう。

ループ処理にはforeachを使う

本項も前項と同じく、配列を扱います。配列をループで回す方法として、forとforeachとwhileの3つの選択肢を比べましょう。

次のコードでは、1から256までの数字を要素に持つ配列から、偶数である要素数を数えるコードを例に、C形式のfor[5]とイテレータとして動作するforeachとwhileを比較します。

sub loop1f {
    my $v = 0;
    my @p = (1..256);
    for( my $e = 0; $e < 256; $e++ ) {
        $v++ if $p[$e] % 2 == 0;
    }
    return $v;
}
sub loop2e {
    my $v = 0;
    my @p = (1..256);
    foreach my $e ( @p ) {
        $v++ if $e % 2 == 0;
    }
    return $v;
}
sub loop3w {
    my $v = 0;
    my @p = (1..256);
    while( my $e = shift @p ) {
        $v++ if $e % 2 == 0;
    }
    return $v;
}

考察：foreachがwhileとC形式のforに快勝

表11に示すとおり、結果はforeachの一強となりました。whileはイテレータが返す値を取り回すのにも使用しますが、C形式のforはめったに必要となりませんので、1.6倍も速いforeachの一択でしょう。

しかし、高速化を理由として常にwhileをforeachに書き換えられるとは限りません。whileではshift()関数で代入時に偽となっていたコードが、foreachでは偽とならないケースがあります。詳しくは、本誌サポートサイトで配布するサンプルコードfails-onforeach-loop.plで確認してください。このような落とし穴もありますので、ループを書き換える場合は周辺のロジックも含めて確認、測定、変更が必要です。

全体の性能を測るプロファイリング

ここまで紹介した例のとおり、Benchmarkモジュールでのベンチマークは部分としてのコードを競わせるものです。部分的に高速であるからと言って、スクリプト全体やシステム全体でも高速であるとは限りません。「⁠木を見て森を見ず」とはよく言ったもので、プロファイリングによるプログラム全体やシステム全体での比較は必須です。

筆者は、ベンチマークの結果、最も高速であった書き方を適用したコードと適用する前のコードを別ブランチで切り離し、それぞれDevel::NYTProfモジュールを使ってプロファイリングをしたうえで、正式採用するかどうかを決定しています。

nytprofhtmlで結果を見やすくする

Devel::NYTProfモジュールが出力するnytprof.outはバイナリファイルですので、そのままでは読めません。付属のnytprofhtmlコマンドを実行すると作られるnytprof/index.htmlをブラウザで開き、結果の検証や副作用の有無を確認しましょう。

プロファイリング用Makefile

とはいえ、筆者はすぐにプロファイリングで使うコマンドや引数を忘れます。そこで、次の内容でMakefileにprofileターゲットを定義して、ターミナルからmakeprofileを実行するだけで完了するようにしています。

CODE := 'Sisimai->make(shift, delivered => 1)'
MAIL := tmp/emails-for-speed-test

profile:
    perl -d:NYTProf -Ilib -MSisimai -lE $(CODE) $(MAIL)
    nytprofhtml

プロファイリング結果の検証

図1はwhileを、図2はfor[1]をそれぞれループ処理に使ったプロファイリング結果です。行単位でぶつ切りにしたメールヘッダを、ヘッダ名とヘッダの値の組となるようハッシュに変換する処理で、前節でのベンチマーク結果と同じく、プログラム全体としてもfor（7.06ms）を使ったほうがwhile（41.9ms）より速いとわかります。

部分でも全体でもforがwhileに勝るので、この結果をもって筆者はコードの書き換えを行いました。一方、部分が高速であっても全体が遅くなってしまったプロファイリング結果なら、書き換えを行いません。

まとめ

インフラを触るときの戒め「まずは計測せよ」と同様に、コードの改善もまずはベンチマークです。やり方は一つだけではないので、普段動かしているPerlのコードは改善する余地をたくさん残しているかもしれません。これも、Perlのおもしろさであると筆者は考えます。

実際、Sisimaiでも改善できる点がたくさんありました。本稿で紹介したベンチマークや紹介できなかったベンチマーク、そしてプロファイリングの結果に基づき、正規表現の削減とハッシュと配列の適材適所を意識して、Sisimaiのリファクタリングを兼ねた高速化に挑戦してきました。その結果、2017年12月にリリースしたバージョンと、本稿執筆時点でのmasterブランチで、約1.8倍の高速化を達成しています。

ただし、ベンチマークを始める場合、速度を求めるあまりスピード狂の魔物とならぬよう、境界となる線引きを設けましょう。たとえば、保守性が著しく損なわれていないかのレビューを受ける、n倍以上の高速化であれば採用するなどの基準は必要でしょう。

なお、本稿で紹介したベンチマーク結果は、実行環境やPerlのコンパイルオプションの違い、そして未来にリリースされるPerlで異なるかもしれませんので、まずは自分で測定することが大切です。

さて、次回の執筆者は藤原俊一郎さんで、テーマは「AWS X-Rayによる分散トレーシング」です。お楽しみに。

本誌最新号をチェック！
WEB+DB PRESS Vol.130

2022年8月24日発売
B5判／168ページ
定価1,628円
（本体1,480円＋税10%）
ISBN978-4-297-13000-8

• 特集1
  イミュータブルデータモデルで始める
  実践データモデリング
  業務の複雑さをシンプルに表現！
• 特集2
  いまはじめるFlutter
  iOS/Android両対応アプリを開発してみよう
• 特集3
  作って学ぶWeb3
  ブロックチェーン、スマートコントラクト、NFT