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

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

このコミットは、Goランタイムにおいてメモリのゼロクリアとコピーのパフォーマンスを大幅に向上させるために、Duff's Device（ダフのデバイス）と呼ばれる最適化手法を導入したものです。特にARMアーキテクチャ向けに、アセンブリコードレベルでの変更と、コンパイラおよびリンカの対応が含まれています。

コミット

commit 51b72d94debdab3e72ce4236e03d8933d217e9b3
Author: Keith Randall <khr@golang.org>
Date:   Wed May 7 13:17:10 2014 -0700

    runtime: use duff zero and copy to initialize memory
    
    benchmark                 old ns/op     new ns/op     delta
    BenchmarkCopyFat512       1307          329           -74.83%
    BenchmarkCopyFat256       666           169           -74.62%
    BenchmarkCopyFat1024      2617          671           -74.36%
    BenchmarkCopyFat128       343           89.0          -74.05%
    BenchmarkCopyFat64        182           48.9          -73.13%
    BenchmarkCopyFat32        103           28.8          -72.04%
    BenchmarkClearFat128      102           46.6          -54.31%
    BenchmarkClearFat512      344           167           -51.45%
    BenchmarkClearFat64       50.5          26.5          -47.52%
    BenchmarkClearFat256      147           87.2          -40.68%
    BenchmarkClearFat32       22.7          16.4          -27.75%
    BenchmarkClearFat1024     511           662           +29.55%
    
    Fixes #7624
    
    LGTM=rsc
    R=golang-codereviews, khr, bradfitz, josharian, dave, rsc
    CC=golang-codereviews
    https://golang.org/cl/92760044

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

https://github.com/golang/go/commit/51b72d94debdab3e72ce4236e03d8933d217e9b3

元コミット内容

runtime: use duff zero and copy to initialize memory

benchmark                 old ns/op     new ns/op     delta
BenchmarkCopyFat512       1307          329           -74.83%
BenchmarkCopyFat256       666           169           -74.62%
BenchmarkCopyFat1024      2617          671           -74.36%
BenchmarkCopyFat128       343           89.0          -74.05%
BenchmarkCopyFat64        182           48.9          -73.13%
BenchmarkCopyFat32        103           28.8          -72.04%
BenchmarkClearFat128      102           46.6          -54.31%
BenchmarkClearFat512      344           167           -51.45%
BenchmarkClearFat64       50.5          26.5          -47.52%
BenchmarkClearFat256      147           87.2          -40.68%
BenchmarkClearFat32       22.7          16.4          -27.75%
BenchmarkClearFat1024     511           662           +29.55%

Fixes #7624

LGTM=rsc
R=golang-codereviews, khr, bradfitz, josharian, dave, rsc
CC=golang-codereviews
https://golang.org/cl/92760044

変更の背景

Go言語のランタイムにおいて、メモリのゼロクリア（初期化）やメモリコピーは頻繁に行われる操作です。特に、構造体の初期化やスライス・配列のコピーなど、様々な場面でこれらの操作がパフォーマンスに影響を与えます。従来のループベースの実装では、特に小〜中規模のメモリブロックに対して、ループのオーバーヘッドが無視できない問題となっていました。

このコミットの背景には、GoのIssue #7624があります。このIssueでは、Goのコンパイラが生成するメモリゼロクリアおよびコピーのコードが非効率的であるという問題が提起されていました。特に、ARMアーキテクチャのような組み込みシステムやモバイル環境では、CPUのキャッシュ効率や命令パイプラインの最適化が重要であり、より高速なメモリ操作が求められていました。

コミットメッセージに示されているベンチマーク結果は、この変更がもたらす劇的なパフォーマンス改善を明確に示しています。BenchmarkCopyFat系のベンチマークでは最大約75%の高速化、BenchmarkClearFat系のベンチマークでも最大約54%の高速化が達成されており、これはGoアプリケーション全体の実行速度向上に大きく貢献するものです。ただし、BenchmarkClearFat1024のみパフォーマンスが低下している点も注目に値します。これはDuff's Deviceの特性上、非常に大きなブロックに対しては必ずしも最適ではない場合があることを示唆しています。

前提知識の解説

Duff's Device（ダフのデバイス）

Duff's Deviceは、1983年にトム・ダフによって考案された、ループアンローリング（loop unrolling）を最適化するためのプログラミングテクニックです。主にC言語で用いられ、特定のサイズのブロックを効率的にコピーまたは初期化する際に利用されます。

