HN 日本語サマリー

← 一覧へ戻る
プログラミング

より高速なバイナリサーチ:コンパイル済みコードからメカニカルシンパシーへ

Faster binary search: from compiled code to mechanical sympathy (pythonspeed.com)

55 pointsby enz11 コメント

要約

この記事では、Pythonコードの計算速度を向上させるための高度な手法について解説しています。特に、scikit-learnの勾配ヒストグラムブースティングアルゴリズムにおける、浮動小数点数をバケットに割り当てるためのバイナリサーチの実装を、CPUの動作原理(メカニカルシンパシー)を考慮することで6倍高速化する過程を紹介しています。分岐予測の失敗を避けるためのブランチレス実行や、CPUの並列処理能力を最大限に引き出す最適化手法が説明されています。

全文翻訳

8倍高速なバイナリ検索:コンパイル済みコードからメカニカルシンパシーへ

計算量の多いPythonコードを高速化するにはどうすればよいでしょうか? 一般的で有用な出発点は以下の通りです。

  1. 適切なアルゴリズムを選択する。
  2. コンパイル言語でPython拡張を作成する。
  3. 並列処理を追加して複数のCPUコアを利用する。

しかし、さらに速度が必要な場合はどうでしょうか? scikit-learnの勾配ヒストグラムブースティングアルゴリズムのステップの一つである、以下の実用的な問題を考えてみましょう。

  • 浮動小数点数の大きな配列がある。
  • それらを0〜254の整数範囲に、均等に分散させて割り当てたい。

scikit-learnでは、浮動小数点値の全範囲を255個のバケットに分割し、バケット境界のソート済み配列を作成し、バイナリ検索を使用して各値に適切なバケットを選択することでこれを実装しています。バイナリ検索はコンパイル言語で実装されており、複数のコアで並列実行できます。

最近、Quansightでの仕事の一環として、Paul Khuongによる2つの投稿に触発され、この実装を大幅に高速化しました。どうやって? コードがCPUと競合しないようにしたのです。

この記事では、簡略化された例でこの高速化の過程を説明します。その後、一連の追加最適化を示し、最終バージョンは元の実装よりも6倍高速に動作します。

多くの異なる低レベルハードウェアトピック(命令レベル並列性、ブランチ(予測)ミス、その他)に触れることになります。これは記事一つでは、可能性のあることを briefly に紹介するにすぎず、詳細なチュートリアルにはなり得ません。そのため、記事の最後にこれらのトピックについてさらに学ぶ方法について説明します。

更新:

  • f64比較に関する愚かな間違いを修正しました。単純に比較できます。SIMDはもう役に立ちませんが、それでもコードはさらに高速です。
  • halvesの事前計算の利点を明確にしました。

出発点:標準的なバイナリ検索

元のscikit-learnコードはCythonで実装されていましたが、この記事ではRustを使用します。ここでは、バケットの配列を与えられた場合にバケットを見つけるというこのユースケースのために設計された、バイナリ検索の非常に標準的な実装(NumPyのものをベースにしています)を示します。

/// バケット境界の配列を与えられた場合に、浮動小数点値をどのバケットに適合するかを見つけることで、整数値に変換します。
fn bucketize_classic_impl(
    arr: &[f64],
    boundaries: &[f64],
) -> Vec<usize> {
    // Vec(またはvector)はRustにおけるPythonのlistに相当します。ここでは`arr.len()`の値を格納するのに十分なメモリを確保した空のVecを作成します:
    let mut result = Vec::with_capacity(arr.len());
    for value in arr {
        // 標準的なバイナリ検索アルゴリズム:
        let mut min_idx = 0;
        let mut max_idx = boundaries.len();
        while min_idx < max_idx {
            let middle = min_idx + ((max_idx - min_idx) / 2);
            if boundaries[middle] < *value {
                min_idx = middle + 1;
            } else {
                max_idx = middle;
            }
        }
        // これはPythonのa_list.append()と同等です:
        result.push(min_idx);
    }
    // 結果を返します:
    result
}

完全を期すために、これをPythonにフックする方法を示します。これにより、NumPy配列を受け取り、返すことができます。これはボイラープレートなので、後の関数では表示しません。RustとPyO3に慣れていない場合や、特に気にしない場合はスキップしても構いません。記事の残りの部分とは関係ありません。

