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

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

このコミットは、Go言語のランタイムにおけるARMアーキテクチャ上での符号なし整数除算（div）および剰余（mod）演算のパフォーマンスを大幅に改善するものです。具体的には、これらの演算が約3.7倍高速化され、ベンチマークでは最大77%以上の性能向上が確認されています。この最適化は、src/pkg/runtime/vlop_arm.sというARMアセンブリ言語で記述されたファイルに対して行われました。

コミット

commit 3e3fa7b5f17fd57e9890cd823d39add271c77d9c
Author: Shenghou Ma <minux.ma@gmail.com>
Date:   Sat Oct 20 16:40:19 2012 +0800

    runtime: ~3.7x speed up of div/mod on ARM
    benchmark                      old ns/op    new ns/op    delta
    BenchmarkUint32Div7                  281           75  -73.06%
    BenchmarkUint32Div37                 281           75  -73.02%
    BenchmarkUint32Div123                281           75  -73.02%
    BenchmarkUint32Div763                280           75  -72.89%
    BenchmarkUint32Div1247               280           75  -72.93%
    BenchmarkUint32Div9305               281           75  -73.02%
    BenchmarkUint32Div13307              281           75  -73.06%
    BenchmarkUint32Div52513              281           75  -72.99%
    BenchmarkUint32Div60978747           281           63  -77.33%
    BenchmarkUint32Div106956295          280           63  -77.21%
    BenchmarkUint32Mod7                  280           77  -72.21%
    BenchmarkUint32Mod37                 280           77  -72.18%
    BenchmarkUint32Mod123                280           77  -72.25%
    BenchmarkUint32Mod763                280           77  -72.18%
    BenchmarkUint32Mod1247               280           77  -72.21%
    BenchmarkUint32Mod9305               280           77  -72.21%
    BenchmarkUint32Mod13307              280           77  -72.25%
    BenchmarkUint32Mod52513              280           77  -72.18%
    BenchmarkUint32Mod60978747           280           63  -77.25%
    BenchmarkUint32Mod106956295          280           63  -77.21%
    
    R=dave, rsc
    CC=dave, golang-dev, rsc
    https://golang.org/cl/6717043

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

https://github.com/golang/go/commit/3e3fa7b5f17fd57e9890cd823d39add271c77d9c

元コミット内容

このコミットは、Go言語のランタイムにおけるARMアーキテクチャでのdiv（除算）とmod（剰余）演算の性能を約3.7倍向上させることを目的としています。コミットメッセージには、BenchmarkUint32DivおよびBenchmarkUint32Modのベンチマーク結果が示されており、いずれのテストケースでも実行時間が大幅に短縮され、最大で77.33%の改善が見られます。

変更の背景

Go言語は、様々なアーキテクチャで動作するように設計されています。ARMアーキテクチャは、モバイルデバイスや組み込みシステムで広く利用されており、その性能はGoアプリケーションの全体的な実行速度に大きく影響します。特に、除算や剰余といった基本的な算術演算は、多くのプログラムで頻繁に使用されるため、これらの演算が遅いとアプリケーション全体のボトルネックとなる可能性があります。

このコミットが行われた2012年当時、ARMプロセッサにはハードウェアによる高速な整数除算命令が標準で搭載されていないことが一般的でした（ARMv7-A以降の一部のプロセッサではUDIV/SDIV命令が導入されましたが、それ以前のアーキテクチャではソフトウェアによる実装が必要でした）。そのため、Goのランタイムは、これらの演算をソフトウェアでエミュレートする必要がありました。従来のソフトウェア実装は効率が悪く、パフォーマンス上の課題となっていました。

このコミットは、ARMアーキテクチャ上でのGoプログラムの実行速度を向上させ、特に数値計算を多用するアプリケーションや、リソースが限られた環境でのパフォーマンスを改善することを目的としています。

前提知識の解説

ARMアセンブリ言語