動作原理: 通常のループアンローリングでは、ループの反復回数が固定されている場合に、その回数分の処理を直接コードに記述することで、ループ制御のオーバーヘッドを削減します。しかし、Duff's Deviceは、ループの反復回数が実行時に決定される場合でも、効率的なアンローリングを実現します。

これは、switch文とdo-whileループを組み合わせることで実現されます。switch文の各caseラベルは、アンロールされたループの特定の位置に対応します。処理を開始する前に、残りの処理回数に基づいて適切なcaseラベルにジャンプし、そこからdo-whileループに入ります。これにより、ループの先頭で条件判定を行うオーバーヘッドを最小限に抑えつつ、複数の処理を一度に実行できます。

アセンブリ言語でのDuff's Device: アセンブリ言語では、Duff's Deviceはより直接的に実装されます。具体的には、一連の繰り返し処理（例: MOVW命令によるメモリコピー）を連続して記述し、処理すべき残りの量に応じて、この連続した命令列の途中に直接ジャンプ（分岐）します。これにより、ループの開始と終了の条件判定、カウンタのインクリメントといったオーバーヘッドを完全に排除し、CPUの命令パイプラインを最大限に活用できます。

Go言語のコンパイラとリンカ (5g, 5l)

Go言語のツールチェインは、特定のアーキテクチャ向けに設計されたコンパイラとリンカを含んでいます。このコミットで言及されている5gと5lは、それぞれARMアーキテクチャ（Goの内部ではarmまたは5と表記されることが多い）向けのコンパイラとリンカを指します。

  • 5g (Go Compiler for ARM): GoのソースコードをARMアセンブリコードにコンパイルする役割を担います。このコミットでは、メモリのゼロクリアやコピーが必要なGoのコードに対して、Duff's Deviceを利用した新しいアセンブリ命令（ADUFFZERO, ADUFFCOPY）を生成するように変更されています。
  • 5l (Go Linker for ARM): コンパイルされたオブジェクトファイルとランタイムライブラリをリンクし、実行可能なバイナリを生成します。このコミットでは、5lが新しいDuff's Device関連の命令を正しく認識し、リンクできるように変更が加えられています。

ARMアーキテクチャのアセンブリ

ARMアーキテクチャは、モバイルデバイスや組み込みシステムで広く使用されているRISC（Reduced Instruction Set Computer）ベースのCPUアーキテクチャです。Goランタイムのアセンブリコードは、特定のARM命令セットとレジスタの使用規則に従って記述されます。

  • MOVW.P R0, 4(R1): このような命令は、ARMアセンブリにおける「ポストインデックスアドレッシング」を示します。R1が指すアドレスから4バイトオフセットしたメモリ位置にR0の値を書き込み、その後R1レジスタの値を4だけインクリメントします。これは、連続したメモリ領域を効率的に処理する際に非常に有用です。

技術的詳細

