読者です 読者をやめる 読者になる 読者になる

雨谷の日和

過去12年で1,600を超えるアニメの第1話だけは見続けた僕のお勧めアニメがハズレなはずがない

Cでの行列式計算(ループ、事前、alloca)

次に、事前メモリ確保のallocaでの実装を実測してみよう。 ソースコードは以下のようになる。 #include #include long** array_buf; long expand(long arraybase[ ], int dim){ int j, k, l, index, d, flg; long **array; long *return_value; int *i; long…

行列式計算の色々なアルゴリズム2

kp氏より、ここの2004.06.27付けの記述にコメントを頂いています。→「行列式」 雨谷の日和の行列式計算の色々なアルゴリズムで言及されているように、行列式の計算として掃き出し法が速度に対して有効なのは確かなのですが、精度が落ちる可能性があるという…

Cでの行列式計算(ループ、事前、malloc/free)

今度は事前にメモリを確保してその領域を使い回す方法を、ループ展開の場合にも試してみよう。 まずはCのmalloc/freeについて書き下すと以下のようになる。 #include #include long** array_buf; long expand(long arraybase[ ], int dim){ int j, k, l, in…

行列式計算の色々なアルゴリズム

以前から色々ご指摘頂いているkp氏から、今回のループへの展開の実測結果についての考察を頂いています。有難うございます。 「河馬は赤い血を流す」より引用します。 以前再起関数はループに変換でき、ループにしたほうが一般的に速いと書きましたが、この…

Javaでの行列式計算(ループ、動的、AOT)

今度はAOTを用いた場合の処理時間を実測しよう。 20:41:27 result: 489261678 20:42:31 result: 489261678 20:43:23 result: 489261678 20:44:15 最適化無しで約64秒、配列関連の最適化有りで約52秒、更に最適化(-O3)しても約52秒という結果となった。 性…

Javaでの行列式計算(ループ、動的、最適化有)

次に最適化有りにして実行してみよう。 result: 489261678 Flat profile of 12.36 secs (761 total ticks): main Interpreted + native Method 0.1% 0 + 1 sun.net.www.URLConnection. 0.1% 0 + 1 java.lang.String.length 0.3% 0 + 2 Total interpreted Com…

Javaでの行列式計算(ループ、動的、最適化無)

では、昨日のソースコードを実行してみよう。 まずは最適化無しで実測を行ってみる。 result: 489261678 Flat profile of 154.12 secs (9749 total ticks): main Interpreted + native Method 99.6% 9178 + 459 Test.expand 0.0% 0 + 1 java.io.WinNTFileSys…

Javaでの行列式計算(ループ、動的)

