HN 日本語サマリー

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

8バイトはすでに数値である

Eight Bytes Are a Number (blog.sebastiansastre.co)

6 pointsby sebastianconcpt2 コメント

要約

Rustにおけるデータパース処理において、`Vec`によるヒープ確保を避けるゼロコピートラッキング技術の重要性を解説しています。これにより、不要なメモリ割り当てやシステムコールを削減し、特に高速なデータ処理が求められるシステムでパフォーマンスを大幅に向上させることができます。

全文翻訳

Eight Bytes Are Already a Number

下流での処理のためにデータをパースする必要があるとき、処理結果を早く得たいという熱意から、パースの方法にかかるコストを見落としてしまうことがあります。

例えば、「u64 としてパースして」という関数を見てみましょう。

fn parse_id(bytes: &[u8]) -> Result<u64, ParserError> {
    if bytes.len() < 8 {
        return Err(ParserError::InputTooShortForU64);
    }
    let owned = bytes[..8].to_vec();
    Ok(u64::from_le_bytes(owned.try_into().map_err(ParserError::InvalidU64)?))
}

この関数は、長さをチェックし、スライスから適切なバイト数を Vec にコピーして、それを u64 としてパースします。プロダクションに適した 適切な Err を返します。すべて短く安全に見えます。

では、より注意深く調べてみましょう。

数値のような単純な型に対して、ヒープを使用すべきでしょうか、それとも使用しないべきでしょうか? システムコールについてはどうでしょうか?

Rustでは、Vec は常にヒープを使用します。その割り当ては、システムコールを必要とする場合もあれば、しない場合もあります。これは、アロケータが既に空きブロックを持っているか、OSにメモリを要求する必要があるかによって異なります。後者は負荷の下では容易に発生します。

多くのアプリケーションはこの詳細を気にしませんが、一部のアプリケーションは気にする必要があります。

気にする とどうなるのでしょうか?

8バイトのバッファはすでに u64 であり、from_le_bytes はそれを読み取る方法を知っているので、.to_vec() で割り当てた Vec は結果への道のりにおける偶発的な複雑さであると言えます。目的を達成するための一種の内部的な複雑さです。しかし、それが必要ない方法を見つけたらどうでしょうか? 最終結果のために「場所を確保する」必要がなければ、時間、労力、実行時コスト、そしてその「場所を確保する」ためのコードメンテナンスを節約できます。

読み取りをインプレースで行うように設計を進めてみましょう。

読み取り元への参照 &[u8] はすでに受け取っているので、次に u64 に読み取るべき正確な量を知る必要があります。この「インプレース読み取り」技術は、ゼロコピーと呼ばれるものです。なぜなら、処理のために何を行うにしても、開始するためにコピーを必要としないからです(&[u8] で作業することはその契約です)。

これらの8バイトは from_le_bytes のためにスタックに移動しますが、ヒープの使用はスキップしました。

Rustがその契約(型)において持つ強みは、プログラムでゼロコスト抽象化を生み出すために使用されます。したがって、データ内の正しい型を読み取り、すべてのエラーモードが適切にモデル化され、処理されている場合、あなたは実行時においてそのすべての強みを得ることができます。

コピーしない抽象化を使いましょう。

前の例をゼロコピー実装で示します。

fn parse_id(bytes: &[u8]) -> Result<u64, ParserError> {
    let raw: [u8; 8] = bytes.get(..8)
                        .ok_or(ParserError::InputTooShortForU64)?
                        .try_into().map_err(ParserError::InvalidU64)?;
    Ok(u64::from_le_bytes(raw))
}

今回は、バイトが既に存在する場所から読み取り、8バイトを読み取れることを検証し、それらを使用して確実に u64 を生成します。

もし型が u64 より複雑だったらどうなるでしょうか?

より長いメッセージも同じ技術の繰り返しであり、新しい契約で異なる形状になります。結局のところ、この再利用性がゼロコピーをテクニックたらしめているのです。

例えば、私が orderflow のために書いているコマンドコーデックでは、コマンドは enum です。リミットオーダーはアカウント、クライアントオーダーID、その他の詳細を保持します。オーダーIDによるキャンセルは2つの整数です。マーケットオーダーには価格フィールドがありません。バッファ内のバイトは、各エンジンコマンドで幅が異なります。