コードを見るにはここをクリックしてください

use pyo3::prelude::*;
use numpy::ndarray::Array;
use numpy::{PyArray1, PyReadonlyArray1};

#[pyfunction]
fn bucketize_classic<'py>(
    py: Python<'py>,
    // これらの2つの引数は浮動小数点数の1次元配列です:
    arr: PyReadonlyArray1<f64>,
    boundaries: PyReadonlyArray1<f64>,
) -> PyResult<Bound<'py, PyArray1<usize>>> {
    let result = bucketize_classic_impl(
        arr.as_slice().unwrap(),
        boundaries.as_slice().unwrap(),
    );
    // RustのvectorをPythonに返すことができる1次元NumPy配列に変換します:
    let result =
        PyArray1::from_owned_array(py, Array::from_vec(result));
    Ok(result)
}

ブランチの予測ミスがコードを遅くする

このバイナリ検索の実装をどうすれば高速化できるでしょうか? すでにスケーラブルなアルゴリズムとコンパイル言語を使用しています。並列処理はもちろん選択肢ですが、ここでは異なるアプローチを使用します:メカニカルシンパシー、つまりCPUがどのように動作するかをより深く理解することです。まず、最新のCPUが単一コア内でどのようにコードを並列実行するかを簡単にレビューします。

Pythonコードの合理的なメンタルモデルは、コードが一度に1つの命令ずつ実行されるというものです。算術演算を2倍行うと、コードは2倍遅くなります。コンパイル言語に切り替えると、操作が1つまたは2つのCPU命令にマッピングされる場合があるため、そのメンタルモデルはもはや正しくありません。最新のCPUは、単一のCPUコアで複数の独立したCPU命令を同時に実行できる場合があり(「命令レベル並列性」)、実行速度が向上します。

fn two_adds(a: i64, b: i64, c: i64, d: i64) -> i64 {
    // あなたのCPUはおそらくこれらの2つの加算を、単一コアで自動的に並列実行できるでしょう:
    let t1 = a + b;
    let t2 = c + d;
    // 結果を返します:
    t1 + t2
}

しかし、if/while/for式によって作成されるコード内のブランチは問題を引き起こします。コードは一方のパスに進むか、もう一方のパスに進む可能性があります。2つの選択肢がある場合、CPUはどの将来の命令セットを並列実行しようと試みるべきでしょうか?

fn maybe_add(a: i64, b: i64, c: i64, d: i64, add: bool) -> i64 {
    let t1 = a + b;
    // CPUは`a + b`と並列して、これらの2つのブランチのどちらを実行すべきでしょうか?
    let t2 = if add {
        c + d
    } else {
        c * d
    };
    t1 + t2
}

高速な実行を保証するために、CPUにはどのブランチを並列実行するかをヒューリスティックに選択するブランチ予測器があります。推測が正しければ、コードは高速になります。推測が間違っている場合、CPUは最終的にそれに気づき、間違った作業を元に戻してから、正しいブランチを実行します…これはコードが遅くなることを意味します。場合によっては、大幅に遅くなります。

上記のバイナリ検索アルゴリズムは、残念ながら入力データによっては非常に予測が困難です。バケット境界は、入力値がすべてのバケットに均等に分散するように選択されることを思い出してください。これは、バイナリ検索で左右どちらに進むかの選択が全く予測不可能であることを意味します。

// CPUはどちらのパスが取られるかを確実に推測できません:
if boundaries[middle] < *value {
    min_idx = middle + 1;
} else {
    max_idx = middle;
}

同様に、反復回数も変動する可能性があります。

// このループは停止するまでに何回続きますか?
// 使用されている特定のデータによっては知ることは不可能です。
while min_idx < max_idx {
    // ...
}

この仮説を検証するために、CPUのハードウェアカウンター(py-perf-eventを介してPythonからアクセス可能)を使用して、実行中のコードが実行するブランチの数と、これらのブランチのうちいくつが予測ミスしたかを測定できます。使用する入力は次のとおりです。

import numpy as np
from numba import jit

# 0から1の間の値:
DATA = np.random.random(1_000_000)

