8バイトはすでに数値である
Eight Bytes Are a Number (blog.sebastiansastre.co)
要約
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 +++
| Column | Meaning |
|---|---|
| calls | そのシステムコールが実行された回数 |
| errors | その呼び出しのうち失敗した回数。空白はゼロを意味します |
| seconds | そのシステムコール内で費やされた合計時間 |
| usecs/call | 1コールあたりの平均時間(マイクロ秒) |
| % time | この表におけるそのシステムコールの時間の割合 |
これにより、以下のことがわかります。
brk(NULL)はヒープの現在の終了位置を要求します。- 次の
brkはその終了位置を前方に移動させます。これは、アロケータが起動中にヒープを作成していることを意味します。 - 20480バイトの
mmapはMAP_STACKとしてマークされ、対応するmunmapは書き込み後、終了時に行われます。
munmap(0xffff953ef000, 1052672) は、追加のシステムコールを必要とした予約済みRAMを持つ Vec の解放であり、対応する mmap で行われたことに注意してください。