ARMアセンブリ言語は、ARMアーキテクチャのプロセッサが直接実行できる機械語命令を人間が読める形式で記述したものです。レジスタ、メモリ操作、分岐、算術演算など、プロセッサの低レベルな動作を直接制御します。Go言語のランタイムは、パフォーマンスが重要な部分や、特定のハードウェア機能にアクセスする必要がある部分でアセンブリ言語を使用します。

整数除算アルゴリズム

コンピュータにおける整数除算は、単純な引き算の繰り返しから、より複雑なアルゴリズムまで様々です。ハードウェアによる除算命令がない場合、ソフトウェアで除算を実装する必要があります。一般的なソフトウェア除算アルゴリズムには以下のようなものがあります。

  • 引き算の繰り返し: 最も単純な方法で、除数で被除数を繰り返し引き、引けた回数を商とする。非常に遅い。
  • シフトと引き算: 被除数をシフトしながら除数を引いていく方法。手計算の筆算に似ている。
  • 乗算による逆数近似 (Newton-Raphson法): 除算を乗算と近似の繰り返しで実現する方法。除数の逆数を近似的に求め、それを被除数に乗じることで商を得る。高速だが、浮動小数点演算や反復計算が必要となる。

このコミットでは、特に後者の「乗算による逆数近似」が採用されており、これは高性能な除算アルゴリズムとして知られています。

ニュートン・ラプソン法 (Newton-Raphson Method)

ニュートン・ラプソン法は、方程式の根を数値的に求めるための反復法です。除算の文脈では、1/D（除数Dの逆数）を求めるために利用されます。f(x) = 1/x - D の根を求めることで 1/D を計算します。この方法は、初期値が適切であれば急速に収束し、高い精度で逆数を求めることができます。逆数が求まれば、N / D = N * (1/D) のように乗算に変換して除算を実行できます。

Go言語のランタイム

Go言語のランタイムは、ガベージコレクション、スケジューラ、プリミティブな型操作など、Goプログラムの実行をサポートする低レベルなコードの集合体です。src/pkg/runtime/ディレクトリには、Goプログラムが動作するために必要なアセンブリ言語やC言語で書かれたコードが含まれています。vlop_arm.sのようなファイルは、特定のアーキテクチャ（この場合はARM）に特化した最適化されたルーチンを提供します。

技術的詳細

このコミットの主要な技術的改善点は、ARMアセンブリ言語で記述された符号なし整数除算ルーチン udiv の実装を、従来のビットシフトと引き算に基づく方法から、ニュートン・ラプソン法に基づく乗算による逆数近似に切り替えたことです。

従来の除算ルーチンは、div<>(SB)という関数で実装されており、これはビットシフトと条件付き引き算を繰り返す古典的なアルゴリズムでした。これは直感的ですが、各ビットを処理するために多くのサイクルを必要とし、特に32ビット整数では32回の反復が必要となるため、効率が悪いという問題がありました。

新しい udiv<>(SB) 関数は、以下のステップで除算を高速化しています。

  1. 正規化シフトの計算 (CLZ): CLZ (Count Leading Zeros) 命令を使用して、除数 d の最上位ビットの位置を特定し、正規化のためのシフト量 s を計算します。これにより、除数を特定の範囲に正規化し、逆数近似の精度と収束速度を向上させます。
  2. 逆数近似の初期値の取得: fast_udiv_tab というルックアップテーブルを使用し、正規化された除数の上位数ビットに基づいて逆数近似の初期値を取得します。このテーブルは、事前に計算された逆数の近似値をバイト単位で格納しており、効率的な初期値を提供します。
  3. ニュートン・ラプソン反復: 取得した初期値を用いて、2回のニュートン・ラプソン反復を実行します。これにより、除数の逆数 1/d の高精度な近似値 q を効率的に計算します。
    • MUL.PL, MULAWT, MULAL.NE などの乗算命令を駆使して、q = q - q * (q * d - 1) のような形式の反復計算を行います。
    • ARMプロセッサの乗算命令は、従来のシフトと引き算よりもはるかに高速です。
  4. 剰余の計算と調整: 逆数近似によって得られた商 q を使用して、剰余 r = n - q * d を計算します。ニュートン・ラプソン法による近似商は、実際の商とわずかに異なる場合があるため、剰余が 0 <= r < d の範囲に収まるように、必要に応じて商と剰余を微調整します。これには、CMN (Compare Negative) や ADD.CS (Add if Carry Set) などの条件付き命令が使用されます。
  5. 符号付き除算/剰余への対応: _div, _mod 関数は、符号なし除算ルーチン udiv を呼び出す前に、被除数と除数の符号を調整し、結果の符号を適切に処理することで、符号付き整数除算/剰余を実現しています。これにより、符号付きと符号なしの両方の演算で高速化の恩恵を受けられます。