このコミットの核となる技術的変更は、Goランタイムがメモリのゼロクリアとコピーを行う際に、Duff's DeviceをARMアセンブリレベルで利用するようにした点です。

  1. 新しいアセンブリ命令の導入: src/cmd/5l/5.out.h に、新しい擬似命令 ADUFFCOPY と ADUFFZERO が追加されています。これらは、コンパイラがDuff's Deviceを利用したメモリ操作を表現するために使用する内部命令です。

  2. ARMアセンブリルーチンの実装 (src/pkg/runtime/asm_arm.s):

    • runtime·duffzero(SB): メモリをゼロクリアするためのDuff's Deviceルーチンです。R0レジスタにはゼロ値が、R1レジスタにはゼロクリア対象のメモリへのポインタが渡されます。このルーチンは、MOVW.P R0, 4(R1) のような命令を多数連続して記述することで、アンロールされたループを形成しています。コンパイラは、ゼロクリアすべきバイト数に応じて、このルーチン内の適切なオフセットにジャンプします。
    • runtime·duffcopy(SB): メモリをコピーするためのDuff's Deviceルーチンです。R0はスクラッチレジスタ、R1はソースメモリへのポインタ、R2はデスティネーションメモリへのポインタとして使用されます。MOVW.P 4(R1), R0 と MOVW.P R0, 4(R2) のペアを多数連続して記述することで、アンロールされたコピー処理を実現しています。同様に、コピーすべきバイト数に応じて、ルーチン内の適切なオフセットにジャンプします。

  3. コンパイラ (src/cmd/5g) の変更:

    • sgen 関数 (src/cmd/5g/cgen.c): メモリコピーを生成する部分が変更され、特定のサイズ（4バイトから128バイト）のコピーに対して ADUFFCOPY 命令を生成するようになりました。これにより、Goのコードで構造体や配列のコピーが行われる際に、Duff's Deviceが利用されるようになります。
    • defframe 関数 (src/cmd/5g/ggen.c): 関数のスタックフレーム初期化時に、ローカル変数のゼロクリアを行う部分が変更されました。特に、zerorange ヘルパー関数が導入され、特定のサイズ（128ワードまで）のゼロクリアに対して ADUFFZERO 命令を生成するようになりました。
    • clearfat 関数 (src/cmd/5g/ggen.c): 大きな構造体や配列のゼロクリアを行う部分が変更され、ADUFFZERO 命令を利用するように修正されました。
    • これらの変更により、コンパイラはGoのコードから、より効率的なDuff's Deviceベースのメモリ操作を生成できるようになります。

  4. リンカ (src/liblink) の変更:

    • src/liblink/asm5.c および src/liblink/obj5.c: 新しい ADUFFCOPY および ADUFFZERO 命令をリンカが認識し、正しく処理できるように変更が加えられています。これらの命令は、通常の関数呼び出し (ABL) と同様に扱われ、特定のオフセットへのジャンプを伴う特殊な命令として処理されます。

  5. レジスタ割り当てと最適化 (src/cmd/5g/peep.c, src/cmd/5g/reg.c):

    • peep.c では、ADUFFZERO と ADUFFCOPY 命令が使用するレジスタ（R0, R1, R2）が、他の最適化（レジスタの置き換えなど）によって誤って変更されないように、特別な処理が追加されています。
    • reg.c では、これらの新しい命令がレジスタ割り当てのロジックに正しく組み込まれるように調整されています。

これらの変更により、Goのコンパイラとランタイムは、ARMアーキテクチャ上でメモリのゼロクリアとコピーをより効率的に実行できるようになり、結果としてGoプログラムのパフォーマンスが向上します。

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

このコミットで変更された主要なファイルと、その変更の目的は以下の通りです。

  • src/cmd/5g/cgen.c:
    • sgen 関数において、特定のサイズのメモリコピー（4バイトから128バイト）に対して、新しく導入された ADUFFCOPY 命令を生成するように変更されました。これにより、Goコンパイラが生成するコピーコードがDuff's Deviceを利用するようになります。
  • src/cmd/5g/ggen.c:
    • defframe 関数において、スタックフレーム上のローカル変数のゼロクリア処理が変更されました。
    • zerorange ヘルパー関数が新しく追加され、特定のサイズのゼロクリアに対して ADUFFZERO 命令を生成するようになりました。
    • clearfat 関数も ADUFFZERO を利用するように修正されました。
  • src/cmd/5g/peep.c:
    • ADUFFZERO と ADUFFCOPY 命令が使用するレジスタ（R0, R1, R2）が、レジスタの置き換え最適化の対象外となるように、特別な処理が追加されました。これは、Duff's Deviceルーチンがこれらのレジスタを特定の目的で使用するため、その整合性を保つために必要です。
  • src/cmd/5g/prog.c:
    • progtable に ADUFFZERO と ADUFFCOPY の情報が追加され、これらの命令が関数呼び出し (Call) として扱われることが定義されました。
  • src/cmd/5g/reg.c:
    • レジスタ割り当てのロジックにおいて、ADUFFZERO と ADUFFCOPY 命令が正しく扱われるように変更が加えられました。
  • src/cmd/5l/5.out.h:
    • 新しい擬似命令 ADUFFCOPY と ADUFFZERO の定義が追加されました。これらはコンパイラとリンカがDuff's Deviceを扱うための内部的な識別子です。
  • src/liblink/asm5.c:
    • リンカが ADUFFZERO と ADUFFCOPY 命令を認識し、通常の関数呼び出し (ABL) と同様に処理できるように、optab と buildop 関数が更新されました。特に、これらの命令が持つオフセット値が、リンク時に正しく処理されるように修正されています。
  • src/liblink/obj5.c:
    • リンカのオブジェクト処理において、ADUFFZERO と ADUFFCOPY 命令が正しく扱われるように変更されました。
  • src/pkg/runtime/asm_arm.s:
    • このコミットの最も重要な変更点です。 runtime·duffzero と runtime·duffcopy という2つの新しいアセンブリルーチンが追加されました。これらは、Duff's Deviceの原理に基づいて、メモリのゼロクリアとコピーを非常に効率的に行うためのアンロールされた命令シーケンスを含んでいます。
  • src/pkg/runtime/memmove_test.go:
    • ベンチマークテストの定義が、[N]byte から [N/4]uint32 に変更されました。これは、Duff's Deviceがワード単位（4バイト）で操作を行うため、その効果をより正確に測定するための調整です。

