6.5.5 Two-stage integer division

(Two-stage integer divison;2段階除算)ほとんどのハードウェアでは、 乗算は除算よりも大幅に高速です。 したがって、 多くの数値を同じ除数(割る数)で除算する必要がある場合は、 通常、 除数の逆数を一度求めて、 その逆数を数値に乗算する方が高速です。 整数の場合、 これは技巧的になってしまうため、 Gforth ではこの作業をこのセクションで説明するワード群にパッケージ化しています。

以下の例から始めるとしましょう。 あなたがセルの配列のすべての要素を同じ数値 n で除算したいとします。 これを素直に実装すると以下のようになります:

: array/ ( addr u n -- )
  -rot cells bounds u+do
    i @ over / i !
  1 cells +loop
  drop ;

より効率的なバージョンは以下のようになります:

: array/ ( addr u n -- )
  {: | reci[ staged/-size ] :}
  reci[ /f-stage1m
  cells bounds u+do
    i @ reci[ /f-stage2m i !
  1 cells +loop ;

この例では、 まず、 逆数データを格納するためのサイズ staged/-size のローカル・バッファー reci[ を作成します。 次に、 /f-stage1m は n の逆数を計算し、 reci[ に格納します。 最後に、 ループ内で /f-stage2m が reci[ のデータを使用して除算の商を計算します。

これにはいくつかの制限があります。 /f-stage1m では正の除数のみがサポートされます。 u/-stage1m には 2 以上の数を使用できます。 サポートされていない除数を使用しようとすると、 エラーが発生します。 floored 第2ステージ・ワードの相互(reciprocal)バッファーは /f-stage1m で初期化し、 符号な無しの第2ステージ・ワードの相互バッファーは u/-stage1m で初期化する必要があります。 最初のステージと2番目のステージの間で相互バッファーを変更してはなりません。 基本的に、 これはメモリ・バッファーとして扱うのではなく、 最初のステージでのみ変更可能なものとして扱います。 このルールのポイントは、 Gforth の将来のバージョンではこのバッファーのエイリアスが考慮されないということです。

これらのワードが以下です:

staged/-size ( – u  ) gforth-1.0 “staged-slash-size”

u/-stage1m または /f-stage1m のバッファーのサイズ。

/f-stage1m ( n addr-reci –  ) gforth-1.0 “slash-f-stage1m”

n の逆数を計算し、 サイズ staged/-size のバッファー addr-reci に格納します。 n<1 の場合、 エラーを出します(throw)。

/f-stage2m ( n1 a-reci – nquotient ) gforth-1.0 “slash-f-stage2m”

Nquotient は、n1 を a-reci で表される除数で除算した結果であり、 /f-stage1m によって計算されます。

modf-stage2m ( n1 a-reci – umodulus ) gforth-1.0 “mod-f-stage2m”

Umodulus は、 n1 を a-reci で表される除数で割った余り(remainder)で、 /f-stage1m によって計算されます。

/modf-stage2m ( n1 a-reci – umodulus nquotient ) gforth-1.0 “slash-mod-f-stage2m”

Nquotient は商で、 umodulus は n1 を a-reci で表される除数で割った余り(remainder)で、 /f-stage1m によって計算されます。

u/-stage1m ( u addr-reci –  ) gforth-1.0 “u-slash-stage1m”

u の逆数を計算し、 サイズ staged/-size のバッファー addr-reci に格納します。 u<2 の場合、 エラーを出します(throw)。

u/-stage2m ( u1 a-reci – uquotient ) gforth-1.0 “u-slash-stage2m”

Uquotient は、 u1 を a-reci で表される除数で除算した結果であり、 u/-stage1m によって計算されます。

umod-stage2m ( u1 a-reci – umodulus ) gforth-1.0 “u-mod-stage2m”

Umodulus は、 u1 を a-reci で表される除数で割った余り(remainder)で、u/-stage1m によって計算されます。

u/mod-stage2m ( u1 a-reci – umodulus uquotient ) gforth-1.0 “u-slash-mod-stage2m”

Uquotient は商で、 umodulus は a-reci で表される除数で u1 を割った余り(remainder)で、u/-stage1m によって計算されます。

Gforth は現在、 段階的対称除算(staged symmetrical division)をサポートしていません。

staged/-divisor @ を使用すると、 逆数(のアドレス)から除数を復旧(recover)できます:

staged/-divisor ( addr1 – addr2  ) gforth-1.0 “staged-slash-divisor”

Addr1 は逆数のアドレス、 addr2 は逆数の計算元となった除数を含むアドレスです。

これは、Gforth の逆コンパイラ出力を確認するときに役立ちます。 定数による除算は、 多くの場合、 逆数のアドレスとその後に続く第2ステージ・ワードを含むリテラルにコンパイルされます。

これらのワードを使用した場合のパフォーマンスへの影響は、 アーキテクチャ(ハードウェア除算があるかどうか)と、 特定の実装(ハードウェア除算の速さはどれくらいか)に大きく依存しますが、 これらのワードの相対的なパフォーマンスについてのアイデアを提供するために、 以下を示します。 2 つの AMD64 実装でのマイクロ・ベンチマークの反復ごとのサイクルを以下に示します。 norm 列は通常の除算ワード(例: u/)を示し、stg2 列は対応する stage2 ワード(例: u/-stage2m)を示します:

intel Skylake       AMD Zen2
norm stg2           norm stg2
41.3 15.8 u/        35.2 21.4 u/
39.8 19.7 umod      36.9 25.8 umod
44.0 25.3 u/mod     43.0 33.9 u/mod
48.7 16.9 /f        36.2 22.5 /f
47.9 20.5 modf      37.9 27.1 modf
53.0 24.6 /modf     45.8 35.4 /modf
    227.2 u/stage1      101.9 u/stage1
    159.8 /fstage1       97.7 /fstage1