この最適化により、特にARMv5やARMv6のようなハードウェア除算命令を持たないARMプロセッサにおいて、Goプログラムの算術演算性能が劇的に向上しました。

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

変更は src/pkg/runtime/vlop_arm.s ファイルに集中しています。

  • 削除されたコード: 従来の非効率な save<>, rest<>, div<>, _div, _mod, _divu, _modu 関数が削除されました。これらは、ビットシフトと引き算に基づく除算アルゴリズムを実装していました。
  • 追加されたコード:
    • 新しい符号なし除算ルーチン udiv<>(SB) が追加されました。これがニュートン・ラプソン法に基づく高速な除算アルゴリズムの本体です。
    • fast_udiv_tab というルックアップテーブルが追加されました。これは、逆数近似の初期値を効率的に取得するために使用されます。
    • 新しい _divu, _modu, _div, _mod 関数が追加されました。これらは、udiv<>(SB) を呼び出して実際の除算/剰余を行い、結果を適切に処理します。

具体的には、122行が削除され、185行が追加されており、コードの大部分が書き換えられています。

コアとなるコードの解説

udiv<>(SB) 関数

この関数は、符号なし32ビット整数 n を d で除算し、商 q と剰余 r を返します。

// func udiv(n, d uint32) (q, r uint32)
// Reference: 
// Sloss, Andrew et. al; ARM System Developer's Guide: Designing and Optimizing System Software
// Morgan Kaufmann; 1 edition (April 8, 2004), ISBN 978-1558608740
q = 0 // input d, output q
r = 1 // input n, output r
s = 2 // three temporary variables
m = 3
a = 11
// Please be careful when changing this, it is pretty fragile:
// 1, don't use unconditional branch as the linker is free to reorder the blocks;
// 2. if a == 11, beware that the linker will use R11 if you use certain instructions.
TEXT udiv<>(SB),7,$-4
    CLZ     R(q), R(s) // find normalizing shift
    MOVW.S  R(q)<<R(s), R(a)
    ADD     R(a)>>25, PC, R(a) // most significant 7 bits of divisor
    MOVBU.NE        (4*36-64)(R(a)), R(a) // 36 == number of inst. between fast_udiv_tab and begin

begin:
    SUB.S   $7, R(s)
    RSB     $0, R(q), R(m) // m = -q
    MOVW.PL R(a)<<R(s), R(q)

    // 1st Newton iteration
    MUL.PL  R(m), R(q), R(a) // a = -q*d
    BMI     udiv_by_large_d
    MULAWT  R(a), R(q), R(q), R(q) // q approx q-(q*q*d>>32)
    TEQ     R(m)->1, R(m) // check for d=0 or d=1

    // 2nd Newton iteration
    MUL.NE  R(m), R(q), R(a)
    MOVW.NE $0, R(s)
    MULAL.NE R(q), R(a), (R(q),R(s))
    BEQ     udiv_by_0_or_1

    // q now accurate enough for a remainder r, 0<=r<3*d
    MULLU   R(q), R(r), (R(q),R(s)) // q = (r * q) >> 32    
    ADD     R(m), R(r), R(r) // r = n - d
    MULA    R(m), R(q), R(r), R(r) // r = n - (q+1)*d

    // since 0 <= n-q*d < 3*d; thus -d <= r < 2*d
    CMN     R(m), R(r) // t = r-d
    SUB.CS  R(m), R(r), R(r) // if (t<-d || t>=0) r=r+d
    ADD.CC  $1, R(q)
    ADD.PL  R(m)<<1, R(r)
    ADD.PL  $2, R(q)

    // return, can't use RET here or fast_udiv_tab will be dropped during linking
    MOVW    R14, R15

