- 接続性監視システムの ICMP Echo Request 記録構造体を縮小する過程で、リングバッファのメモリ使用量が 12KiB から 4KiB に減少
sent_ns と received_ns の両方を保存せず、受信後は 遅延時間 だけを残すように共用体を使うと、配列サイズが 8KiB に縮小- ナノ秒精度の代わりに 100 マイクロ秒単位を使い、
received をビットフィールドに変えたが、構造体パディング のため追加の削減は発生しなかった
- 送信元アドレスの代わりに ICMP
identifier の一部の意味を 4 ビットカウンタで置き換えると、構造体は 8 バイトになり、512 要素の配列は 4KiB になった
- アプリケーションにはメモリ制約がなかったため実用上の必要性はなかったが、フィールド配置やビットアクセスのコストまで検討する最適化実験になった
問題設定: ping 記録を保存する方法
- 接続性監視システムは複数のサーバーに ICMP Echo Request を送り、1 分・5 分・15 分区間の遅延時間とパケット損失の平均を観測する
- 最初に思いついた保存方法は 512 エントリのリングバッファで、各エントリは送信時刻、受信時刻、送信元アドレス、シーケンス番号、受信有無を持つ
- 初期構造体配列
pings_rb[512] のサイズは 12KiB と測定された
struct ping_timestamp {
uint64_t sent_ns;
uint64_t received_ns;
in_addr_t source_addr;
uint16_t seq_no;
bool received;
};
最初の削減: 送信時刻と経過時間を共用体に統合
- 実際に残したい値は受信後の
received - sent の遅延時間なので、送信時刻と経過時間を同時に保持する必要はない
sent_ts と elapsed_ts を共用体で束ねた構造体は、同じスロットを送信前には送信時刻として、受信後には経過時間として使う- この変更後、512 要素の配列サイズは 12KiB から 8KiB に減少した
struct ping_timestamp_2 {
union {
uint64_t sent_ts;
uint64_t elapsed_ts;
};
in_addr_t source_addr;
uint16_t seq_no;
bool received;
};
2 回目の試み: 精度縮小とビットフィールド
- ping 時間は数十・数百・数千ミリ秒単位で測定されるため、ナノ秒精度をすべて保存する必要はない
- 時間単位を 100 マイクロ秒、つまり 0.1ms 単位に変えると、43 ビットで最大 20 年間の ping 追跡が可能になる
received の真偽値に 8 ビットを使うのは過剰なので、ビットフィールドを適用した- しかし
ping_timestamp_3 の配列サイズも 8KiB のままで、追加の削減は発生しなかった
struct ping_timestamp_3 {
uint64_t sent_or_elapsed_ts: 43;
uint64_t received: 1;
uint64_t seq_no: 16;
in_addr_t source_addr;
};
構造体パディングのため縮まらなかったサイズ
ping_timestamp_2 には最後にアラインメント要件を満たすためのパディングバイトが付くping_timestamp_3 は先頭 8 バイトに時間、受信有無、シーケンス番号を入れるが、その後ろに送信元アドレスとパディングが残る- ビットフィールドを適用しても 36 ビットのパディングが残り、構造体全体のサイズは縮まらない
- 単純に bool をビットに縮めるだけでは、メモリ配置とアラインメントの問題は解決しない
送信元アドレスの削除と 4 ビットカウンタ
- 製品がモバイルデータネットワーク上で動作している間は送信元アドレスが頻繁に変わるため、従来の構造体では送信元アドレスを保存していた
- アドレスが変わるとシーケンス番号もリセットされ、過去には異なる送信元アドレスと同じシーケンス番号を持つパケットが同時に処理されたことがあった
- ICMP Echo Request には、アプリケーションが自分の送ったパケットを識別できる 16 ビットの
identifier フィールドがある
- 16 ビット全体を使う必要はないため、余った 4 ビットを送信元アドレス変更時に増加するローリングカウンタとして使う
- このカウンタは、アプリケーションの別の場所で監視されている送信元アドレス変更に合わせて増加する
struct ping_timestamp {
uint64_t elapsed_or_sent_ts : 43;
uint64_t received : 1;
uint64_t counter: 4;
uint64_t seq_no: 16;
};
最終結果とフィールド配置
- 最終構造体は送信元アドレスフィールドを削除し、64 ビット内に時間、受信有無、カウンタ、シーケンス番号を収める
- 512 要素のリングバッファ配列サイズは 4KiB となり、1 ページ分のデータに収まった
- 初期の 12KiB と比べて合計 8KiB を削減した
- フィールド順は
seq_no が 16 ビット境界に合うよう調整され、ロード時にシフトなしで単一の ldrh 命令で読める
elapsed_or_sent_ts を読むときにはマスクだけが必要になる
追加最適化: 受信ビットアクセスのコスト削減
struct ping_timestamp {
uint64_t elapsed_or_sent_ts : 43;
uint64_t counter: 4;
uint64_t not_received : 1;
uint64_t seq_no: 16;
};
結論
- 最適化の結果、メモリ使用量は 12KiB から 4KiB に減ったが、アプリケーション自体はメモリ制約を受けていない
- 実際の必要性とは別に、構造体レイアウト、パディング、ビットフィールド、命令レベルのアクセスコストを検討する実験になった
- 最後の注釈では、「問題」という表現も緩い意味で使っており、ベンチマークすらしていないと明かしている
1件のコメント
Lobste.rsの意見
こういう問題を考えるのがもう楽しくなくなる日が来たら、その日がプログラミングをやめる時だと思う
早すぎる最適化はいつだって楽しい
その最適化がなぜ早すぎたのかに気づいたあと、その結果を片付ける作業はたいてい楽しくないけど
タイムスタンプに43ビット使うという部分が少し分かりにくい。24ビットで十分に見える
512個のリングバッファの話からすると、2秒ごとに新しい ping を送って、直近17分4秒の ping を追跡しているように見える
最初の段階として、理想的なタイマー/シーケンス番号に対するデルタエンコーディングを使えばよい。最後の送信時刻を2秒ずつ増やし、リングバッファのインデックスを見れば、パケットがいつ送られるべきかは簡単に分かるので、ちょうど時間どおりに送れたのか、0.1ms遅れたのか、2.3ms遅れたのかなどを記録すればよい
経過時間についても、その後は ping が期限切れになるのだから、17分4秒を超える必要はなさそうだ。512 × 2s = 10,240,000 × 100μs なので、その精度なら約23.3ビットで足りるし、必要なら24ビットに切り上げればよい。余る無効なビットパターン約6,536,216個も、別の用途に使えるかもしれない
さらに24ビットなら、「送信済み」の精度をずっと高くして量子化誤差を減らせる。マイクロ秒精度でも ping は最大16秒遅れて送られうるので、十分余裕があるように見える
サンプルを64ビットから48ビットに減らしたとき、性能の助けになるのか足を引っ張るのかは分からない。x86 と ARM の 32ビット/64ビット環境ごとに結果が違っても驚かない
ただ、元のサイズでもかなり古いプロセッサのデータキャッシュに十分すんなり収まる程度なので、メモリ節約が差を生むとは思えない
早すぎる最適化をする理由はまさにそれだと確信している。趣味としてのスポーツなんだ
システムを設計したり低水準のシステム言語で作業したりするとき、早すぎる最適化は正直いちばん好きなことの一つだ
少なくとも、あとで時間とメモリを節約してくれるかもしれないという希望がある。中途半端な結果で済むなら「なんでこんな作りにしたんだ？」を理解しようとして頭痛が少し増す程度で、最悪の場合であり、時にはむしろより良い場合でもあるのは、設計中の最適化作業が大きくなりすぎてプロジェクトそのものが進まなくなることだ。「ああ、複雑になりすぎた。そもそもなんでこれをやってるんだ？」となってプログラムを閉じる