/// EngineCommand is a client request to change order state.
/// When a matching engine receives work, it uses this type so the variant is the
/// layout: NewLimit and NewMarket are separate, and New has no engine OrderId.
#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
pub enum EngineCommand {
    /// Request to open a limit order.
    NewLimit {
        account_id: AccountId,
        client_order_id: ClientOrderId,
        instrument_id: InstrumentId,
        side: Side,
        price: Price,
        quantity: Quantity,
    },

    /// Request to open a market order.
    NewMarket {
        account_id: AccountId,
        client_order_id: ClientOrderId,
        instrument_id: InstrumentId,
        side: Side,
        quantity: Quantity,
    },

    /// Request to cancel by engine OrderId.
    CancelByOrder { order_id: OrderId },
    ...
}

これらのコマンドでは、バイトの先頭にある1バイトがどのレイアウトを見ているかを示します。各レイアウトには1つの長さがあります。その長さをチェックし、フィールドを新しい型に読み込みます。例えば NewLimit を取ると、価格はティック数(i64)、数量はロット数、そして残りはすべて意図的に Copy です。これにより、コマンドは非常にコンパクトになるだけでなく、全体として、あるものをアンロックします。

定義の #[derive(Debug, Copy... に注目してください。

enum EngineCommand のどの要素もバッファを所有していません。

それらの Copy 性は、enum 全体の「コピー性」を完全にアンロックします。

エンジンがゼロコピー技術を使用してパースできるようにするための非常に意図的な設計上の選択であり、パースだけでなく、コマンドのさらなる下流処理も「インプレース」で行える可能性があります。

const NEW_LIMIT_LEN: usize = 57;

fn decode_new_limit(payload: &[u8]) -> Result<EngineCommand, DecodeError> {
    if payload.len() != NEW_LIMIT_LEN {
        return Err(DecodeError::Length);
    }
    Ok(EngineCommand::NewLimit {
        account_id: AccountId::new(read_u64(payload, 8)),
        client_order_id: ClientOrderId::new(read_u64(payload, 16)),
        instrument_id: InstrumentId::new(read_u64(payload, 24)),
        side: decode_side(payload[32])?,
        price: Price::new(read_i64(payload, 33)),
        quantity: Quantity::new(read_u128(payload, 41)),
    })
}

予想されるように、これらのコマンドはシーケンス番号と kind 型を持つエンベロープ内に存在し、ストリームからどのように読み取るかを定義します。

match kind {
    Kind::NewLimit => decode_new_limit(payload),
    Kind::NewMarket => decode_new_market(payload),
    Kind::CancelByOrder => decode_cancel_by_order(payload),
    Kind::CancelByClient => decode_cancel_by_client(payload),
    Kind::Replace => decode_replace(payload),
}

NewLimit は57バイトです。CancelByOrder は16バイトです。すべてがどのように読み取られるかは決定されており、それはコンパイラによって保証されます。残りは、無効なデータを摂取不可能にすることです。これは、考えられる各失敗モードを拡張的に処理することによって行います。

書き込みについてはどうでしょうか?

ゼロコピーのために使用したのと同じ設計意図を、書き込みにも適用します。つまり、エンコーダーは、呼び出し元が既に所有しているバッファに同じオフセットを書き込みます。各バリアントは、データバッファに予測可能に収まる整数の固定パイルです。書き込み中に中間的な割り当ては不要です。

ジャーナルフレームとデータグラムはどちらもペイロード領域を引き渡し、1つの書き込みを共有します。どちらのパスもコマンドのプライベートコピーを成長させません。

この enum は興味深いのは、バリアントがメモリレイアウトを変更しますが、ヒープからは解放されたままだからです。

これらの8バイトがすでに数値であったのと同じように、リミットオーダーは57バイトで、既知の場所にあります。残りは、それをシーケンス番号と kind バイトを持つエンベロープでラップし、安全かつ一貫性があり、正しい順序でそれらを探すように指示することです。

そして、Rustパーサーの仕事は、データがすでに配置されている場所からコマンドに応答し、エンジンが下流で処理できる毎秒数百ミリオンのコマンドという甘い結果を提供することです。

decode_frame/stream/cancel_by_order
time:   [4.0990 ns 4.1100 ns 4.1243 ns]
thrpt:  [242.46 Melem/s 243.31 Melem/s 243.96 Melem/s]

decode_frame/stream/new_limit
time:   [4.1835 ns 4.1934 ns 4.2058 ns]
thrpt:  [237.76 Melem/s 238.47 Melem/s 239.03 Melem/s]
                        