# バケット境界、均等に配置:
BOUNDARIES = np.linspace(0.0, 1.0, 255)[1:-1]

そして、コードを実行した結果は次のとおりです。

コード➘ 経過マイクロ秒➘ ブランチ命令数➘ ブランチ予測ミス率 %
bucketize_classic(DATA, BOUNDARIES)44,572.726,996,90416.6%

➘ 数値が小さいほど良い

16%のブランチ予測ミスは良くなく、1つの値あたりのブランチ数もかなり多いです。DATAは1,000,000個の値があり、合計2700万回のブランチがあるため、値あたり27回のブランチになります。

ブランチレス実行への切り替え

予測不可能なブランチの両方の原因を取り除きます。whileループの反復回数については、代わりに固定回数、つまりバケット数のlog2だけ反復します。値によっては、以前はバケットが1〜2回の反復で見つかっていた場合、少し多くの作業が発生するかもしれませんが、ブランチ予測ミスを回避することによる速度の向上により、それだけの価値があります。

if式については、現在のコードは時々一方の変数を設定し、時々もう一方を設定していました。これを、変更されない場合でも常に同じ変数を設定するコードに置き換えます。次に、Rustのstd::hint::select_unpredictable()を使用して、可能であればコンパイラにブランチを発行しないように指示します。多くの場合、CPUにはブランチなしで2つの値の間で条件付きで選択するための特別な命令があります。

新しいブランチレスバージョンは次のようになります。

use std::hint::select_unpredictable;

fn bucketize_branchless_impl(
    arr: &[f64],
    boundaries: &[f64],
) -> Vec<usize> {
    let size = boundaries.len();
    let n_iterations = (size as f64).log2().ceil() as usize;
    let mut result = Vec::with_capacity(arr.len());

    for value in arr {
        let mut left = 0;
        let mut remaining_size = size;

        // ブランチレスバイナリ検索:検索領域を半分に切り続けます。
        for _ in 0..n_iterations {
            let half = remaining_size / 2;
            let middle = left + half;
            // 条件付き操作:boolならa、そうでなければb。実際のブランチなしでコンパイラによって生成されることを期待します。
            left = select_unpredictable(
                boundaries[middle] < *value,
                middle,
                left,
            );
            remaining_size -= half;
        }

        // 元のアルゴリズムとのオフバイワンエラーを修正します。
        left = select_unpredictable(
            boundaries[left] < *value,
            left + 1,
            left,
        );
        result.push(left);
    }
    result
}

そして、2つのバージョンのパフォーマンス比較を以下に示します。

コード➘ 経過マイクロ秒➘ CPU命令数➘ ブランチ命令数➘ ブランチ予測ミス率 %➚ IPC
bucketize_classic(DATA, BOUNDARIES)44,588.9112,979,34626,996,94216.5%0.7
bucketize_branchless(DATA, BOUNDARIES)9,849.3🏆111,101,14619,020,5180.0%3.1

➘ 数値が小さいほど良い、➚ 数値が大きいほど良い

注目すべき点は以下の通りです。

  1. 新しいバージョンはブランチ数が少ない:値あたり19回、元の27回と比較して。
  2. ブランチ予測ミスが完全に解消された。
  3. IPC(サイクルあたりの命令数)が大幅に向上した。これはCPUが並列実行できる命令数を測定するもので、高いほど良い:ブランチが少なく、より予測可能になったことで、CPUはより多くの命令レベル並列性を使用できるようになりました。

結果として、わずかに多くのCPU命令を使用しているにもかかわらず、はるかに高速な実装が得られました。

ブランチと無駄な作業の排除

コードのメカニカルシンパシーを改善したことで、速度の他の要因、つまりコンパイルのチューニングと、より少ない作業を行うことによるアルゴリズム効率の向上に取り組む機会を得ました。

まず、ブランチレスコードにはまだ値あたりのブランチが19個あります。そのうち7〜8個はfor _ in 0..n_iterationsです。forループを継続または終了するかどうかを決定するにはブランチが必要であり、n_iterationsは255程度のlog2です。しかし、残りはどこから来るのでしょうか?

