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

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


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



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

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

スポンサーサイト

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

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

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

前話
・整数の除算ならば、「乗算とシフト」に置き換えると良いと述べた。また、過去記事除算が遅いで取り上げたように
・浮動小数点の除算ならば、「逆数の掛け算」に置き換えると良い。

前話前々話で想定していたのは、整数の除算で商を求めるケースである。高速化のために除算命令を避けたい旨で綴った。実際には、商ではなく余り ( 剰余 ) を求めたい場面もある。
除算命令を用いるならば



EAX レジスタに 商、EDX レジスタに 余りが入る。

検索サイトからお越しいただいた方の中には
除算命令を直接発行せずに余りを求めるにはどうしたら良いだろう!?!?
と疑問を抱くヒトもいるかもしれない。余りの求め方は難しい話ではないので省いてしまった。

A = B ÷ C を基に考えるとしよう。



余り = B - ( A × C ) となる。



おそらく、A = B ÷ C の演算直後であれば A と C の値はレジスタ ( 演算器 ) に残っているハズ。
商を求めるには乗算とシフト、余りを求めるには乗算と減算。おおむね、加算や減算およびシフトは 1クロック、乗算は3 ~ 5 クロック。よって、全てのクロック数を足しても除算命令を1回行うよりもはるかに速い。
しかし、レジスタに空きが無い場合、一旦、演算結果をメモリ上にストア、ロードしなおすなどロスが生じてしまう・・・


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


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

まず、頭に入れておきたいのはCPU に近いほどデータのアクセスが高速になる点。
データへのアクセスが速い順に挙げるとレジスタ内の数値、メモリ上の数値データ、ディスク上のデータ・・・となる。メモリを CPU に直結されたキャッシュメモリとソケットに装着するメインメモリと分けた場合、前者のアクセスは、後者よりも高速。

大雑把な言い方だが、レジスタの空き状況は実行環境ごとに異なる。64ビット版アプリは、32ビット版に比べレジスタ数に余裕がある

自動車でエンジンに該当するのは、PC の中で CPU と呼ばれている。これを書いている時点では Core i7 や Atom 、Core 2 Duo などが搭載されている。これらはIntel の i386 ( 80386 ) の流れを汲むCPU。
i386 の中で一般的な計算 ( 整数の四則演算 ) を担当するのがEAX , EBX , ECX , EDX と呼ばれる4本のレジスタ ( 演算器 ) 。ほか、ESI と EDI などのレジスタもあるが、これらはロード、ストアつまり読み出しや書き込みの場所を指す役割を担っていた。

EAX や EBX と書いたところでイメージし難いかもしれない。レジスタの幅を図で表すと以下の通り。



上の図は右側を軸とし、左方向へいくほどビット幅が広がることを意図している。

i386 の祖先は8086 や 80286 等の16ビット版のプロセッサ。それらの CPU には AX , BX , CX , DX と名前を持つ16ビット幅のレジスタが計4本備わっている。それぞれのレジスタはある程度役割が決まっていて、AX は 演算、CX は繰り返し処理の残り回数、AX と DX を組み合わせて 32ビット幅の数を扱うなどなど。

i386 はそれら16ビット版 CPUと互換性を保ちながら拡張が施された。各レジスタの数値幅は上位16ビット分拡張され、ひとつのレジスタで32ビット幅の数を扱えるようになった。
それぞれのレジスタの頭に「E」が付く。図にあるとおり、EAX レジスタの下位16ビット分が従来の AX レジスタを兼ねている。例えば「E」を付けずに「AX」と指定して書くことで16ビット幅の数値を扱うことも可能。
他方、レジスタの本数は 16ビット版 CPU と同じまま、つまり増えていない。

個人的には、32ビット版 CPU とともに扱えるレジスタ数が増えるだろうと期待していた。同じ頃の対抗 CPU を見ると、8 から 32 本のレジスタを備えた製品が登場していた。おそらく、設計・開発の段階で深い検討の末、増やさないことに決定したのであろう。

仮にレジスタが増設されたとして、消費電力が増加するだけではない。当時、マルチタスクの OS が普及することが予想されていた。ひとつの OS 上で複数のアプリを同時実行が提唱されていた。
それまではシングルタスクが主流で、ワープロや表計算ごとに別々の PC を用意していた。もちろん、一台の PC でフロッピーを入れ替えて電源を入れなおすことで別のアプリを起動することも可能であった。しかし、昨今の PC に比べ起動に時間がかかり、限られた時間の中で作業を進めるには複数台用意したほうが効率的であった・・・

人間から見て、ひとつのデスクトップでワープロや表計算やWebブラウジングを同時に実行しているように感じるヒトも多いハズ。PC の中では、ごく短い時間でそれぞれのアプリの実行を切り替えているのだ。ほかのアプリに切り替わる際、現状のレジスタ内容をどこかに保存する。実行する順番が来たアプリは、以前保存した内容を読み出し( 同じ状況に戻し )、続きを遂行する。同時に立ち上げるアプリが増えるほど、レジスタの本数に応じたメモリが必要となる。現在と比べメモリは高価であった。