decode_frame/stream/new_market
time:   [4.0677 ns 4.0850 ns 4.1051 ns]
thrpt:  [243.60 Melem/s 244.80 Melem/s 245.84 Melem/s]

*Melem/s: メガ要素/秒


Verification Bonus

これを firsthand で証拠として収集するために、RustとDockerをインストールして、新しいプログラムを作成してください。

cargo new count-mem-syscalls-check

そしてこれを試してください。

fn parse_id(bytes: &[u8]) -> u64 {
    let mut owned = bytes[..8].to_vec();
    // glibc serves allocations above 128 KiB with mmap
    // so we force a larger allocation by reserving more space
    owned.reserve(1024 * 1024);
    let id = u64::from_le_bytes(owned[..8].try_into().unwrap());
    std::hint::black_box(owned);
    id
}

fn zero_copy_parse_id(bytes: &[u8]) -> u64 {
    u64::from_le_bytes(bytes[..8].try_into().unwrap())
}

fn main() {
    let bytes = 0x0123_4567_89ab_cdefu64.to_le_bytes();
    let id = parse_id(&bytes);
    // let id_2 = zero_copy_parse_id(&bytes);
    println!("{id}");
    // println!("{id_2}");
}

次に strace を実行してシステムコールを測定してください。まず parse_id(割り当てあり)を実行します。次にその呼び出しをコメントアウトし、zero_copy_parse_id のコメントを解除して、再度実行します。

毎回、この測定結果の表を確認してください。

docker run --rm \
  -v "$PWD":/src \
  -w /src \
  -e CARGO_TARGET_DIR=/tmp/target \
  -e DEBIAN_FRONTEND=noninteractive \
  rust:1-slim \
  sh -c 'apt-get update -qq && apt-get install -y -qq strace >/dev/null && cargo build --release --quiet && strace -c -e trace=memory /tmp/target/release/count-mem-syscalls-check && strace -e mmap,brk,munmap,write /tmp/target/release/count-mem-syscalls-check'

parse_id を使用した場合の私の結果(31個のシステムコール)です。

81985529216486895
% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
 44.01    0.000136           9        14           mmap
 31.07    0.000096          13         7           mprotect
 18.77    0.000058           8         7           munmap
  6.15    0.000019           6         3           brk
------ ----------- ----------- --------- --------- ----------------
100.00    0.000309           9        31           total
...

brk(NULL)                               = 0xaaaaf8b05000
brk(0xaaaaf8b26000)                     = 0xaaaaf8b26000
mmap(NULL, 20480, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS|MAP_STACK, -1, 0) = 0xffff9571e000
mmap(NULL, 1052672, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0xffff953ef000
munmap(0xffff953ef000, 1052672)         = 0
write(1, "81985529216486895\n", 18)     = 18
munmap(0xffff9571e000, 20480)           = 0
+++ exited with 0 +++

zero_copy_parse_id を使用した場合の私の結果(29個のシステムコール)です。

81985529216486895
% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
  0.00    0.000000           0         3           brk
  0.00    0.000000           0         6           munmap
  0.00    0.000000           0        13           mmap
  0.00    0.000000           0         7           mprotect
------ ----------- ----------- --------- --------- ----------------
100.00    0.000000           0        29           total
...

brk(NULL)                               = 0xaaaae88cb000
brk(0xaaaae88ec000)                     = 0xaaaae88ec000
mmap(NULL, 20480, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS|MAP_STACK, -1, 0) = 0xffffb07d6000
81985529216486895
write(1, "81985529216486895\n", 18)     = 18
munmap(0xffffb07d6000, 20480)           = 0
+++ exited with 0 +++
ColumnMeaning
callsそのシステムコールが実行された回数
errorsその呼び出しのうち失敗した回数。空白はゼロを意味します
secondsそのシステムコール内で費やされた合計時間
usecs/call1コールあたりの平均時間(マイクロ秒)
% timeこの表におけるそのシステムコールの時間の割合

これにより、以下のことがわかります。

  1. brk(NULL) はヒープの現在の終了位置を要求します。
  2. 次の brk はその終了位置を前方に移動させます。これは、アロケータが起動中にヒープを作成していることを意味します。
  3. 20480バイトの mmap は MAP_STACK としてマークされ、対応する munmap は書き込み後、終了時に行われます。

munmap(0xffff953ef000, 1052672) は、追加のシステムコールを必要とした予約済みRAMを持つ Vec の解放であり、対応する mmap で行われたことに注意してください。