これらの追加のブランチは、Rustコンパイラがベクトルおよび配列アクセスに境界チェックを追加するために存在します。インデックス付きの読み書きごとに、インデックスが範囲外でないかを確認するチェックがあり、メモリの安全性を確保します。長さ10のベクトルのインデックス100への書き込みは、クラッシュやメモリ破損につながる可能性があります。境界チェックは、バグを検出するという点では良いものですが、追加の計算が発生するという点では悪いものです。そのため、Rustのunsafeコードを使用して、境界チェックをバイパスするget_unchecked()のようなAPIを呼び出します。これにより、コードが引き続き正しいことを保証する責任が私に移ります。

次に、half/remaining_sizeの計算が、すべてのバイナリ検索でまったく同じであることを確認してください。理論的には、これは無駄な作業です。実際には、CPUはその余分な1〜2個の命令を並列実行できるため、これらの値を事前計算するとCPU命令数は少なくなりますが、IPCがわずかに低下し、同じ速度になります。それでも、これらの値を事前計算します。害はなく、unsafeコードの安全性の不変条件を表現しやすくなります。

結果として得られるコードは次のようになります。

fn bucketize_branchless2_impl(
    arr: &[f64],
    boundaries: &[f64],
) -> Vec<usize> {
    let size = boundaries.len();
    let n_iterations = (size as f64).log2().ceil() as usize;

    // ハーリング値を事前計算します。n_iterationsのサイズのVecを作成し、ゼロで埋めます:
    let mut halves = vec![0usize; n_iterations];
    let mut remaining_size = size;
    for i in 0..n_iterations {
        let half = remaining_size / 2;
        halves[i] = half;
        remaining_size -= half;
    }
    // Rust(および読者)に、halvesはもはや変更不可能であることを伝えます:
    let halves = halves;

    // 後続のunsafe操作が依存する不変条件の安全チェック:halvesの合計はboundariesの長さ未満です。
    assert!(
        halves.iter().copied().sum::<usize>() < boundaries.len()
    );

    let mut result = Vec::with_capacity(arr.len());
    for value in arr {
        let mut left = 0;

        for half in &halves {
            let middle = left + half;
            left = select_unpredictable(
                // 安全性:`left`と`middle`は`halves`の合計以下であり、上記のコードは、この合計が`boundaries`の長さ未満であることをアサートしています。
                unsafe {
                    *boundaries.get_unchecked(middle)
                } < *value,
                middle,
                left,
            );
        }

        left = select_unpredictable(
            // 安全性:上記のコメントを参照してください。
            unsafe { *boundaries.get_unchecked(left) } < *value,
            left + 1,
            left,
        );
        result.push(left);
    }
    result
}

そして、そのパフォーマンスは次のとおりです。

コード➘ 経過マイクロ秒➘ CPU命令数➘ ブランチ命令数➘ ブランチ予測ミス率 %➚ IPC
bucketize_branchless(DATA, BOUNDARIES)9,865.5111,101,22419,020,5190.0%3.1
bucketize_branchless2(DATA, BOUNDARIES)7,278.5🏆66,101,6676,020,6140.0%2.5

➘ 数値が小さいほど良い、➚ 数値が大きいほど良い

予想通り、ブランチ数が少なくなりました。全体として、命令数は少なくなりました(良い)、IPCはわずかに低下しました(悪い)、そして最も重要なことに、コードは高速になりました。

命令レベル並列性の向上(単一CPUコア内)

最後に、メカニカルシンパシーに戻ります。各値に対する小さなループは、各反復のleftが前の反復のleftに依存するため、命令レベル並列性が制限されます。これは、命令を並列実行することを困難にする依存関係です。

これを解決するために、入力配列内の異なる値が基本的に同じ操作を受けていることに注意する価値があります。元のバージョンでは、内部反復の回数は異なりましたが、今では各値に対して同じ回数の反復が発生しています。

そのため、halvesに対する反復を外側のループにし、arrの値を反復することを内側のループに再構成します。以前は逆でした。これにより、内側のループ内で異なる独立した値に対する操作が発生し、CPUがより多くの命令を並列実行できるようになることが期待できます。

