Vimのパッチ存在確認処理を速くした

Vim

昨日Apple Eventを待機しながらVimのコードを眺めていたら、なんだか香ばしい匂いのするコードを見つけてしまいました。

/*
 * Return TRUE if patch "n" has been included.
 */
    int
has_patch(int n)
{
    int        i;

    for (i = 0; included_patches[i] != 0; ++i)
        if (included_patches[i] == n)
            return TRUE;
    return FALSE;
}

ペロッ… こ、これは、線形探索！

Vimは、メインのブランチのすべてのコミットでパッチバージョンが上がっていく方式をとっています。 プラグインが新しい機能を使いたい時に、ユーザーが使っているVimに特定のパッチが入っているかをチェックする必要があります (関数やイベントなど機能が入っているかを直接チェックすることができる場合もありますが、機能が入ってもバグっていることがありますし、直接チェックできない機能もあります。その時はパッチバージョンでチェックする必要があります)。 こういうプラグイン実装者のために、 has('patch-8.2.1200') のように関数 has() でパッチバージョンが含まれているかをチェックすることができます (詳しくは :h has-patch)。

含まれているパッチバージョンは included_patches という配列にすべて羅列されており、これを線形に探索しているコードです。 しかし included_patches は必ず大きい番号順にソートされており、二分探索したほうがほとんどのケースでお得なはずです。 ということで昨日シュッとコードを書いて、出してみました。

github.com 素朴な二分探索です。

/*
 * Return TRUE if patch "n" has been included.
 */
    int
has_patch(int n)
{
    int        h, m, l;

    // Perform a binary search.
    l = 0;
    h = (int)(sizeof(included_patches) / sizeof(included_patches[0])) - 1;
    while (l < h)
    {
        m = (l + h) / 2;
        if (included_patches[m] == n)
            return TRUE;
        if (included_patches[m] < n)
            h = m;
        else
            l = m + 1;
    }
    return FALSE;
}

朝起きたら、無事 v8.2.1973 として取り込まれていました。修正なしで入っていると嬉しいですね。 github.com

ここの処理は大昔から変わっておらず (少なくとも2004年からずっと同じコードでした。もっと遡れるかもしれません) で、今まで見過ごされていたのが不思議なくらいです。 Vimがまた少し速くなってよかったですね。