Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

[インデックス 16871] ファイルの概要

コミット

commit 085159da267376309ff8cf718390e58276ba49a7
Author: Nick Craig-Wood <nick@craig-wood.com>
Date:   Thu Jul 25 13:28:27 2013 +1000

    crypto/md5: native arm assembler version
    
    An ARM version of md5block.go with a big improvement in
    throughput (up to 2.5x) and a reduction in object size (21%).
    
    Code size
    
      Before 3100 bytes
      After 2424 bytes
      21% smaller
    
    Benchmarks on Rasperry Pi
    
    benchmark                       old ns/op    new ns/op    delta
    BenchmarkHash8Bytes                 11703         6636  -43.30%
    BenchmarkHash1K                     38057        21881  -42.50%
    BenchmarkHash8K                    208131       142735  -31.42%
    BenchmarkHash8BytesUnaligned        11457         6570  -42.66%
    BenchmarkHash1KUnaligned            69334        26841  -61.29%
    BenchmarkHash8KUnaligned           455120       182223  -59.96%
    
    benchmark                        old MB/s     new MB/s  speedup
    BenchmarkHash8Bytes                  0.68         1.21    1.78x
    BenchmarkHash1K                     26.91        46.80    1.74x
    BenchmarkHash8K                     39.36        57.39    1.46x
    BenchmarkHash8BytesUnaligned         0.70         1.22    1.74x
    BenchmarkHash1KUnaligned            14.77        38.15    2.58x
    BenchmarkHash8KUnaligned            18.00        44.96    2.50x
    
    benchmark                      old allocs   new allocs    delta
    BenchmarkHash8Bytes                     1            0  -100.00%
    BenchmarkHash1K                         2            0  -100.00%
    BenchmarkHash8K                         2            0  -100.00%
    BenchmarkHash8BytesUnaligned            1            0  -100.00%
    BenchmarkHash1KUnaligned                2            0  -100.00%
    BenchmarkHash8KUnaligned                2            0  -100.00%
    
    benchmark                       old bytes    new bytes    delta
    BenchmarkHash8Bytes                    64            0  -100.00%
    BenchmarkHash1K                       128            0  -100.00%
    BenchmarkHash8K                       128            0  -100.00%
    BenchmarkHash8BytesUnaligned           64            0  -100.00%
    BenchmarkHash1KUnaligned              128            0  -100.00%
    BenchmarkHash8KUnaligned              128            0  -100.00%
    
    This also adds another test which makes sure that the sums
    over larger blocks work properly. I wrote this test when I was
    worried about memory corruption.
    
    R=golang-dev, dave, bradfitz, rsc, ajstarks
    CC=golang-dev, minux.ma, remyoudompheng
    https://golang.org/cl/11648043

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/085159da267376309ff8cf718390e58276ba49a7

元コミット内容

このコミットは、Go言語のcrypto/md5パッケージにARMアーキテクチャ向けのネイティブアセンブラバージョンを導入するものです。これにより、スループットが最大2.5倍向上し、オブジェクトサイズが21%削減されるという大きな改善がもたらされました。

具体的には、Raspberry Pi上でのベンチマーク結果が示されており、様々なサイズのハッシュ計算において、処理時間の短縮（ns/opの減少）、スループットの向上（MB/sの増加）、そしてメモリ割り当ての完全な排除（allocsとbytesの100%削減）が確認されています。

また、この変更には、より大きなブロックでのMD5計算が正しく機能することを確認するための追加テストも含まれています。これは、メモリ破損の懸念から追加されたものです。

変更の背景

Go言語は、そのパフォーマンスと並行処理の容易さから、サーバーサイドアプリケーションやツール開発で広く利用されています。しかし、組み込みシステムや低電力デバイス、特にARMアーキテクチャを搭載したデバイス（Raspberry Piなど）での利用においては、パフォーマンスが重要な課題となることがあります。

MD5のような暗号ハッシュ関数は、データの整合性チェックやデジタル署名など、多くのアプリケーションで頻繁に使用されます。これらの処理がCPUバウンドである場合、純粋なGo言語実装では、特定のアーキテクチャに最適化されたアセンブラ実装に比べて性能が劣る可能性があります。