fn bucketize_branchless3_impl(
    arr: &[f64],
    boundaries: &[f64],
) -> Vec<usize> {
    let size = boundaries.len();
    let n_iterations = (size as f64).log2().ceil() as usize;

    let mut halves = vec![0usize; n_iterations];
    let mut remaining_size = size;
    for i in 0..n_iterations {
        let half = remaining_size >> 1;
        halves[i] = half;
        remaining_size -= half;
    }
    let halves = halves;

    assert!(
        halves.iter().copied().sum::<usize>() < boundaries.len()
    );

    let mut result = Vec::with_capacity(arr.len());
    // 16個のチャンクで反復します:
    for chunk in arr.chunks(16) {
        // 長さ16でゼロで埋められた配列(Vecのようなものですが、固定長でスタック上にあります)を作成します:
        let mut lefts = [0; 16];

        // 値を先に反復するのではなく、まずhalvesを反復し、次に値のチャンクを反復します。すべての値を`half`ごとに1回反復すると、メモリキャッシュの局所性が悪化するため、チャンクを使用します。
        for half in &halves {
            // この内側のループで実行する操作は、CPUが並列実行しやすいものです。
            for (i, value) in chunk.iter().enumerate() {
                let left = unsafe { lefts.get_unchecked(i) };
                let middle = left + half;
                *unsafe { lefts.get_unchecked_mut(i) } = 
                    select_unpredictable(
                        unsafe {
                            *boundaries.get_unchecked(middle)
                        } < *value,
                        middle,
                        *left,
                    );
            }
        }

        for (value, mut left) in chunk.iter().zip(lefts) {
            left = select_unpredictable(
                unsafe {
                    *boundaries.get_unchecked(left)
                } < *value,
                left + 1,
                left,
            );
            result.push(left);
        }
    }
    result
}

そして、すべてのバリエーションのパフォーマンス比較を以下に示します。最新のものが最も高速です。

コード➘ 経過マイクロ秒➘ CPU命令数➘ ブランチ命令数➘ ブランチ予測ミス率 %➚ IPC
bucketize_classic(DATA, BOUNDARIES)45,200.4112,982,28726,996,74916.6%0.7
bucketize_branchless(DATA, BOUNDARIES)9,685.2111,100,88819,020,4640.0%3.2
bucketize_branchless2(DATA, BOUNDARIES)7,280.466,101,4836,020,5710.0%2.5
bucketize_branchless3(DATA, BOUNDARIES)5,453.4🏆96,476,4158,833,0470.0%4.9

➘ 数値が小さいほど良い、➚ 数値が大きいほど良い

この最終バージョンはさらに高速です。より多くの命令を使用しますが、IPCが大幅に向上していることからわかるように、CPUはそれらの多くを並列実行できます。

あなたもコードを高速化できます

ここにはさらに速度向上の機会があります。まず、最も重要なこととして、並列処理を使用して複数のCPUコアを活用できます。また、シングルスレッドコードをさらに高速化する追加の方法もあります。私はそれを試して、機能するかどうかを確認するために実装しました。

しかし、結局のところ、これは単なるコード例の記事です。ここでの本当の価値は、私が別の14%の速度向上を実証することではなく、あなたが自分のコードを高速化することです。これは私が学んだように、あなたも学ぶことができることです。私は、まだ学ぶべきことがたくさんあるとしても、始めた頃よりもはるかに高速なソフトウェアを書くことができるようになりました。

メカニカルシンパシーを構築するのに役立つ書籍をいくつか紹介します。

これらの書籍は、パフォーマンスの他のソースではなく、主にメカニカルシンパシーに焦点を当てています。C言語の知識があることを前提としています。そして、これらは一般的な書籍であるため、学んだことを書いているコードの種類に翻訳する必要があります。

したがって、Pythonから使用されるデータサイエンスまたは科学計算ソフトウェアを特に高速化している場合は、私の新しいPythonパフォーマンスに関する書籍(現在早期アクセス中)を読むことから始めることをお勧めします。この特定のソフトウェアドメインに焦点を当てていることに加えて、この書籍は次のとおりです。

  • 計算パフォーマンスのより広範な入門書として機能し、速度のさまざまなアプローチ(アルゴリズム効率、コンパイル、メカニカルシンパシー、並列処理)をカバーしています。
  • Pythonの知識のみを前提としています。
  • この記事で議論したすべての概念、およびさらに多くの概念を紹介します。

Practices of Performanceの詳細はこちらをご覧ください。