外部コマンド排除で256倍？外部コマンドを救いたい —— コマンドをパイプで繋いで2万5千倍にしよう #ShellScript

外部コマンドの排除で256倍に高速化するという話

『シェルスクリプトリファクタリング～遅いシェルスクリプトが供養されてたので蘇生して256倍に高速化させました～』という記事において、遅いシェルスクリプトを高速化する手法が解説されています。ループの中で外部コマンドを使用したせいで遅くなってしまったので、外部コマンドを一切使わないように書き換える、というものです。

私の手元で試しても、ループ中で crudini や jq を使用したバージョンより高速です。

上のグラフで速度の比が256倍に満たないのは、テストデータのサイズが極小（ファイル数: 1、データサイズ: 10kB 以下）だからです。扱うデータが小さいと、プロセスの起動に掛かる時間が全体に占める割合が大きくなりますから、手法による違いが出にくくなります。データを増やして試すと、速度の比が大きくなります。

データが十分あれば400倍以上に高速化していますね。（差が大き過ぎて棒グラフに適していませんが、高さ2の赤い棒があるのです。後ほど対数目盛のグラフも作ります）

コマンドを活用しつつ高速なコードを書きたい

さて、『256倍に高速化』の記事でリファクタリング対象となったシェルスクリプトの問題は、外部コマンドをループ中で繰り返し起動している事です。であれば、外部コマンドの使用を止めてしまおう、というのは一つの論理的帰結でしょう。

しかし、コマンドは便利ですから使いたいです。そこで、外部コマンドを排除するのでは無く、十分に活用した上で速いスクリプトを書く方法が有ります。外部コマンドをパイプで繋ぎ、フィルターとして使う方法です。この考え方は以前、『シェルスクリプトを何万倍も遅くしないためには —— ループせずフィルタしよう』としてまとめました。以下では、この手法が今回のケースでも有効なことを確認します。
　
（そもそも何をするスクリプトが題材になっているのかは、『やっている事』の項にまとめてあります。しかし、この記事においては重要ではありません）

LTSV 経由で JSON にしてみる

ではコードです。まずは行指向のデータにまとめ、そこから一度 LTSV に変換し、後は LTSV を扱うツール（ltsv2json）に任せました。JSON 構造の変換には jq を使っています。この記事はコードの解説を目的としないので、詳細を読んでいただく必要はありません。

フィルター活用（ltsv2json+jq）

#!/bin/sh
# SPDX-License-Identifier: CC0-1.0

set -u
export LC_ALL=C
tab="$(printf '\t')"

cd /usr/share/applications || exit 1

