100万回の I love you を Garoon ちゃんに送りたい

Garoon PHP 機能改善

この記事は、CYBOZU SUMMER BLOG FES '24 (Newcomer Stage) DAY 2の記事です。

初めまして、Webアプリケーションエンジニア職としてサイボウズに24年新卒で入社したFujiです。

唐突ですが、皆さんは、『100万回の「I love you」』という曲をご存知でしょうか？ とても素敵な曲ですので、未視聴の方、是非とも下のリンクから1度ご視聴ください！！！

さて、この曲のイントロに『「愛してる」の言葉じゃ足りなくらいに君が好き　「愛してる」の言葉を100万回君に送ろう』というフレーズがあります。


Cybozu社の製品であるGaroonちゃんにも、「愛してる」の言葉を100万回送りたいですよね？

私は送りたいです(自己解決)




閑話休題。

Garoon開発チームへの配属が7月初旬に決まり、Garoon内での所属サブチーム決定にあたって複数のサブチームのチーム体験を、各チームに3-5日程度させていただきました。

今回はGaroonの性能に関する問題に取り組んでいるチーム(Nozomiチーム)での5日間の体験にて、Garoonちゃんに100万回の「愛してる」をメールで送ろうとしたお話です。

問題

長文メールの折りたたみ処理に多大な時間を要する。

タスク背景

Garoonではメール転送の際にRFC 5322に準拠してメール本文の1行の文字長が一定の長さを超えないよう、改行を自動挿入(折りたたみ)します。また、改行を挿入する際にはGaroon独自の禁則処理が実行されます。

禁則処理（きんそくしょり）とは、漢字文化圏の文書作成・組版において、「約物などが行頭・行末などにあってはならない」などとされる禁止事項、または、それらを回避するために字詰めや文の長さを調整したりすること。　(出典: フリー百科事典『ウィキペディア（Wikipedia）』)

例えば、パソコンからこの記事を閲覧してくださっている方であれば、ブラウザの横幅を大きくしたり、小さくしたりしながら、次の英文の各行末の英単語に着目してみてください。

Cybozu, Inc. (サイボウズ株式会社, Saibōzu Kabushikigaisha) is a Tokyo-based software company that provides web-based groupware services including Cybozu Office and kintone. In addition to the main office in Tokyo, Cybozu also has offices in Matsuyama and Osaka, as well as several overseas subsidiaries in countries including Vietnam,[2] China,[3] Australia[4] and the United States.[5] The U.S.-based subsidiary, kintone Corporation, is located in San Francisco, California. (From Wikipedia, the free encyclopedia)

おそらく、ブラウザの横幅に応じて文中の改行位置が変化したと思います。また、行末の英単語が途中で改行されることはない(例えば、subsidiaries という単語の途中、subsiとdiariesの間に改行が入ることはない)はずです。これはブラウザによる折りたたみと禁則処理です。

Garoonにおいては、メールでの折りたたみ処理と禁足処理に多大な実行時間とメモリを消費するケースが存在することが報告されていました。

タスクのゴール

従来の仕様に準拠したまま、改行の自動挿入処理と禁則処理の高速化を行う

改修前の模擬コード

ここでは、Fujiが作成したコードに対し、4つの改善を行います。よければ一緒に考えてみてください！

全体の流れは次のようになっています

  1. 処理済みのデータ$processed_text、処理済みの文字数$current_position、を初期化
  2. fold_text関数は、受け取ったデータに対して処理済み文字数を起点として次の区切り文字までの1行を$lineとして切り出す
  3. 処理済みの文字数$current_positionを$lineの末尾となるよう更新
  4. 切り出した1行の折りたたみ：fold_line_to_fit_width関数
    1. 1行が指定幅$max_widthに収まるよう、前半と後半に分割
    2. 禁則処理を行う(行頭禁則処理、行末禁則処理)
    3. 後半が存在するなら、後半部分に対してa-cを再帰的に実行
  5. 処理済みデータ末尾に4の結果を改行文字と共に追加
  6. 以降、データの「処理済みの文字数$current_position」以降に改行が存在しなくなるまで2-5を繰り返す
<?php
function fold_text($main_message) {
    $processed_text = '';
    $current_position = 0;

    while (($next_newline_position = mb_strpos($main_message, "\n", $current_position)) !== false) {
        $line = mb_substr($main_message, $current_position, $next_newline_position - $current_position);
        $current_position = $next_newline_position + 1;
        $foldedLine = fold_line_to_fit_width($line);
        $processed_text .= $foldedLine . "\n";
    }

    // 最後の行の処理
    $lastLine = mb_substr($main_message, $current_position);
    $processed_text .= fold_line_to_fit_width($lastLine);
    return $processed_text;
}