簡単にいえば、、作業員を増やすほど、ロッカーや作業机その他諸々も増す必要が生じコスト増加につながる。

つづいて、昨今の64ビット対応 CPU のレジスタは以下の図のよう。



例えば、EAX レジスタの 上位 32ビット分が拡張された。64ビット幅のレジスタを RAX と呼ぶ。こちらも互換性を重視した拡張である。RAX の下位 32ビットを従来の32ビット幅レジスタの EAX として使うこともできる。また、その下 16ビット分も同様。

64ビットに拡張された際、以前 ( 16ビットから32ビットへの拡張 ) と異なる点は利用できるレジスタの本数が増えたこと。汎用レジスタは R8 から R15 の 8本 が追加された。
省電力の技術が向上したのに加え、メモリも安価になり、大容量のメモリが搭載されるようになってきた。

レジスタ数に余裕がある
ということは演算結果を一旦メモリ上に保存したり、読み込み直す可能性が減る。ロードとストアの回数が増えるほど高速化から遠ざかる。したがって、高速化したい箇所でレジスタ数が足りているか否かをチェックすると良い。

乗算や加算、減算、シフトでレジスタを使うほか、
・どこのメモリ ( 値 )を読み出すか
・演算結果をどこに格納するか
・ループカウンタ、つまり、繰り返し処理を残り何回行う?
などでもレジスタが必要・・・

i386 の流れを汲むCPU の仕様を見るかぎり、32ビット版アプリで自由に使える汎用レジスタは8本、64ビット版アプリでは16本となっている。が、そのうち2本はスタックポインタとなっていて自由に使えない。スタックポインタの値を変更することはアプリの暴走に繋がる・・・

手段としては、アプリをビルドする際にアセンブリ言語ファイルの出力を行い、
「レジスタ不足を補うための退避や復元命令が含まれていないか???」をチェックする。

※ アプリをビルドする際、アセンブリ言語ファイルを出力する方法は車輪の再発明 (7)で触れています。



ファイルの出力方法は何通りかの選択肢がある。その中で
「アセンブリコード」「コンピュータ語コード」「ソースコード」を選択すれば、C/C++ 言語のソースコードがどのようなコンピュータ語に翻訳されたか比較しやすいハズ。
出力されたアセンブリ言語ファイルをメモ帳などで開き、もとの C/C++ 言語のソースコードと一致する箇所を確認する。該当箇所近辺に

push や pop レジスタ名
mov ~ DWORD PTR [esp + △△ ] , レジスタ名
mov ~ QWORD PTR [rsp + △△ ] , レジスタ名
といったコードが含まれているかもしれない。
esp や rsp はスタックポインタ名。スタックポインタを簡単に説明すれば、手一杯なとき一時的にデータを預けるとして、預かり場所の案内係。
これらのコードはメモリ上にレジスタの値をストアもしくはロードする。コンパイラが「この部分でレジスタが足りない」と予想した結果、退避や復元のためストアやロード命令が追加される。

演算を高速化したい部分はたいてい反復処理、ループ化する。ループカウンタを扱うためのレジスタが空いてなければ

inc [esp + △△ ]
inc [rsp + △△ ]

dec [esp + △△ ]
dec [rsp + △△ ]

といった加算や減算のコードが含まれているハズ。もし、加算や減算の部分、つまりループカウンタの変数がレジスタに割り当てられれば

inc レジスタ名 , レジスタ名
dec レジスタ名 , レジスタ名

となる。ほかにも、残り回数を比較する部分で

cmp レジスタ名 , ◇◇
test レジスタ名 , レジスタ名

などの命令が含まれているハズ。
ループカウンタの変数は何度もアクセスされるためキャッシュメモリにヒットする。昨今のCPUはキャッシュメモリへのアクセスが効率化されており、それほど遅くならない・・・

話がアセンブリ言語レベルに偏ってしまいました。冒頭の通り OS を Microsoft Windows 、開発環境 を Visual Studio 、C/C++ 言語にで話しを進めます。
C/C++ 言語を基にアプリを作るとして、どの変数をどのレジスタに割り当てるかはコンパイラ次第。もっと言えばコンパイラの賢さやご機嫌に左右されてしまうのは否めません。なるべく、メモリではなくレジスタに割り当てられるようにレールを敷いてあげることが解決の糸口になるかもしれません。

高速化したい近辺のアルゴリズムを見直す、つまり手順を改良することで良い結果が得られるケースも多々あります。
検索サイトからお越しいただいている方々の中には
多重ループをシングルループに変更できないか検討すると良い
などの記述を目にしたのではないでしょうか。