このコミットの背景には、ARMベースのデバイスにおけるMD5計算のパフォーマンスボトルネックを解消し、Go言語がこれらの環境でより効率的に動作するようにするという明確な目的があります。特に、Raspberry Piのような人気のあるシングルボードコンピュータでのGoの利用を促進するため、MD5のような基本的な暗号プリミティブの最適化は不可欠でした。アセンブラによる最適化は、Goランタイムが提供する高度な抽象化レイヤーの下で、ハードウェアの特性を最大限に活用するための一般的な手法です。

前提知識の解説

MD5 (Message-Digest Algorithm 5)

MD5は、128ビット（16バイト）のハッシュ値を生成する広く使用されている暗号ハッシュ関数です。入力データがどんなに大きくても、常に固定長のハッシュ値を出力します。MD5は、データの改ざん検出（データの整合性チェック）によく使用されますが、衝突耐性（異なる入力から同じハッシュ値が生成される可能性）の脆弱性が発見されているため、セキュリティが最優先される場面（デジタル署名など）ではSHA-256などのより強力なハッシュ関数が推奨されています。しかし、ファイルの整合性チェックや非クリティカルな用途では依然として広く利用されています。

MD5の計算プロセスは、入力データを512ビット（64バイト）のブロックに分割し、各ブロックに対して一連の複雑なビット演算（AND, OR, XOR, NOT, ローテートなど）と加算を繰り返すことでハッシュ値を更新していくものです。このプロセスは4つのラウンドから構成され、各ラウンドで異なる非線形関数が適用されます。

ARMアーキテクチャ

ARM（Advanced RISC Machine）は、モバイルデバイス、組み込みシステム、IoTデバイス、そして最近ではサーバーやデスクトップPCにも広く採用されているRISC（Reduced Instruction Set Computer）ベースのCPUアーキテクチャです。低消費電力と高い電力効率が特徴であり、スマートフォンやタブレット、Raspberry Piなどのシングルボードコンピュータの心臓部として機能しています。

ARMプロセッサは、特定のタスク（例えば、ビット演算やメモリ操作）を非常に効率的に実行できる命令セットを持っています。Go言語のような高水準言語で書かれたコードは、コンパイラによってARMの機械語に変換されますが、コンパイラが生成する汎用的なコードよりも、熟練したアセンブラプログラマが手書きで最適化したコードの方が、特定のハードウェア特性（レジスタの利用効率、パイプライン処理、キャッシュの挙動など）を最大限に引き出し、より高いパフォーマンスを達成できる場合があります。

Go言語のアセンブラ

Go言語は、一部のパフォーマンスクリティカルな部分でアセンブラコードを使用することをサポートしています。Goのアセンブラは、Plan 9アセンブラと呼ばれる独特のシンタックスを使用しており、一般的なGAS (GNU Assembler) やNASM (Netwide Assembler) とは異なります。Goのアセンブラファイルは.s拡張子を持ち、Goのソースコードと連携してコンパイルされます。

Goのアセンブラは、Goの関数呼び出し規約（レジスタの使用、スタックフレームの管理など）に準拠しており、Goの関数からアセンブラ関数を呼び出したり、アセンブラ関数からGoの関数を呼び出したりすることが可能です。これにより、Goのコードベース全体の中で、特定のボトルネックとなる部分だけをアセンブラで最適化するというアプローチが可能になります。

このコミットでは、md5block_arm.sというファイルが追加されており、これはARMアーキテクチャ向けのMD5ブロック処理のコアロジックがGoのアセンブラで実装されていることを示しています。

ビルドタグ (+build)

Go言語のソースファイルには、ファイルの先頭に+buildディレクティブを記述することで、特定のビルド条件を指定できます。これは、異なるオペレーティングシステム、アーキテクチャ、またはカスタムビルドタグに基づいて、どのファイルをコンパイルに含めるかを制御するために使用されます。