function fold_line_to_fit_width($line) {
    $max_width = 80; // 1行の最大byte数,簡単のため実際の上限とは異なる

    if (mb_strlen($line) <= $max_width) {
        return $line;
    }

    $first_part = mb_substr($line, 0, $max_width);
    $remaining_part = mb_substr($line, $max_width);

    if (preg_match('/^[)]/u', $remaining_part)) {
        // 行頭禁則処理
    }

    if (preg_match('/[(]$/u', $first_part)) {
        // 行末禁則処理
    }

    // 再帰的に残りの部分を処理
    $foldedRemaining = fold_line_to_fit_width($remaining_part);
    return $first_part . "\n" . $foldedRemaining;
}

改善その1：mb_strpos関数のループを削除

まずはテストデータ(2万行,24万文字,286KB)のプロファイルを取得します。なお、以降のプロファイルにおける各メトリクスとその説明は次のとおりです。

メトリクス名 説明
Time (ms) この関数と、この関数から呼び出されるすべての関数に費やした時間。
Own Time (ms) この関数に費やされた時間。この関数から呼び出された関数に費やされた時間を割り引いたもの。
Memory (B) この関数およびこの関数から呼び出されるすべての関数によって消費されるメモリ量 (バイト単位)。
Own Memory (B) この関数によって消費されるメモリ量 (バイト単位)。この関数から呼び出される関数によって消費されるメモリ量を差し引きます。
Calls 関数が呼び出された回数。

(抜粋したプロファイル：未改善)

Time (ms) Own Time (ms) Memory (B) Own Memory (B) Calls
fold_text 23,614 436 841,936 0 1
mb_substr 8,913 8,913 841,952 841,952 20,027
mb_strpos 14,542 14,542 0 0 20,025

fold_text関数のTimeが23,614ミリ秒、内14,542ミリ秒がmb_strpos関数です。mb_strpos関数はループが回る度にoffsetが大きくなりながら2万回超呼び出されてます。また、ループ内で呼び出されるmb_substr関数のOwnTimeが8,913ミリ秒です。mb_strpos関数のOwn Time(14,542 ms)とmb_substr関数のOwn Time(8,913 ms)を足し合わせるとfold_text関数のTime(23,614 ms)とほぼ一致しています。

以上より、ループの度に呼び出されるmb_strpos関数とmb_substr関数に多くの時間を要していることがわかりました。そこで、文字列の分割を事前に済ませてからループする方針に変更します。

<?php
function fold_text($main_message) {
    $processed_text = '';
    //事前に改行文字で分割
    $lines = preg_split("/\n/u", $main_message);
    foreach ($lines as $line) {
        $foldedLine = fold_line_to_fit_width($line);
        $processed_text .= $foldedLine . "\n";
    }
    return $processed_text;
}

変更後、同テストデータを処理した際のプロファイルは次のようになりました。

(抜粋したプロファイル：事前分割)

Time (ms) Own Time (ms) Memory (B) Own Memory (B) Calls
fold_text 263 158 1,210,280 0 1
mb_substr 0 0 144 144 2
mb_strpos 0 0 0 0 35
preg_split 7 7 1,213,256 1,213,256 13

fold_text関数のTimeが23,614ミリ秒から263ミリ秒まで劇的に改善しました。

改善その2：fold_line_to_fit_width 関数の再帰呼び出し

fold_line_to_fit_width関数の再帰呼び出しにも問題がありそうです。実際、「100 から 200 を超えるようなレベルの再帰呼び出しは避けてください」とPHP公式ドキュメントにも記載されています。fold_line_to_fit_width関数は、引数として受け取った文字列1行の先頭から$max_width byte相当の文字列を切り出す処理を再帰的に行っています。そのため1行が極めて長いケースで再帰が深くなり、何らかの問題が発生しそうです。試しに、テストデータ2(1行,約26万文字,786KB)を処理してみます。

実行結果は次にようになりました。メモリ不足でのFatal errorです。

Fatal error: Allowed memory size of 1153433600 bytes exhausted (tried to allocate 352256 bytes) in index.php on line 60

また、問題が発生したindex.phpの60行目はfold_line_to_fit_width関数内の次の行です。これは分割された1行から、$max_width byte以降の文字列を切り出す処理です。

<?php
$remaining_part = mb_substr($line, $max_width);

fold_line_to_fit_width関数は呼び出される度に、前半$max_width byte相当の$first_part と$max_widthbyte以降の後半文字列$remaining_partに分割が行います。今回のように一行が極めて長いケースでは、変数$first_part と$max_widthが解放されぬまま、再帰的にfold_line_to_fit_width関数が呼び出されることで、メモリ不足となったようです。