しばしば教科書的な例として、画像処理で連続したメモリ空間にあるデータのうちx軸 ・y軸 の指す値を一律に処理するサンプルコードが載っています。

100 × 100 ピクセル分のマス目があり、処理したい数値が直線的に並んでいるとしましょう。x が 0 から 99 最大値 - 1 まで1つずつ増えてゆき、x が 100 に到達したら x を 0 に戻し y を 1 増やします。y が 100 になると処理が終了・・・といった具合。
x や y の表現よりもアナログ時計の短針、長針を思い浮かべると簡単かもしれません。長針が 0 から 59 で一周すると短針が1 増えます。現在の値は「短針の値 × 60 + 長針 の値」とひとつに纏めることができます。

一般的には変数の数が増えるほど、多くのレジスタ数が必要。この観点から、
・2つの変数を用いるよりもひとつの変数で済ませる
・二次元配列を一次元にまとめる
などのカスタマイズは有意義である。

n [x][y] = ~~~~~~ ;

といったコードを
n[y * 100 + x] = ~~~~~~ ;

に書き直すといった感じだろうか。
もっとも、コンパイラはバージョンアップ毎に賢くなっています。上記のように単純なコードであれば手動で書き直すのは不要かもしれません。最近のコンパイラを使っていれば同等の最適化を代行してくれる可能性が高いハズ。コンパイラに任せてしまうほうが楽。
メンテナンス面を考慮しても、後日でも読み易いコードを組むことは重要です。

仮に、コンパイラが適切なコードを生成しないなどの理由でカスタマイズするならば、「なぜソーソコードをこのように変更したのか」等のコメントを残すよう心がけたいものである・・・

それよりも、実行環境が64ビット版の OS ならば、アプリも64ビット版としてビルドしなおす方が効果的かも。レジスタ不足やその対処コードが追加されてしまうのは32ビット版のアプリとしてビルドした場合に顕著。



同じソースファイルからビルドしたもので比べた場合、64ビット版のアプリの方が効率的なコードが生成されるのは明らか。



64ビット版向けへの切り替え方が判らないヒトは車輪の再発明 (7)の後半をご参照あれ・・・

とはいえ、外部のライブラリ、プラグインモジュールが64ビットに対応していない、32ビット環境に縛られてしまう状況もあることでしょう。はたまた、CPU は64ビット版に対応しているにもかかわらず 32ビット版の OS を購入してしまい、64ビット版のアプリを実行できないヒトもいることでしょう。

Microsoft の Visual Studio を利用しているならば、32ビット版アプリをビルドする際、
/Oy オプションを指定することにより、フレームポインタの作成が省略されます。副作用として自由に使える汎用レジスタが1本増えます。



さらに、
/Ox (最大限の最適化) や /O1 と /O2 (実行速度) のオプションを指定した場合、/Oy オプション を指定したのと同じ効果が得られる。」とMSDN に載っているハズ。

アプリを高速化したいと考えるなら、「最大限の最適化」や「実行速度」を指定するのは自然なことである。

この辺の最適化オプションには苦い思い出がある。いくつか前のバージョンのコンパイラで「最大限の最適化」を施した場合、不正なコードが生成されるケースがあった。同じブロックで特定の条件が揃うとアプリが暴走してしまった。最適化条件を変え、「フレームポインタの作成が省略」をオフにしたり、ほかのコンパイラでビルドした場合には正常に実行できた。
出力されたアセンブリ言語ファイルを開き、「ソースコード」と翻訳された「コンピュータ語のコード」を比較することで、不正なコードが生成されていることが発見できた。

不正なコードが生成されるのは高速化とは無縁の部分だった。よって、その部分だけ「フレームポインタの作成が省略」をオフにすることでトラブルから逃れることができた。

フレームポインタの在無により問題が生じてしまう部分を
#pragma optimize( "y", off )


#pragma optimize( "y", on )

で囲うことでトラブルから脱出するに至った。この囲われた部分は最適化されなくなる。

あくまでも、Microsoft の Visual Studio 固有の機能。#pragma ~~ ディレクティブは環境に依存する。#pragma ~~ を残しておくと Microsoft の Visual Studio 以外では翻訳する際エラーとなってしまう可能性が高い。
また、同系列のコンパイラでもバージョンアップとともに使えなくなることもある。#pragma ディレクティブを使うのであれば、前後を #if と #endif ディレクティブで囲い、特定の環境では無効になるようにガードしておくと安全である・・・

32ビット版アプリを前提とした、レジスタが足りない場合のお話は続きがあります。

長くなりましたので今回はこの辺で・・・

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

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

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

コメントの投稿

非公開コメント

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

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

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

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

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

最新記事
カレンダー
07 | 2017/08 | 09
- - 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 31 - -
カテゴリ
ランキング
いつも応援いただきありがとうございました。ただいま休養中につきランキングへ参加していません・・・

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

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

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