雨谷の日和

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

ボヤキ - 技術

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 最適…