雨谷の日和

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

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

ということで、こんどはalloca版を考えてみよう。
……と思ったのだが、この場合mallocをallocaで単純に書き換えるのは不味いということが分かった。

do {
  if(d < 2){
    return_value[d - 1] = array[d - 1][0];
    d++;
    flg = 1;
  }else{
    if(flg == 0){
      if(i[d - 1] == 0){
        //array[d - 2] = (long *)malloc( (d - 1) * (d - 1) * sizeof(long) );
        array[d - 2] = (long *)alloca( (d - 1) * (d - 1) * sizeof(long) );
        return_value[d - 1] = 0;
      }
      if(i[d - 1] < d){
        l = 0;
        for(j = 0; j < d; ++j){
          if(j != i[d - 1]){
          for(k = 1; k < d; ++k)array[d - 2][(l * (d - 1)) + k - 1] = array[d - 1][(j * d) + k];
            ++l;
          }
        }
        d--;
        i[d - 1] = 0;
      }
    }else{
      if(i[d - 1] < d){
        if(i[d - 1] % 2 == 0){
          return_value[d - 1] += (array[d - 1][i[d - 1] * d] * return_value[d - 2]);
        }else{
          return_value[d - 1] -= (array[d - 1][i[d - 1] * d] * return_value[d - 2]);
        }
        i[d - 1]++;
        flg = 0;
      }
      if(i[d - 1] == d){
        //free(array[d - 2]);
        d++;
        flg = 1;
      }
    }
  }
}while(d <= dim);

コメントアウトした部分がmalloc/free版の記述、その側にあるのがalloca版の記述になっている。
見て頂ければ分かるが、mallocと異なりallocaには明示的にメモリを解放する文法が無い。(少なくとも、私は知らない)
allocaはスタック領域(ローカル変数などのメモリ領域)にメモリを割り当てるものなので、通常はその関数から抜ける際に割り当て領域も解放されるからだ。
前回まではそれぞれの処理ごとに関数を割り当てていたので、その中でのallocaは特に問題なかった。関数から抜ける際にメモリも解放されるからだ。
しかし今回は処理が全て一つの関数内に収まっているため、それらは全ての処理が終わるまで解放されることがなく、別途のスタック領域を割り当て続けてしまうことになる。実際、上記のソースコードコンパイルし、実行するとあっけなくコアダンプで落ちた。
もちろん、このループでの処理で何度も動的にメモリを割り当てる必要は無い(既に必要なメモリはローカル変数の初期化時に取得済みだから)のだが、そういう記述に変更してしまうと、再帰でのものや関数展開でのものなどとの比較に意味がなくなってしまう。
ということで、今回は測定結果無しということで。