コアとなるコードの解説

このコミットの核心は、src/pkg/runtime/asm_arm.s に追加された runtime·duffzero と runtime·duffcopy のアセンブリルーチンです。

TEXT runtime·duffzero(SB), NOSPLIT, $0-0

このルーチンはメモリをゼロクリアするために使用されます。

  • R0 レジスタにはゼロ値が格納されていると仮定されます。
  • R1 レジスタにはゼロクリア対象のメモリ領域の開始アドレスが格納されます。
TEXT runtime·duffzero(SB), NOSPLIT, $0-0
    MOVW.P R0, 4(R1)
    MOVW.P R0, 4(R1)
    ... (多数の MOVW.P R0, 4(R1) 命令が続く)
    MOVW.P R0, 4(R1)
    RET
  • MOVW.P R0, 4(R1): この命令は、R1が指すアドレスにR0の値を書き込み（ここではゼロ）、その後R1の値を4バイト（ワードサイズ）だけインクリメントします。.Pサフィックスはポストインデックスアドレッシングを示し、メモリ操作後にベースレジスタが更新されることを意味します。
  • このルーチンは、同じ MOVW.P 命令を多数連続して記述することで、巨大なアンロールされたループを形成しています。
  • コンパイラ (5g) は、ゼロクリアすべきバイト数に応じて、このルーチン内の特定のオフセットにジャンプします。例えば、12バイトをゼロクリアしたい場合、コンパイラはルーチンの先頭から、残りの12バイトを処理するのに必要な命令数だけスキップした位置にジャンプします。これにより、ループのオーバーヘッドなしに、必要な回数だけゼロクリア操作が実行されます。

TEXT runtime·duffcopy(SB), NOSPLIT, $0-0

このルーチンはメモリをコピーするために使用されます。

  • R0 レジスタはスクラッチ（一時使用）レジスタです。
  • R1 レジスタにはソースメモリ領域の開始アドレスが格納されます。
  • R2 レジスタにはデスティネーションメモリ領域の開始アドレスが格納されます。
TEXT runtime·duffcopy(SB), NOSPLIT, $0-0
    MOVW.P 4(R1), R0
    MOVW.P R0, 4(R2)
    MOVW.P 4(R1), R0
    MOVW.P R0, 4(R2)
    ... (多数の MOVW.P 命令ペアが続く)
    MOVW.P 4(R1), R0
    MOVW.P R0, 4(R2)
    RET
  • MOVW.P 4(R1), R0: R1が指すアドレスから4バイトを読み込み、R0に格納し、その後R1を4バイトインクリメントします。
  • MOVW.P R0, 4(R2): R0の値をR2が指すアドレスに書き込み、その後R2を4バイトインクリメントします。
  • これらの命令ペアが多数連続して記述され、アンロールされたコピー処理を形成しています。
  • duffzero と同様に、コンパイラはコピーすべきバイト数に応じて、このルーチン内の適切なオフセットにジャンプします。これにより、効率的なメモリコピーが実現されます。

これらのアセンブリルーチンは、Goコンパイラが生成するコードと密接に連携しており、Go言語の抽象的なメモリ操作が、低レベルで非常に最適化されたアセンブリ命令に変換されることを可能にしています。

関連リンク

参考にした情報源リンク

  • Duff's device - Wikipedia: (Web検索結果より)
  • Go runtime source code (specifically src/pkg/runtime/asm_arm.s, src/cmd/5g/ggen.c, src/cmd/5g/cgen.c): (Web検索結果より)
  • Go issue tracker: (Web検索結果より)
  • Various articles and discussions on Duff's device and Go runtime optimizations: (Web検索結果より)