例えば、// +build amd64は、このファイルがAMD64アーキテクチャ向けにのみコンパイルされることを意味します。このコミットでは、md5block.goやgen.goの+buildタグが変更され、ARMアーキテクチャ向けのアセンブラ実装が利用可能になった際に、Goの汎用実装がコンパイルされないように制御されています。これにより、特定のアーキテクチャに最適な実装が自動的に選択されるようになります。

技術的詳細

このコミットの主要な技術的貢献は、Go言語のcrypto/md5パッケージにおけるMD5ハッシュ計算のコア部分を、ARMアーキテクチャに特化したネイティブアセンブラで再実装した点にあります。

MD5の計算は、入力データを64バイト（512ビット）のブロックに分割し、各ブロックに対して4つのラウンドからなる一連のビット演算と加算を適用することで、内部状態（4つの32ビットレジスタA, B, C, D）を更新していきます。このプロセスは非常に計算集約的であり、特に大量のデータをハッシュ化する際にはパフォーマンスのボトルネックとなりがちです。

Goの標準ライブラリにおけるMD5の既存の実装は、純粋なGo言語で書かれていました。Goコンパイラは非常に効率的な機械語を生成しますが、特定のCPUアーキテクチャのマイクロアーキテクチャ的特性（例：レジスタの数、命令のレイテンシ、並列実行能力、特定の命令の有無）を最大限に活用することは、手書きのアセンブラコードに一日の長があります。

このコミットで追加されたmd5block_arm.sファイルは、MD5のブロック処理（block関数）をARMアセンブラで実装しています。このアセンブラコードは、以下の最適化戦略を採用していると考えられます。

  1. レジスタの効率的な利用: ARMプロセッサの豊富な汎用レジスタを最大限に活用し、メモリへのアクセス回数を減らすことで、データ転送のオーバーヘッドを削減します。MD5の内部状態変数（A, B, C, D）や中間計算結果をレジスタに保持することで、高速な演算を可能にします。
  2. MD5ラウンド関数の最適化: MD5の各ラウンドで実行されるビット演算（AND, OR, XOR, NOT）とローテート操作は、ARMの命令セットで効率的に表現できます。アセンブラでは、これらの操作を単一または少数の命令で実行し、パイプラインの効率を最大化するように命令をスケジューリングできます。
  3. 定数のロード: MD5の計算には、多数の固定定数（Tテーブル）が使用されます。アセンブラでは、これらの定数を効率的にレジスタにロードし、計算中に再利用する戦略を立てることができます。
  4. アライメント処理の最適化: 入力データがメモリ上でアライメントされていない場合、Goの汎用コードでは追加のコピー操作やバイト単位のアクセスが必要になることがあります。アセンブラでは、アライメントされていないデータに対するアクセスをより効率的に処理したり、必要に応じて最適な方法でアライメントされたバッファにコピーしたりするロジックを直接記述できます。コミットメッセージのベンチマーク結果にUnalignedという項目があることから、この最適化が特に効果を発揮していることが伺えます。
  5. メモリ割り当ての削減: ベンチマーク結果のallocsとbytesが100%削減されていることから、アセンブラ実装では、MD5ブロック処理中に一時的なバッファや中間結果のためにヒープメモリを一切割り当てていないことが示唆されます。これは、スタック上のローカル変数やレジスタのみを使用することで達成され、ガベージコレクションのオーバーヘッドを完全に排除し、パフォーマンスを大幅に向上させます。

md5block_arm.sのコードを見ると、#defineディレクティブを使ってMD5の各ラウンドの計算ロジックをマクロとして定義しており、これによりコードの可読性と再利用性を高めつつ、繰り返しパターンを効率的に記述しています。また、MOVM.IA.Wのような命令は、複数のレジスタを一度にロード/ストアできるARMの命令であり、これによりメモリ操作の効率が向上しています。

このアセンブラ実装の導入に伴い、GoのビルドシステムがARMアーキテクチャでコンパイルする際に、この最適化されたアセンブラバージョンを自動的に選択するように、src/pkg/crypto/md5/gen.goとsrc/pkg/crypto/md5/md5block.goのビルドタグが更新されています。具体的には、!armタグが追加され、ARMアーキテクチャではこれらのGoファイルがコンパイル対象から外れるように設定されています。一方で、src/pkg/crypto/md5/md5block_decl.goにはarmタグが追加され、アセンブラ実装の宣言がARMビルドに含まれるようになっています。