ここで少し寄り道です。 26万文字のテストデータ2、786KBの文字列をfold_line_to_fit_width関数に渡した時、再帰の終了条件、mb_strlen($line) <= $max_widthを満たすまでにどれだけのメモリが必要となるか、ざっくりと計算してみます。 n回目の呼び出しにおける$first_partと$remaining_partで保存される文字列メモリの和を Y_n (byte)とすると、法則がありそうです。(1 KB = 1000 byteとして計算)

Y_1=786 \times 1000

Y_2=786 \times1000-$max_width

Y_3=786 \times 1000-2 $max_width


これは次のような等差数列です。
初項 786 \times 1000
公差 -$max_width
一般項 (byte) 786 \times 1000-(n-1)$max_width

$max_width=80として、再帰の終了条件を満たすまでに確保される文字列のメモリ総和は「初項 786 \times 1000、公差 -80の等差数列の和が最大になる時」です。

項が0以上となる範囲は Y_n \geq 0 、 786 \times 1000-(n-1)80 \geq 0 、\frac{786 \times 1000 + 80}{80} \quad \geq n、 9826 \geq n

これを満たす最大の整数nは9826

初項( Y_1=786 \times 1,000)から第9826項( Y_{9826}=0)までの和は、等差数列の和の公式、 \frac{n}{2}(Y_1+Y_n) より、 \frac{9826}{2} \quad (786 \times 1000+0) =3,861,618,000 (byte) です。

たかだか786 KBの文字列処理のために3.861GBのメモリが必要になっていました。

そこで再帰を削除し、受け取った文字列の先頭から$max_width文字づつ切り出すループとなるように修正します。

<?php
function fold_line_to_fit_width($remaining_part) {
    $max_width = 80; // 1行の最大byte数,簡単のため実際の上限とは異なる
    $substr_folded = "";
    while (strlen($remaining_part) > 0) {
        $first_part = mb_substr($remaining_part, 0, $max_width);
        $remaining_part = mb_substr($remaining_part, $max_width);
        if (preg_match('/^[）]/u', $remaining_part)) {
            // 行頭禁則処理
        }
        if (preg_match('/[(]$/u', $first_part)) {
            // 行末禁則処理
        }
        $substr_folded .= $first_part."\n";
    }
    if(strlen($remaining_part) !== 0) {
        $substr_folded .= $remaining_part;
    }
    return $substr_folded;
}

変更後、同テスト(1行,26万文字,786KB)を処理すると、メモリ不足によるFatal Errorが解消され、次のようなプロファイルが得られました。

(抜粋したプロファイル：事前分割+再帰削除)

Time (ms) Own Time (ms) Memory (B) Own Memory (B) Calls
fold_text 13,114 38 803,032 0 1
fold_line_to_fit_width 13,065 99 1,295,904,736 0 1
mb_substr 7,565 7,565 1,295,904,736 1,295,904,736 6,554
preg_match 5,411 5,411 112 112 6,623

メモリの観点からは、mb_substr関数のOwnMemoryが1,295,904,736 byte、1ギガバイト超となっています。ただし、一回のwhileループで保持する文字列、$first_part+$remaining_partは、初回ループが最大となり、従来の再帰のようにメモリ不足で実行できなくなる事態にはならないはずです。

改善その3：mb_substr関数の一部削除

実行時間の観点で、fold_text関数のTimeが13,114ミリ秒のうち、7,565ミリ秒がmb_substr関数の実行時間です。ここで、mb_substr関数 を利用している次の行について改善できないか考えます。

<?php
$remaining_part = mb_substr($remaining_part, $max_width);

これは、「$max_widthバイト以降の文字列を切り出す処理」です。果たして、マルチバイトに対応したmb_substr関数を利用する必要はあるのでしょうか？

切り出し開始位置のbyte数、つまり、strlen($first_part) byte 以降を末尾まで切り出すのであれば、より高速なマルチバイト非対応の関数で代替できそうです。次のように変更してみます。

<?php
$remaining_part = substr($remaining_part,strlen($first_part));

変更後、同テスト(1行,26万文字,786KB)を処理したプロファイルは次のようなものです。

(抜粋したプロファイル：事前分割+再帰削除+substr)

Time (ms) Own Time (ms) Memory (B) Own Memory (B) Calls
fold_text 9,295 43 803,032 0 1
fold_line_to_fit_width 9,239 105 1,295,904,704 0 1
mb_substr 3 3 1,048,544 1,048,544 3,227
substr 3,755 3,755 1,294,882,104 1,294,882,104 3,855
preg_match 5,386 53,86 112 112 6,623