find -L . -name '*.desktop' -exec \
    grep -E \
        -e '^\[' \
        -e '^(Name|Exec|Icon|Type|Comment) *=' \
        -- /dev/null {} + \
    | sed ' 
        # ヘッダー行を処理

        /^[^:]*:\[/  {
            # grep が付けたファイル名を出力用に変換
            s#^\./##
            s#\.desktop##
            y#.-#__#

            # 先頭のファイル名は cut で削除するので後ろにコピー
            s#^\([^:]*\):.*\]#&\1#
        } '\
    | cut  -d: -f2-             \
    | sed  "/^\[/  s#^#$tab#"   \
    | tr   '\n\t'  '\t\n'       \
    | grep '^\[Desktop Entry\]' \
    | sed  '
        # LTSV化
        # 末尾コメント参照

        s#^\[Desktop Entry\]#id:#
        s#\('"$tab"'[^= ]*\) *= *#\1:#g
        s#'"$tab"'$##
        '\
    | ltsv2json \
    | jq 'INDEX(.id) | del(.[].id)'


### LTSV化概要 ###
#
# 入力行フォーマット:
#   [Desktop Entry]file_name  <tab>  Name=Value  <tab>  Name2=Value2  <tab>
#
#   * 末尾にタブがある
#   * 「=」の前後に任意個のスペースが存在可 (例: `Name =   Value`)
#
# 出力行フォーマット:
#   id:file_name  <tab>  Name:Value  <tab>  Name2:Value2
#
# エスケープ:
#   * Desktop Entry のエスケープ表記を考慮するのは出力を利用する側とする
#     https://specifications.freedesktop.org/desktop-entry-spec/latest/ar01s04.html
#   * よって、エスケープ処理は必要無い

ここで重要なのは、一連のコマンドがパイプで繋がれ、一つのコマンド列を形成していることです。こういったコードの特徴は「形」としてはっきりと表れます。もちろん、コードの整形のスタイルは様々ですが、概ねこのように、コマンドがずらっと揃って並び、上から下にまっすぐ処理が進むことになります。

速度は下の通りです。

処理対象のデータのサイズがある程度以上ならば、ループで書かれたオリジナルの数千倍程度高速です。データが極小のケースでは、十数倍程度となります。

標準コマンドのみで JSON にしてみる

上では、ltsv2json や jq といったコマンドを使いましたが、こういったツールを用意できないこともあるでしょう。ですので、標準的なコマンドのみで、直接 JSON を生成してみます。

といっても、sed で頑張って置換するだけです。LTSV化が3つの正規表現で済んだのに対し、JSON化には十個以上が必要となりました。こういったコードを毎回書くのは大変なので、JSON などをよく使うのであれば、汎用的なツールを用意しておくべきです。

フィルター活用（標準的なコマンドのみ使用）

#!/bin/sh
# SPDX-License-Identifier: CC0-1.0

set -u
export LC_ALL=C
tab="$(printf '\t')"

cd /usr/share/applications || exit 1

find -L . -name '*.desktop' -exec \
    grep -E \
        -e '^\[' \
        -e '^(Name|Exec|Icon|Type|Comment) *=' \
        -- /dev/null {} + \
    | sed ' 
        # ヘッダー行を処理

        /^[^:]*:\[/  {
            # grep が付けたファイル名を出力用に変換
            s#^\./##
            s#\.desktop##
            y#.-#__#

            # 先頭のファイル名は cut で削除するので後ろにコピー
            s#^\([^:]*\):.*\]#&\1#
        } '\
    | cut  -d: -f2-             \
    | sed  "/^\[/  s#^#$tab#"   \
    | tr   '\n\t'  '\t\n'       \
    | grep '^\[Desktop Entry\]' \
    | sed  '
        # JSON化
        # 末尾コメント参照
        # （都度都度こういった処理を書く事は、お勧めしません。
        #   汎用的なコマンドを用意しておきましょう。）

        s#^\[Desktop Entry\]##

        s#\\#\\\\#g
        s#"#\\"#g

        s#[^'"$tab"']\{1,\}#"&"#g
        s#\('"$tab"'[^= ]*\) *= *#\1": "#g

        s#'"$tab"'#: { #
        s#'"$tab"'#, #g
        s#, $##
        s#$#}#

        1    s#^#{#
        $   !s#$#,#
        $    s#$#}#
        '

### JSON化概要 ###
#
# 入力行フォーマット:
#   [Desktop Entry]file_name  <tab>  Name=Value  <tab>  Name2=Value2  <tab>
#
#   * 末尾にタブがある
#   * 「=」の前後に任意個のスペースが存在可 (例: `Name =   Value`)
#
# 出力行フォーマット:
#   "file_name": { "Name": "Value", "Name2": "Value2" },
#
#   * 1行目なら先頭に「{」
#   * 最終行なら、末尾の「,」の代わりに「}」
#
# エスケープ:
#   * Desktop Entry のエスケープ表記を考慮するのは出力を利用する側とする
#     https://specifications.freedesktop.org/desktop-entry-spec/latest/ar01s04.html
#   * よって、JSON 用に「\」と「"」だけ無条件にエスケープする

速度はどうでしょうか。

jq を省いたおかげで、さらに速くなりました。データの大きさが十分であれば、ループで書かれたオリジナルの2万5千倍以上の速度ですから、この記事のタイトルを回収できたのではないでしょうか。

左の方がよく見えないので、対数目盛バージョンも用意しました。

データが極小であれば外部コマンド排除が一番速い、という事がばれてしまいましたね。まあ、これは処理時間にして数ミリ秒のことですので、私は気にしません。フィルターの威力をある程度は示せたと思うので満足です。

以上

補足

やっている事

『256倍に高速化』の記事で扱われている課題は、「Linux にインストールされてるアプリの一覧を JSON で出力する」というものです。Unix 系のデスクトップ環境ではアプリケーションがインストールされる際、特定のディレクトリに「Desktop Entry」という仕様に準じたファイルを配置しますので、これを処理するという課題です。

私のコードでは、完全に動作を合わせてはいません（例えば JSON の整形方法は異なります）。しかし、概ね同じ意味の処理になっているはずです。

入力

ディレクトリ /usr/share/applications の下にある全ての *.desktop ファイルを入力とします（注: 実用の際は $XDG_DATA_DIRS を参照した方がよいかも知れません）。元記事ではサブディレクトリが除かれていましたが、これは意図が読めなかったので、とりあえずこの記事ではサブディレクトリも対象としています。

入力は、この様なファイル（たち）です。

入力ファイル例（firefox.desktop　より抜粋）

[Desktop Entry]
Version=1.0
Name=Firefox Web Browser
Comment=Browse the World Wide Web
GenericName=Web Browser
Keywords=Internet;WWW;Browser;Web;Explorer
Exec=firefox %u
Type=Application
Icon=firefox

# 以下のように、[Desktop Entry] 以外のグループもあります
# これらは無視しなければなりません
[Desktop Action NewWindow]
Name=Open a New Window
Exec=firefox -new-window

[Desktop Action NewPrivateWindow]
Name=Open a New Private Window
Exec=firefox -private-window

出力

全ての入力ファイルの [Desktop Entry] グループに含まれる Name, Exec, Icon, Type 及び Comment というエントリーを抽出し、下のような構造の 1つの JSON にまとめます。目的のエントリー（Name など）が存在しない際は、値を空文字とするか、JSON に含めないものとします。

出力するJSONの構造

{
   "firefox" : {
      "Comment" : "Browse the World Wide Web",
      "Exec" : "firefox %u",
      "Icon" : "firefox",
      "Name" : "Firefox Web Browser",
      "Type" : "Application"
   },
   "gvim_huge" : {
      "Comment" : "Edit text files",
      "Exec" : "gvim-huge -f %F",
      "Icon" : "gvim",
      "Name" : "GVim",
      "Type" : "Application"
   }
}

トップレベルのキー名は、ファイル名（フルパスから /usr/share/applications/ を除いたもの）から下記の変換で求めます。

拡張子(.desktop)を削除: firefox.desktop → firefox
「-」と「.」を「_」に置換: gvim-huge → gvim_huge （注: これは意図が読めなかった処理ですが、この記事でも同じ処理をしました。ただ、これにより JSON のキー名が一意である保証が無くなるかも知れません）

テストデータのサイズ

この記事のグラフでは、3つのサイズのテストデータを使っています。

ファイル数: 1 (9.9Kb)
ファイル数: 225 (1.7Mb)
ファイル数: 4500 (34Mb)

1番目は極小のデータとして、
2番目は私が実際に使っている Linux機の /usr/share/applications/ を元に実際的な利用ケースとして、
3番目はプロセスの起動コスト部分の影響が小さくなる、ある程度大きいデータとして、
それぞれ用意しました。

この文章のライセンス

この記事はクリエイティブ・コモンズ表示 - 継承 4.0 国際 (CC BY-SA 4.0)の元で公開します。文中のコード片の著作権は放棄（CC0 1.0）します。

外部コマンド排除で256倍？ 外部コマンドを救いたい —— コマンドをパイプで繋いで2万5千倍にしよう