追加されたTestLargeテストは、MD5の計算が大きなデータブロック（10000バイトのデータに対して、オフセットやブロックサイズを変えながら）でも正しく機能することを確認するためのものです。これは、アセンブラ実装がメモリ破損や境界条件の問題を引き起こしていないことを検証する上で非常に重要です。

コアとなるコードの変更箇所

このコミットにおける主要なコード変更は以下のファイルに集中しています。

  1. src/pkg/crypto/md5/gen.go:

    • ビルドタグが変更されました。以前は!amd64でしたが、!amd64,!386,!armに変更され、ARMアーキテクチャでもこの汎用Go実装がコンパイルされないように設定されました。これは、ARM向けに専用のアセンブラ実装が提供されるためです。

  2. src/pkg/crypto/md5/md5_test.go:

    • TestLargeという新しいテスト関数が追加されました。このテストは、大きなデータブロック（10000バイト）に対して、異なるオフセットとブロックサイズでMD5ハッシュを計算し、結果が期待通りになることを検証します。これは、アセンブラ実装がメモリ破損や境界条件の問題を引き起こしていないことを確認するために重要です。

  3. src/pkg/crypto/md5/md5block.go:

    • ビルドタグが変更されました。以前は!amd64,!386でしたが、!amd64,!386,!armに変更され、ARMアーキテクチャでもこの汎用Go実装がコンパイルされないように設定されました。gen.goと同様の理由です。

  4. src/pkg/crypto/md5/md5block_arm.s:

    • 新規追加されたファイルです。このファイルには、ARMアーキテクチャ向けのMD5ブロック処理のネイティブアセンブラコードが記述されています。MD5の4つのラウンドの計算ロジックが、ARMの命令セット（EOR, AND, ADD, MOVW, MOVM.IA.Wなど）とGoのアセンブラシンタックスを用いて実装されています。レジスタの割り当て、スタックフレームの管理、MD5定数のロードなどが詳細に定義されています。

  5. src/pkg/crypto/md5/md5block_decl.go:

    • ビルドタグが変更されました。以前はamd64 386でしたが、amd64 386 armに変更されました。これにより、このファイル（アセンブラ実装の宣言を含む）がARMアーキテクチャ向けビルドにも含まれるようになります。

コアとなるコードの解説

このコミットの核心は、src/pkg/crypto/md5/md5block_arm.sに新しく追加されたARMアセンブラコードです。このファイルは、Goのcrypto/md5パッケージのblock関数（MD5ハッシュ計算の主要なループを処理する部分）のARMアーキテクチャ向け最適化バージョンを提供します。

GoのアセンブラはPlan 9アセンブラのシンタックスを使用しており、一般的なx86アセンブラとは異なる表記法を持っています。

