リンクフリーを近日中にとりやめる予定です

すでにリンクを貼っていただいている方、ご一報頂きたくお願い申し上げます。


ごく少数ですが、リンクをお断りする場合があります



ブログ内 風景光景カテゴリー

続編記事などをご希望の方は こちらへどうぞ

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

[未掲載分] 「除算が遅い」の補足 (2)

今回も「除算が遅い」、「除算の高速化」などのキーワードで検索サイトからお越しいただいている方々への対応記事となります。

前話で、
・除算そのもの以外にも速度低下の要因が含まれていないか?
・除算を行う近辺の贅肉をそぎ落とせないだろうか
といった点を触れました。
除数が定数ならば、さらに高速化を狙えます。前話が長くなったため後回とした分を・・・


お知らせ
活動休止にともない、この記事を事前に予約投稿してあります。
トップ記事の固定を目的としています


※ これを下書きしたのは2012年夏の終わり頃です。
ご覧いただいている時期によっては状況が異なっている可能性があります。
下書きした頃の環境は、OS - Microsoft Windows 7、開発環境 - Visual Studio 2008 , C/C++ 言語。

前回の続きに入る前に、

分数でいうところの分子は numerator もしくは fraction 、分母は denominator の 単語が該当。よって、x = n ÷ d や x = n / d と記したいところです。ここでは話を簡単に進めるため A = B ÷ C



と表現します。それぞれ、

A 演算結果、商。
B 被除数、割られるほうの数。
C 除数、割るほうの数。

さて、過去記事除算が遅いにおいて、浮動小数点演算ならば
・分母が定数ならば「割り算」を「逆数の掛け算」に置き換えると良い
と述べた。今回は想定しているのは整数の除算。

整数の除算において除数が固定できる場合、除算命令を使わずに済ますことが可能。結論を急いでしまえば、
・定数の乗算 ( 掛け算 ) と シフトに置き換える
ことができる。厳密にいえば、符号なし整数と符号付き整数で異なるのだが、話を簡単にするため符号なし整数を基に話を進めよう。

A = B ÷ 10 を求めたいとする ( ただし、A , B , C それぞれが32ビット幅に収まる数値 )。
16進数 0xcccccccd を掛けて、35ビット分右方向にシフトした値と一致する。

「シフト」や「ビット」や「バイト」について苦手なヒトは過去記事遅くない除算をご参照あれ。



右方向にシフトとは下方向にシフトすること。1ビット分右シフトすることは「÷ 2」と同じ、逆に1ビット分左シフトすることは「×2」と同等。



少し機械寄りな話、前回記したことと重複する。
32ビット版のOS上でも64ビット版のOS上でも32ビット版アプリを動かしている場合、ひとつのレジスタ ( 演算器 ) の幅は32ビット。
B と 0xcccccccd を掛けた値は32ビット幅に収まりきらない可能性も生じ、正しい結果を得るには64ビット分の幅が必要。
通常、乗算命令の結果は上位32ビット分が EDX レジスタ、下位32ビット分は EAX レジスタに格納される。
ということで、乗算命令の結果のうちEDX レジスタを3ビット分右にシフトした値と「B ÷ 10」が一致する。

64ビット版のOS上で64ビット版アプリを動かしている場合、ひとつのレジスタ ( 演算器 ) の幅は64ビット。
「B × 0xcccccccd」の結果もひとつのレジスタに収まり、32ビット以上のシフト操作も容易・・・

参考までに
「÷ 100」は 0x51eb851f で掛けて、37ビット右シフト、
「÷ 1000」は 0x10624dd3 で掛けて、38ビット右シフト、
「÷10000」は 0xd1b71759 で掛けて、45ビット右シフト・・・

ほかにも、○○で掛けて△△ビットシフトするの組み合わせは多数。

さすがに覚えきれないし、表計算では縦方向に制限がある。



印刷して持ち歩くのも大変なので、アプリを自作した・・・



例えば、除数を「44100」と入力すれば、0xbe37c63bで掛けて、47ビット右シフトといった具合・・・



さてさて、「除算」を「乗算とシフト」に切り替えることでどれ位の効果を期待できるのだろう。
これを書いている時点で出回っている CPU の傾向を載せる。それぞれ、CPU 名、除算に要するクロック数 ( 待ち時間 )、乗算に要するクロック数、シフトに要するクロック数は概ね以下の通り。

CPU除算乗算シフト
Core i72542
Core 2 duo4051
Pentium480111

大雑把に言えば、待ち時間が60分から10分前後へと縮まるイメージ。
細かく言えば、このクロック数は前後のメモリアクセス等を無視している。前後のメモリアクセス ( ロード / ストア) や他の命令との絡みで状況も変わる・・・

