(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