md5block_arm.sの主要な構造と機能は以下の通りです。

  • レジスタ定義: ファイルの冒頭で、MD5計算で使用するARMレジスタに意味のある名前（table, data, a, b, c, d, c0〜c3, t0, t1など）を割り当てています。これにより、コードの可読性が向上しています。
  • TEXT ·block(SB), 7, $84-16:
    • これはGoのblock関数のアセンブラ実装の開始を宣言しています。
    • ·block(SB): block関数をシンボルテーブルに登録します。SBはStatic Baseレジスタを意味し、グローバルシンボルであることを示します。
    • 7: GoのABI（Application Binary Interface）における引数の数（この場合はdigとp）。
    • $84-16: スタックフレームのサイズを示します。84はローカル変数と一時的なストレージに必要なバイト数、16は引数に割り当てられたスタック上のスペースです。
  • 引数のロード:
    • MOVW p+4(FP), R(data): pスライス（Goの[]byte型）のデータポインタをdataレジスタにロードします。FPはFrame Pointerを意味し、スタックフレーム上の引数にアクセスするために使用されます。
    • MOVW p_len+8(FP), R(t0): pスライスの長さをt0レジスタにロードします。
  • アライメント処理:
    • AND.S $3, R(data), R(t0): データポインタが4バイトアライメントされているか（data % 4 == 0）をチェックします。
    • BEQ aligned: アライメントされていればalignedラベルにジャンプし、コピーをスキップします。
    • アライメントされていない場合、runtime·memmove(SB)を呼び出して、データをアライメントされた一時バッファ（buf）にコピーします。これは、アライメントされたデータの方がARMプロセッサで効率的に処理できるためです。
  • MD5状態のロード:
    • MOVW dig+0(FP), R(c0): digest構造体（MD5の内部状態A, B, C, Dを含む）へのポインタをc0レジスタにロードします。
    • MOVM.IA (R(c0)), [R(a),R(b),R(c),R(d)]: digest構造体からMD5の4つのアキュムレータ（A, B, C, D）をレジスタa, b, c, dに一括ロードします。MOVM.IAはIncrement Afterの複数レジスタロード命令です。
  • MD5ラウンドマクロ:
    • #define ROUND1(a, b, c, d, index, shift, const): MD5の各ラウンドの計算ロジックをマクロとして定義しています。これにより、コードの重複を避け、可読性を高めています。
    • 各マクロ内では、MD5の仕様に従ってビット演算（EOR (XOR), AND）と加算（ADD）が実行されます。
    • ADD R(a)@>(32-shift), R(b), R(a): これはローテート操作（循環シフト）と加算を組み合わせたものです。@>は右ローテートを示します。
    • MOVM.IA.W (R(table)), [R(c0),R(c1),R(c2),R(c3)]: MD5の定数テーブルから、そのラウンドで使用する定数をレジスタにロードします。Wはワード（32ビット）アクセスを示します。
  • ループ処理:
    • loop:ラベルから始まり、CMP R(t0), R(data)とBLO loopで、入力データの全ブロックが処理されるまでループを繰り返します。ADD $64, R(data)で次の64バイトブロックに進みます。
  • MD5状態のストア:
    • MOVM.IA [R(a),R(b),R(c),R(d)], (R(t0)): 更新されたMD5アキュムレータ（A, B, C, D）の値をdigest構造体に一括でストアします。
  • MD5定数テーブル:
    • ファイルの最後には、MD5の計算で使用される固定定数（Tテーブル）がDATAディレクティブを使って定義されています。これらの定数は、MD5アルゴリズムの不可欠な部分です。
    • GLOBL ·table(SB),8,$256: tableシンボルをグローバルに定義し、そのサイズ（256バイト）を指定しています。

このアセンブラコードは、MD5の計算プロセスをARMプロセッサの命令セットに直接マッピングすることで、Go言語のコンパイラが生成する汎用コードよりも、より少ない命令数で、より効率的に実行されるように設計されています。特に、レジスタの効率的な利用、メモリアクセスの最小化、そしてアライメント処理の最適化が、ベンチマーク結果に示される大幅なパフォーマンス向上に寄与しています。

関連リンク

参考にした情報源リンク

  • Go言語のソースコード (特にsrc/pkg/crypto/md5ディレクトリ): https://github.com/golang/go/tree/master/src/crypto/md5
  • Go言語のIssue Tracker (関連する議論や背景情報がある可能性): https://github.com/golang/go/issues
  • Go言語のCode Review (CL 11648043): https://golang.org/cl/11648043 (コミットメッセージに記載されているリンク)
  • ARMアーキテクチャに関する一般的な情報源 (例: Wikipedia, ARM公式ドキュメント)
  • MD5アルゴリズムに関する一般的な情報源 (例: Wikipedia, Cryptography Stack Exchange)
  • Go言語におけるアセンブラの使用例や解説記事 (例: "Go Assembly Language" by Russ Cox, "Writing Go Assembly" by Dave Cheney)
  • Raspberry Piのパフォーマンスに関する情報源 (ベンチマーク結果の背景理解のため)
  • Go言語のビルドタグに関するドキュメント: https://go.dev/cmd/go/#hdr-Build_constraints
  • Go言語のABIに関する情報 (アセンブラコードの理解のため)