・・・とここまでの流れでは
除算を高速に処理したい部分を「乗算とシフト」に置き換えることを推奨していると思われるかも。実際のところ、
コンパイラの賢さに依存
する。例えば、C/C++ 言語 で「A = B ÷ C」のままコードを書いたとしよう。

64ビット向けアプリにビルドした場合、ほどよく「乗算とシフト」に変換された実行コードが生成される。しかし、同じソースコードを32ビット向けアプリとしてビルドした場合、除算命令や __aulldiv を呼び出すようなコードが生成されてしまう。

個人的な感触では除数が一定の数値までは「乗算とシフト」が生成される。もしかしたら、「ここは速度重視ではないので、除算命令を生成しよう」とコンパイラが判断した可能性も否定できない。詳しくは両方をビルド後にアセンブリ言語の出力ファイルを比較すれば良い・・・

高速さを求める部分で「A = B ÷ C」ではなく、「○○で掛けて△△ビットシフトする」のコードを意図的に書くのは「除算命令を生成させない」という意味で有効。以下の点も頭に入れておきたい。

・コンパイラのバージョンアップにともない改善されてゆく。
・将来的には、除算の待ち時間がさらに短くなるよう、ハードウェア面で改良されてゆく。
・保守する際に複雑。
とくに多人数で作成に携っている場合、トリッキーなコードはトラブルのもと。オリジナルコードとなぜこのコードに置き換えたのか等のコメントを忘れないようにしたいものだ・・・

ではでは、除数 ( A = B ÷ C の C の値) がランダムな場合でも
「乗算とシフト」のテーブルを埋め込んでおくことで高速化できるのでは?
ちょっとビミョー。除数の範囲が狭いならば高速化を期待できそう。テーブルがキャッシュメモリに収まるか否かで速度が格段に違ってくる。

乗数とシフトカウントは4バイト + 1 バイトでパックできる。一般的な PC の構造を考慮した場合、4バイトの倍数にデータが整列配置されていないとメモリから値を読み取る時に遅延が生じる ( 可能性がある ) 。
とすれば、「乗数とシフト」ひとつの組み合わせで8バイト。ちなみに、これを書いている時点で、一般的な PC の L1キャッシュは 32768バイト。ということは、32768÷8で
4096通りまでは L1 キャッシュに収まるので高速化を狙える???

現行の一般的な OS は複数のタスクを切り替えて実行している。人間から見れば、ワープロや表計算や Web ブラウザーを複数同時に実行しているように感じるのだが、ごく短い時間毎に切り替えている。
ほかのアプリに切り替わる際、たいていL1 キャッシュの内容が変更されてしまう。おそらく、再び実行の順番が巡ってきた際、L1キャッシュに残っていないなら L2 キャッシュなどから読み直す。さらに L2キャッシュにもデータがなければ・・・

Core i7 以降はメモリアクセスが改善されています。メモリからのロードを含めても、除算命令を遂行するより待ち時間を短縮できるかもしれません・・・

続きは後日。

本日も最後までご覧いただきありがとうございます。

「つまらなかった」「判り辛った」という方もご遠慮なくコメント欄へどうぞ

テーマ : プログラミング
ジャンル : コンピュータ

コメントの投稿

非公開コメント

承認待ちコメント

08/06(木)

このコメントは管理者の承認待ちです
検索サイトからお越しの方へ
検索サイトからお越しの方は、ブラウザのアドレス欄vitalaboloveおよび、fc2.comが含まれているかご確認ください。
含まれていない場合、偽サイトを閲覧なされている可能性があります。

偽サイトは、当ブログの文字部分や画像部分が有害サイトへのバナーと置き換わっているようです。
プロフィール

Author:Vitalabolove
ご訪問ありがとうございます。
店長を任されておりますVitalaboloveです。

コメントはお気軽に。
今のところリンクフリーですが、あと数日でとりやめます。

画像データ、文言の引用は事前連絡くださるようお願い申し上げます。事前連絡の際は、左下、メールフォームを経由をご利用ください。

最新記事
カレンダー
05 | 2017/06 | 07
- - - - 1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 -
カテゴリ
ランキング
いつも応援いただきありがとうございました。ただいま休養中につきランキングへ参加していません・・・

フリーエリア
内緒話などはおきてがみをご利用ください。
月別アーカイブ
メールフォーム
掲載された記事について、ご不明な点はここからお問い合わせください

名前:
メール:
件名:
本文:

最新コメント
最新トラックバック
スパムと思われるトラックバックは削除しました
QRコード
QR
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。