udiv_by_large_d:
    // ... (large divisor specific handling)

udiv_by_0_or_1:
    // ... (d=0 or d=1 specific handling)

fast_udiv_tab:
    // var tab [64]byte
    // tab[0] = 255; for i := 1; i <= 63; i++ { tab[i] = (1<<14)/(64+i) }
    // laid out here as little-endian uint32s
    WORD $0xf4f8fcff
    // ... (rest of the table)
  • レジスタ割り当て: q, r, s, m, a はそれぞれARMレジスタに割り当てられています。q は除数 d の入力と商 q の出力、r は被除数 n の入力と剰余 r の出力に使用されます。
  • CLZ (Count Leading Zeros): 除数 d の先頭のゼロの数を数え、正規化のためのシフト量 s を決定します。これにより、除数を特定の範囲にスケーリングし、逆数近似の精度を高めます。
  • fast_udiv_tab: これは、除数の上位ビットに基づいて逆数近似の初期値をルックアップするためのテーブルです。事前に計算された値が格納されており、効率的な初期値を提供します。
  • ニュートン・ラプソン反復: MUL.PL, MULAWT, MULAL.NE などのARMの乗算命令を効率的に使用して、除数の逆数を反復的に近似します。これにより、従来のビットシフトと引き算よりもはるかに少ないサイクルで高精度な商を得ることができます。
  • 剰余の調整: ニュートン・ラプソン法は近似であるため、計算された商と剰余が正確な範囲に収まるように、CMN, SUB.CS, ADD.CC, ADD.PL などの条件付き命令を使って微調整を行います。これにより、0 <= r < d の条件を満たす正確な剰余が保証されます。
  • 特殊ケースのハンドリング: udiv_by_large_d や udiv_by_0_or_1 のようなラベルは、除数が非常に大きい場合や、0または1の場合の特殊な処理を示しています。これにより、アルゴリズムの堅牢性が向上します。

_divu, _modu, _div, _mod 関数

これらの関数は、Go言語のランタイムが呼び出すエントリポイントであり、実際の除算/剰余演算のために udiv<>(SB) を呼び出します。

  • _divu(SB) (符号なし除算): 被除数と除数をレジスタにロードし、udiv<>(SB) を呼び出して商を計算し、結果を返します。
  • _modu(SB) (符号なし剰余): 同様に udiv<>(SB) を呼び出し、計算された剰余を返します。
  • _div(SB) (符号付き除算): 被除数と除数の符号をチェックし、必要に応じて絶対値に変換してから udiv<>(SB) を呼び出します。その後、元の符号に基づいて結果の商の符号を調整します。
  • _mod(SB) (符号付き剰余): 被除数と除数の符号をチェックし、絶対値に変換してから udiv<>(SB) を呼び出します。その後、元の被除数の符号に基づいて結果の剰余の符号を調整します。

これらのラッパー関数により、Go言語のコードからは通常の除算/剰余演算として呼び出すことができ、内部で最適化されたアセンブリルーチンが透過的に使用されます。

関連リンク

参考にした情報源リンク

  • Sloss, Andrew et. al; ARM System Developer's Guide: Designing and Optimizing System Software; Morgan Kaufmann; 1 edition (April 8, 2004), ISBN 978-1558608740
    • この書籍は、ARMアーキテクチャにおけるシステムソフトウェアの設計と最適化に関する詳細な情報を提供しており、特に低レベルな算術演算の最適化手法について言及されていると考えられます。このコミットの udiv 関数のコメントにも明記されており、実装の基盤となった重要な情報源です。