雨谷の日和

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

ボヤキ - 技術

行列式計算改良(先頭アドレスのみコピー)インデックス版(alloca)

2004.07.24のものはmallocでメモリの確保を行っていたが、今度はそれをallocaで行う場合を見てみよう。 ソースコードは以下のようになるだろう。 #include #include long array[ ] = { 1, 2, 3, 4, 6, 1, 7, 1, 9, 0, 0, 5, 1, 5, 7, 7, 3, 5, 3, 6, 1, 6, 7…

行列式計算改良(先頭アドレスのみコピー)インデックス版Java(AOT)

次に、AOTでの実測も行っておこう。 20:38:51 result: 489261678 20:39:39 result: 489261678 20:40:27 result: 489261678 20:41:13 最適化無しで約48秒、配列関係の最適化有りでも約48秒、更に最適化(-O3)すると約46秒という結果となった。 若干の向上が…

行列式計算改良(先頭アドレスのみコピー)インデックス版Java(最適化有)

次は最適化有りの結果を見てみよう。 result: 489261678 Flat profile of 5.40 secs (334 total ticks): main Interpreted + native Method 0.3% 0 + 1 java.io.WinNTFileSystem.getLastModifiedTime 0.3% 0 + 1 Total interpreted Compiled + native Method…

行列式計算改良(先頭アドレスのみコピー)インデックス版Java(最適化無)

Javaで書いたものについて、まずは最適化無しでの実行profileを見てみよう。 result: 489261678 Flat profile of 51.35 secs (3277 total ticks): main Interpreted + native Method 98.6% 2798 + 432 Test.expand 98.6% 2798 + 432 Total interpreted Threa…

行列式計算改良(先頭アドレスのみコピー)インデックス版Java

ということで、2004.07.24のものをJavaで書き直してみた。 以下のようになると思う。 class Test { private static long[ ] array = new long[ ]{ 1, 2, 3, 4, 6, 1, 7, 1, 9, 0, 0, 5, 1, 5, 7, 7, 3, 5, 3, 6, 1, 6, 7, 6, 4, 8, 4, 6, 1, 7, 1, 4, 8, 6, …

行列式計算改良(先頭アドレスのみコピー)インデックス版2

ということで、実際に実行してみよう。 20:34:53 result:489261678 20:35:35 result:489261678 20:36:16 最適化無しで約42秒、最適化有りで約41秒という結果となった。 書き直す前の結果と全く同じ結果になったことになる。 ということで、今度はこれをJava…

行列式計算改良(先頭アドレスのみコピー)インデックス版

2004.07.20のものを、ポインタを使わない記述に書き換えてみる。 ポインタはその変数のメモリ上の位置を指し示すものだが、今回のソースコードでは配列の中の、参照するインデックス位置を指し示すのに使われているだけである。 ということで、ポインタの配…

行列式計算改良(先頭アドレスのみコピー)ポインタ版2

ということで、昨日のものを実行してみよう(gccで) 20:36:16 result:489261678 20:36:58 result:489261678 20:37:39 最適化無しで約42秒、最適化有りで約41秒という結果となった。 以前のものの結果と比較すると、若干改善しているようだ。 さて、これをJa…

行列式計算改良(先頭アドレスのみコピー)ポインタ版

先日書いたように、しばらく行列式計算のアルゴリズムの改良を試みようと思う。 前提条件は以下とする。 誤差を極力避けるため、整数値の加減算と乗算のみを用いる。 アルゴリズムの改良度合いの比較のため、データ内容に依存する改良(枝刈りなど)は後回し…

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

ということで、Borland Cの場合も含めた、実測結果をまとめておく。 Pentium4:2.4GHzWindowsXP(MS932)cygwingcc3.3.1Borland C++5.5JDK1.4 CJava gccBorland CインタプリタHotSpotAOT 最適化無最適化有最適化無最適化有最適化無最適化配列最適化有 mallocal…

Cでの行列式計算(Borland C、ループ)

失礼。昨日書いた結果は、全然別の実測でした。(その旨注記しました) ということで、ループに展開した場合の実測を再度。 動的メモリ確保、malloc/free 20:35:56 result: 489261678 20:36:04 result: 489261678 20:36:12 最適化無:約8秒、最適化有:約8秒…

Cでの行列式計算(Borland C、ループ)間違い

※この日の記述は、私のミスで全く別のものを書いてしまっています。以下は全くの間違いです。記録としては残しておきますが、内容は無効です。最後に、ループに展開した場合の実測を行っておこう。 動的メモリ確保、malloc/free 20:40:54 result:489261678 2…

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

今度は、再帰呼び出しを単純に関数に展開した場合を実測してみよう。 動的メモリ確保、malloc/free 20:04:10 result: 489261678 20:04:14 result: 489261678 20:04:19 最適化無:約4秒、最適化有:約5秒 動的メモリ確保、alloca 20:04:19 result: 489261678 …

Cでの行列式計算(Borland C、再帰有)

まずは再帰呼び出し有の場合のソースコードをコンパイルし、実行時間を見てみよう。 動的メモリ確保、malloc/free 20:16:31 result: 489261678 20:16:37 result: 489261678 20:16:42 最適化無:約6秒、最適化有:約5秒 動的メモリ確保、alloca 20:16:42 resu…

Cでの行列式計算(Borland C)

以前、kp氏から以下のように指摘頂いているので、検証を行う。 以下、該当部分を再度引用します。 Pentium4 1.9GHz+Borland C++ 5.5で3.5秒前後。ただ改変する前も7秒程度で終了していた。さらに、事前メモリ確保バージョンを試したところ4.5秒程度だったの…

JavaとCとの性能比較(行列式計算/ループ)

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

Javaでの行列式計算(ループ、事前、AOT)

最後に、AOTの場合も実測しよう。 20:47:05 result: 489261678 20:47:24 result: 489261678 20:47:32 result: 489261678 20:47:38 最適化無しで約19秒、配列関連の最適化を行うと約8秒、更に最適化(-O3)を行うと約6秒という結果となった。 次回、これらの…

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

今度は最適化した場合を見てみよう。結果は以下のようになった。 result: 489261678 Flat profile of 10.61 secs (679 total ticks): main Interpreted + native Method 0.1% 1 + 0 java.util.jar.Attributes$Name.isValid 0.1% 1 + 0 Total interpreted Com…

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

まずは最適化無しで実行してみよう。 result: 489261678 Flat profile of 159.05 secs (11168 total ticks): main Interpreted + native Method 100.0% 11167 + 0 Test.expand 100.0% 11167 + 0 Total interpreted Thread-local ticks: 0.0% 1 Class loader …

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

今度はJavaで、事前メモリ確保の場合を実測する。 ソースコードは以下のようになる。 public class Test { private static long[ ][ ] array_buf; public static long expand(long[] arraybase, int dim){ long[ ][ ] array = new long[dim][ ]; long[ ] ret…

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 …