今度は、Javaで実測を行う。 ループ展開したものを元に、実際に動くソースコードを書くと、以下のようになる。 public class Test { public static long expand(long[ ] arraybase, int dim){ long[ ][ ] array = new long[dim][ ]; long[ ] return_value = …

Cでの行列式計算(ループ、動的、alloca)

ということで、こんどはalloca版を考えてみよう。 ……と思ったのだが、この場合mallocをallocaで単純に書き換えるのは不味いということが分かった。 do { if(d malloc( (d - 1) * (d - 1) * sizeof(long) ); array[d - 2] = (long *)alloca( (d - 1) * (d - 1…

Cでの行列式計算(ループ、動的、malloc/free)

ということで、前回までの展開結果を元に、Cのソースを書いてみた。 以下のようになる。 #include #include long expand(long arraybase[], int dim){ int j, k, l, index, d, flg; long **array; long *return_value; int *i; long result; array = (long …

再帰のループ展開その9

さて、いよいよ展開した結果を元に、expand 関数を書いてみよう。 private static long expand(long[ ] arraybase, int dim){ long[ ][ ] array = new long[dim][ ]; long[ ] return_value = new long[dim]; int[ ] i = new int[dim]; int d = dim; int flg …

再帰のループ展開その8

昨日までの置換で、ほぼ再帰の展開は終わっている。 ただ、一時変数のvalue が残っているので、これを消去しよう。 value の使われているのは以下の部分。 long value = 0; if(i[d - 1] % 2 == 0){ value += (array[d - 1][i[d - 1] * d] * return_value[d -…

再帰のループ展開その7

最後に、(E)を置換しよう。 (E) if(i % 2 == 0){ value += (array[i * dim] * result); }else{ value -= (array[i * dim] * result); } array はarray[d - 1]、result はresult_value[d - 2] になる。 (E) if(i[d - 1] % 2 == 0){ value += (array[d - 1][i[…

再帰のループ展開その6

(B)に続いて、(C)の置き換えを行う。 (C)は単純な配列のコピーなので、ほとんどそのまま置き換えだけでよい。 (C) int l = 0; for(int j = 0; j 上記が、以下のようになる。 (C) int l = 0; for(int j = 0; j array[d - 1] から、array[d - 2]へのコピーだ。…

再帰のループ展開その5

ロジック的な部分は整理し終えたので、今度は(B)(C)(E)を埋め込み、変数を新しいものに置き直そう。 まず、(B)を置換する。 (B) long[ ] subarray = new long[(dim - 1) * (dim - 1)]; long value = 0; 上記のsubarray は array[ ] に置き換わる。次の呼び出…

再帰のループ展開その4

では、i のループを消してみよう。 ループを度外視してi[ ] の初期化とインクリンメントを該当箇所にバラしてみる。 long[ ][ ] array = new long[dim][ ]; long[ ] return_value = new long[dim]; int[ ] i = new int[dim]; int d = dim; //d = dim if(d こ…

再帰のループ展開その3

どんどん行こう。 昨日までで、なんとなくd をパラメータとしたループになりそうだと分かる。 各段階の計算結果はreturn_value のd - 1 の場所に格納していけば良い。 ということで、その見込みに従いd に対する操作を追加してみよう。 long[ ][ ] array = n…

再帰のループ展開その2

では展開の続きを。 次に(B)の部分とreturn文をループの中に入れることが出来るので入れておく。 ただし、i に関する条件付きで。 private static long expand(long[] array, int dim) { if(dim さて、ここからが本番である。 関数の呼び出しの記述によって…

再帰のループ展開その1

ということで、再帰呼び出しを今度はループに展開してみようと思う。 結構ややこしいので、順を追ってちまちまと開いていくことにする。 展開対象となるのは、以下のexpand関数である。 作業はまずJavaの方で行い、後にCの方も類似の記述に改めることにする…

JavaとCとの性能比較(行列式計算)

ということで、再帰有りと再帰無しの結果を表にまとめておく。 Pentium4:2.4GHzWindowsXP(MS932)cygwingcc3.3.1JDK1.4 CJava 最適化無最適化有インタプリタHotSpotAOT mallocallocamallocalloca最適化無最適化配列最適化有 行列式計算再帰有り動的メモリ確…

Javaでの行列式計算(再帰無し、事前、AOT)

では次は、AOTでの実行性能を計測してみよう。 2004.05.25でのソースコードをコンパイルし、実行してみた結果が以下である。 20:04:31 result: 489261678 20:04:38 result: 489261678 20:04:43 result: 489261678 20:04:47 最適化無で約7秒、配列関係の最適…

Javaでの行列式計算(再帰無し、事前、最適化有)

次は最適化有の場合である。 result: 489261678 Flat profile of 6.22 secs (372 total ticks): main Interpreted + native Method 0.3% 1 + 0 java.lang.String.toLowerCase 0.3% 1 + 0 Total interpreted Compiled + native Method 39.0% 145 + 0 Test.exp…

Javaでの行列式計算(再帰無し、事前、最適化無)

では、昨日のソースコードを実際に実行してみよう。 まずは最適化無の場合である。 result: 489261678 Flat profile of 65.98 secs (4222 total ticks): main Interpreted + native Method 40.6% 1713 + 0 Test.expand02 32.1% 1354 + 0 Test.expand03 17.2%…

Javaでの行列式計算(再帰無し、事前)

では改めて。 2004.05.15付のソースコードを、今度は事前メモリ確保のそれに書き換えてみよう。 private static long array_buf; public static long expand01(long array) { return array[0]; } (省略) public static long expand11(long array) { int i,…

まちがえました

2004.05.22でCの場合の再帰呼び出しを展開した場合の事前メモリ確保の場合を実測、と書きましたが、それ、以前に既にここに掲載してました。→2004.05.10、2004.05.11 失礼しました。次は、Javaの場合の事前メモリ確保を実測する順番でした。 ということで、…

Cでの行列式計算(再帰無し、事前メモリ確保)

さて、次は再帰呼び出しを関数に展開したもので、事前メモリ確保した場合を実測しよう。 まずはCの場合を書き換えてみる。2004.05.06付のソースコードと同様に、以下に掲載しておく。 long expand11(long array[]) { int i, j, k, l; long value = 0; long …

Javaでの行列式計算(再帰無し、動的、AOT)

2004.05.15付のJavaのソースコードを、今度はAOTコンパイラでネイティブバイナリにコンパイルし、それを実行してみよう。 なお最適化については以前と同じく、配列チェックを無くす最適化と、それに加えて「-O3」での最適化との2つの場合を実測してみる。 …

Javaでの行列式計算(再帰無し、動的、最適化有)

それでは、今度は最適化有の場合のprofileを見てみよう。 以下のようになった。 result: 489261678 Flat profile of 6.82 secs (407 total ticks): main Interpreted + native Method 0.2% 1 + 0 Test.expand08 0.2% 0 + 1 java.lang.String.indexOf 0.5% 1 …

Javaでの行列式計算(再帰無し、動的、最適化無)

では、まずは最適化無しのprofileを見てみよう。 result: 489261678 Flat profile of 75.86 secs (4802 total ticks): main Interpreted + native Method 44.4% 1833 + 297 Test.expand02 30.9% 1392 + 92 Test.expand03 14.5% 663 + 33 Test.expand04 5.2% …

Javaでの行列式計算(再帰無し、動的)

今度はJavaのソースコードについても、再帰呼び出しを展開した形にして、どうなるかを見てみよう。 以下のようになる。 public static long expand01(long array[ ]) { return array[0]; } (省略) public static long expand11(long array[ ]) { int i, j,…

Cでの行列式計算(再帰無し、事前alloca)

昨日のものと同じソースコードを、今度はallocaでメモリ確保した場合について実測しよう。 19:59:16 result: 489261678 19:59:20 result: 489261678 19:59:22 最適化無しで約4秒、最適化有りで約2秒となった。 再帰呼び出しの場合はそれぞれ約5秒、約3秒だっ…

Cでの行列式計算(再帰無し、事前malloc/free)

昨日の結果は以下のようになった。 19:59:11 result: 489261678 19:59:14 result: 489261678 19:59:16 最適化無しで約3秒、最適化有りで約2秒となったようだ。 再帰呼び出し無しだとそれぞれ約5秒、約3秒だから、こちらもやや速くなったと言える。

Cでの行列式計算(再帰無し、事前メモリ確保)

もはや私の趣味でしかないが、考え付くパターンについて実測を続けよう。 今度は、再帰呼び出しを展開した場合の、事前メモリ確保でのソースコードを見てみよう。 long expand11(long array[]) { int i, j, k, l; long value = 0; long *subarray = array_bu…

Cでの行列式計算(再帰無し、動的alloca)

次はmalloc/freeの代わりにallocaを用いた場合を実測しよう。 ソースコードの該当部分は、以下のように変更する。 long expand11(long array[]) { int i, j, k, l; long value = 0; long *subarray; subarray = (long *)alloca(10 * 10 * sizeof(long)); for…

Cでの行列式計算(再帰無し、動的malloc/free)

では、昨日のものを実際に実行してみよう。 19:57:39 result: 489261678 19:58:23 result: 489261678 19:59:05 最適化無しのものは約44秒、最適化有り(-O3)のものは約42秒という結果になった。 再帰有りのものだとそれぞれ約46秒、約43秒だったので、ほと…

Cでの行列式計算(再帰無し)

さて、動的メモリ確保がCではかなり負荷が高く、Javaではそれ程でもない、ただしJavaはその分メモリ管理の厳密性を犠牲にしているようだということは分かった。 では、もう一つ2004.04.02付でのソースコードで速度劣化の原因になりそうということで挙げられ…

JavaとCとの性能比較(行列式計算/再帰呼び出し有)Solaris版

2004.04.27付の「JavaとCとの性能比較(行列式計算/再帰呼び出し有)」と同じものをSolarisで実行した結果も実測してきたので、結果を掲載する。 UltraSPARC3:1.2GHzSolaris8(EUCJP)gcc2.95.3JDK1.4 CJava 最適化無最適化有インタプリタHotSpotAOT malloca…

JavaとCとの性能比較(ファイル出力処理)Solaris版

2004.03.27付の「JavaとCとの性能比較(ファイル出力処理)」での結果はWindowsXPでの結果だった。 今回、それと同じものをSolarisを借りて実行することが出来たので、その結果を掲載する。 UltraSPARC3:1.2GHzSolaris8(EUCJP)gcc2.95.3JDK1.4 CJava 最適…

JavaとCとの性能比較(行列式計算/再帰呼び出し有)

ということで、ここまでで再帰呼び出し有りの行列式計算での性能比較は一区切りとしたい。 出力処理の時と同じく、比較表にまとめておこう。 Pentium4:2.4GHzWindowsXP(MS932)cygwingcc3.3.1JDK1.4 CJava 最適化無最適化有インタプリタHotSpotAOT mallocall…

一次キャッシュの効果

2004.04.17付の日記で、以下のようなことを書きました。 これで分かることは、それが例えmallocで確保されたものであっても、メモリ領域にアクセスするだけなら特に性能劣化の原因にはならないということだろうか。 要するに、malloc/freeの処理そのものが遅…

Javaでの行列式計算(事前メモリ確保での実装/AOT)結果

では今度は2004.04.20付の事前メモリ確保での行列式計算のソースコードでAOTコンパイラを使った場合を実測してみよう。 昨日と同じようにコンパイル、実行した結果が以下である。 20:51:25 result: 489261678 20:51:35 result: 489261678 20:51:41 result: 4…

Javaでの行列式計算(動的メモリ確保での実装/AOT)結果

では、まず2003.03.31付で提示した、動的メモリ確保して行列式を計算させるソースコードをコンパイルし、実行してみよう。 コンパイルは以下のようにして行った。 gcj -o jtest.exe --main=Test Test.java gcj -o jtest1.exe -fno-bounds-check -fno-store-c…

JavaのAOTコンパイラ

さて、ちょっとここで比較項目を増やそうと思う。 いままでJavaについてはHotSpotでの最適化のみを取り上げて比較してきた。 しかしJavaでは実行時最適化のHotSpotの他にも、Cと同じような実行前最適化の技術の研究も為されている。 Ahead of time(AOT)コ…

Javaでの行列式計算(事前メモリ確保での実装/最適化有)結果

2004.04.21と同じものを、こんどは最適化有りで実行してみたprofilegは、以下である。 result: 489261678 Flat profile of 7.62 secs (487 total ticks): main Interpreted + native Method 0.2% 1 + 0 java.util.jar.Attributes.read 0.2% 1 + 0 Total int…

Javaでの行列式計算(事前メモリ確保での実装/最適化無)結果

では、2004.04.20のソースを最適化無しで実行してみよう。 result: 489261678 Flat profile of 81.38 secs (5208 total ticks): main Interpreted + native Method 99.4% 5179 + 0 Test.expand 0.0% 0 + 1 java.util.zip.Inflater.inflateBytes 99.5% 5179 +…

Javaでの行列式計算(事前メモリ確保での実装)

それでは、Javaでも事前にメモリを確保してから処理を行うように書いてみよう。 以下のようになる。 class Test { private static long[ ][ ] array_buf; private static long expand(long[ ] array, int dim) { if(dim 次回と次々回をかけて、最適化無/有の…

Cでの行列式計算(事前メモリ確保での実装)結果2

2004.04.16付け付のソースの、mallocの部分をallocaに変えてコンパイルし直し、同じようにして実行してみた。(freeの行も削除した) 結果は以下である。 20:16:26 result: 489261678 20:16:32 result: 489261678 20:16:37 result: 489261678 20:16:41 resul…

Cでの行列式計算(事前メモリ確保での実装)結果

2004.04.16付のソースを実行してみた。 20:13:14 result: 489261678 20:13:20 result: 489261678 20:13:25 result: 489261678 20:13:29 result: 489261678 20:13:32 result: 489261678 20:13:35 最適化無しで約5秒、最適化有りだと約3秒という結果である。非…

Cでの行列式計算(事前メモリ確保での実装)

malloc/freeでの動的なメモリの管理に負荷がかかる(そしてこれはkp氏の指摘にあるように、必要な負荷である)ことから、高速化のためには、必要なメモリ領域を事前に確保しておくと良さそうだということが分かった。 ということで、事前にメモリを確保する…

Cでの行列式計算(allocaでの実装)結果

では、2004.04.14付「Cの行列式計算(allocaでの実装)」で示したソースコードをコンパイルし、実行してみよう。 20:56:28 result: 489261678 20:56:36 result: 489261678 20:56:44 result: 489261678 20:56:48 result: 489261678 20:56:52 result: 4892616…