fold_text関数のTimeが13,114ミリ秒から9,295ミリ秒まで改善しました。また、マルチバイト文字列が文字化けすることなく分割されていることを、別途実施したテストにより確認しました。

改善その4：preg_match関数の範囲変更

これが体験期間に行った最後の改善です。行頭禁則処理、行末禁則処理が必要かどうか判定する、次のifに着目しました。

<?php
        if (preg_match('/^[)]/u', $remaining_part)) {
            // 行頭禁則処理
        }
        if (preg_match('/[(]$/u', $first_part)) {
            // 行末禁則処理
        }

行頭禁則処理は、文字列の先頭に特定の文字、今回の例では)が来ることを禁止します。行頭禁則処理が必要か判定する際、preg_match関数に$remaining_part全文を渡す必要はあるのでしょうか？判定には先頭1文字を用いれば十分なはずです。$first_partは最大$max_width文字ですが、$remaining_part には上記で利用しているテストケース(1行,26万文字,786KB)の初回ループで、ほぼ全文の26万文字が格納され、正規表現の処理が遅くなっていると考えられます。

そこで、行頭禁則処理が必要かどうか判定する際は「$first_partの先頭1文字のみ」、行末禁則処理が必要かどうか判定する際には「$remaining_partの末尾1文字のみ」をpreg_match関数に与えるように変更します。

<?php
        if (preg_match('/^[)]/u', mb_substr($remaining_part,0,1))) {
            // 行頭禁則処理
        }
        if (preg_match('/[(]$/u', mb_substr($first_part,-1,1))) {
            // 行末禁則処理
        }

変更後、同テスト(1行,26万文字,786KB)を処理したプロファイルは次のようなものです。

(抜粋したプロファイル：事前分割+再帰削除+substr+preg_match対象の変更)

Time (ms) Own Time (ms) Memory (B) Own Memory (B) Calls
fold_text 3,618 51 803,032 0 1
fold_line_to_fit_width 3,548 110 1,296,114,432 0 1
mb_substr 3 3 1,258,272 1,258,272 9,831
substr 3,433 3,433 1,294,882,104 1,294,882,104 3,855
preg_match 11 11 112 112 6,623

fold_text関数の処理時間が9,295ミリ秒から、3,618ミリ秒へとさらに改善しました。

全ての改善を終えた模擬コード

変更点は次の4つです

  • fold_text関数
    • whileループでのmb_strpos関数による分割を、preg_split関数による事前分割に変更
  • fold_line_to_fit_width関数
    • メモリ消費が激しい再帰呼び出しを削除。whileループへ変更。
    • コードの目的を踏まえ、mb_substr関数からsubstr関数へ一部変更
    • コードの目的を踏まえ、preg_match関数に渡す文字列を削減
<?php
function fold_text($main_message) {
    $processed_text = '';
    $lines = preg_split("/\n/u", $main_message);//about 10 times faster than mb_split
    foreach ($lines as $line) {
        $foldedLine = fold_line_to_fit_width($line);
        $processed_text .= $foldedLine . "\n";
    }
    return $processed_text;
}
function fold_line_to_fit_width($remaining_part) {
    $max_width = 80; // 1行の最大byte数,簡単のため実際の上限とは異なる
    $substr_folded = "";
    while (strlen($remaining_part) > 0) {
        $first_part = mb_substr($remaining_part, 0, $max_width);
        $remaining_part = substr($remaining_part,strlen($first_part)); //52s
        if (preg_match('/^[)]/u', mb_substr($remaining_part,0,1))) {
            // 行頭禁則処理
        }
        if (preg_match('/[(]$/u', mb_substr($first_part,-1,1))) {
            // 行末禁則処理
        }
        $substr_folded .= $first_part."\n";
    }
    if(strlen($remaining_part) !== 0) {
        $substr_folded .= $remaining_part;
    }
    return $substr_folded;
}

結局、Garoonちゃんに愛を送れたんですか？？？

改修後のコードだと手元の開発環境(M3 Mac)では、Garoonちゃんに100万回の愛を送ることができました！！！

ただし、実際の処理時間は様々な要因(例えば、サーバーの性能や他ユーザーからの負荷の高いリクエスト、など)にも左右されます。また、Garoonでは管理者がメールサイズの制限を設定することができる(メールサイズの制限の設定 | クラウド版 Garoon ヘルプ )ため、13MBのメールはメールサイズ制限に触れることも考えられます。　愛を伝える道のりは遠いですね（？）

チーム体験のよかった点、反省点

性能改善チームでのチーム体験で最も良かった点は「パフォーマンスへの意識が高まったこと」です。

これまでに私が制作に関わったことがあるアプリケーションは、主に自分や友人、家族など、限られた少人数が利用するアプリばかりで、パフォーマンスについて意識することはあまりありませんでした。

一方、Garoonは中堅から大規模企業向けのグループウェアであり、求められる機能要件が少人数向けのアプリケーションとは全く異なっています。チーム体験中にメンバーの方に教わったSQLのチューニング資料も学びが多い資料で、今後に役立つ知識と意識が育ったと感じています。(本夏フェスのGaroonレーンにて、性能改善チーム所属の方がブログ執筆されています。良ければ併せてご覧ください。)

一方、反省点は、「一人で作業しがちになったこと」です。一部の作業はモブで助けていただきましたが、「改善方針を一人で考えて実装、共有」といったフローで作業を行っていました。実装前にメンターの方に方針を共有してアドバイスやコメントをいただければ、より良い改善方針を立てられたのではないかと思いますし、方針が誤っていた際の手戻りも少なかったと思います。幸い、Cybozuには分報と呼ばれる社内SNSのような仕組みが存在し、もっと有効に活用できただろうと思います。

参考)まるで社内SNS！「分報」でメンバーの状況をハイブリッドワークでも感じられるようにしよう｜THE HYBRID WORK サイボウズのハイブリッドワーク専門メディア

本ブログ執筆時点は、配属先のチームは未定ですが、配属先チームではチーム体験の学びと反省を活かして活動していきたいと思います。

余談その1：プロファイルのCallsに違和感を持たれた方

例えば、上述の　(抜粋したプロファイル：事前分割+再帰削除+substr)　のCalls列に着目し「mb_substr関数とsubstr関数の呼び出し回数が異なるのはなぜだ？同じ呼び出し回数にならないのか?」と疑問に思われた方、非常に鋭いです。(私はブログ執筆中に気がつきました。)

実は今回のケースではphp.iniにauto_prepend_file(メインファイルの読み込み前に自動で呼び出されるファイルを指定するパラメータ,PHP: Hypertext Preprocessor )が設定されていますauto_prepend_fileに指定したphpファイルも取得したプロファイルに反映されているため、呼び出し回数が一部ズレているように見えています。

余談その2：ここを変えればもっと改善できませんか？

自分なりに改善できる箇所を直したつもりですが、より良い改善方針や、改善可能な箇所がまだまだあるかもしれません。

例えば、改善その3で、一部のmb_substr関数をsubstr関数へ置き換えることで高速化を行いました。一方、改善その4では、次のようにmb_substr関数を利用する形でコードを修正しました。ここで「mb_substr関数は遅いんじゃないのか？」、と思われる方がいらっしゃるかもしれません。

<?php
        if (preg_match('/^[)]/u', mb_substr($remaining_part,0,1))) { //[1]
            // 行頭禁則処理
        }
        if (preg_match('/[(]$/u', mb_substr($first_part,-1,1))) { //[2]
            // 行末禁則処理
        }

まず、実行環境のPHP8.2.18において、mb_substr関数内部では引数として指定したoffsetまで、先頭から順に進むようです。そのため、長文の末尾から切り出す処理は、先頭から切り出す処理に比べて遅くなります。例えば、テストデータ2(1行,約26万文字,786KB)の先頭、中間、末尾からmb_substr関数で1文字切り出す際の実行時間は、手元の環境で次のようになりました。

(mb_substr関数を用いて、26万文字テキストの任意位置から1文字切り出す際の実行時間)

処理時間(マイクロ秒)
先頭から(1文字目を切り出す) 0.0003740788
中間から(393216 byte目から1文字切り出す) 0.0007119179
末尾から(最後の1文字を切り出す) 0.0012049675

つまり、切り出し対象が長文、かつ、切り出し位置が文末付近のケースをsubstr関数に置き換えることができれば、高速化の効果が期待できます。改善その4で追加した[1]は、長文になりえますが、切り出し位置が文頭です。[2]は切り出し位置が文末付近ですが、切り出し対象は最大$first_part byte、今回のケースでは80 byteです。この処理時間は上述の表から0.00037-0.00071 マイクロ秒程度と考えられますので、再帰呼び出しによって3000回呼び出されたとしても無視できるレベルと考えられます。そのため、substr関数を利用していません。

その他、より良い案があればこそっと教えてください。勉強します。

#CybozuSummerBlogFes2024

Lemnis

関連記事
このエントリーをはてなブックマークに追加