6

私は、C で一般的なデータ処理を高速化しようと取り組んでいます。次の形式のサブルーチンをいくつか作成しました。

double *do_something(double *arr_in, ...) {
   double *arr_out; 
   arr_out = malloc(...)

   for (...) {
     do the something on arr_in and put into arr_out
   }

   return arr_out; 
}

このスタイルは読みやすく使いやすいので気に入っていますが、よく次のように呼んでいます。

 array = do_something(array,...);

代わりに void サブ関数を次のように使用すると、コードが高速になります (メモリ リークが防止される可能性があります)。

void do_something(double *arr_in, ...) {
   for (...) {
      arr_in = do that something;
   }
   return;
}

更新 1: 実行可能ファイルで valgrind --leak-check=full を実行しましたが、最初の方法を使用したメモリ リークはないようです。ただし、実行可能ファイルは、このフォームで作成したすべてのサブルーチンを含むライブラリにリンクしているため、ライブラリからのリークをキャッチできない可能性があります。

メモリを解放するラッパーをどのように作成するか、** が実際に何をするか、またはポインターへのポインターが何であるかについて知りたいので、 ** ルートの使用を避けています (それとおそらく私はそれをやった私のMacではコンパイルされなかったので間違っています)。

現在のサブルーチンの 1 つを次に示します。

double *cos_taper(double *arr_in, int npts)
{
int i;
double *arr_out;
double cos_taper[npts];
int M; 
M = floor( ((npts - 2) / 10) + .5);

arr_out = malloc(npts*sizeof(arr_out));

for (i=0; i<npts; i++) {
    if (i<M) {
        cos_taper[i] = .5 * (1-cos(i * PI / (M + 1)));
    }
    else if (i<npts - M - 2) {
        cos_taper[i] = 1;
    }
    else if (i<npts) {
        cos_taper[i] = .5 * (1-cos((npts - i - 1) * PI / (M + 1)));
    }
    arr_out[i] = arr_in[i] * cos_taper[i];
}
return arr_out;
}

私がここで得たアドバイスから、より良い方法のように思えます:

void *cos_taper(double *arr_in, double *arr_out, int npts)
{
int i;
double cos_taper[npts];
int M; 
M = floor( ((npts - 2) / 10) + .5);

for (i=0; i<npts; i++) {
    if (i<M) {
        cos_taper[i] = .5 * (1-cos(i * PI / (M + 1)));
    }
    else if (i<npts - M - 2) {
        cos_taper[i] = 1;
    }
    else if (i<npts) {
        cos_taper[i] = .5 * (1-cos((npts - i - 1) * PI / (M + 1)));
    }
    arr_out[i] = arr_in[i] * cos_taper[i];
}
return
}

電話:

int main() {
  int npts;
  double *data, *cos_tapered;

  data = malloc(sizeof(data) * npts);
  cos_tapered = malloc(sizeof(cos_tapered) * npts);

//fill data

  cos_taper(data, cos_tapered, npts);
  free(data);
  ...
  free(cos_tapered);
  ...
  return 0;
}
4

12 に答える 12

5

malloc は、それが何であるかによって、実行している処理に比べて高価になる可能性があります。インプレース処理に制限するのではなく、in と out の 2 つのパラメーターを使用し、呼び出し元に割り当てを任せます。これにより、呼び出しごとに新しい配列を割り当てずにメモリを再利用するオプションが呼び出し元に与えられます。

于 2010-02-05T18:12:42.093 に答える
1

元のメモリ割り当てへの他のポインタがない場合、最初の呼び出しでメモリリークが発生する可能性があります。

はい、メモリ割り当てなしで呼び出された関数の2番目のバージョンを適切に記述できる場合は、メモリ割り当てに時間がかかるため、より高速になる可能性があります。呼び出された関数を変更して、入力配列と出力配列が事前に割り当てられている場合は、メモリ割り当てコストが呼び出し元の関数に転送される可能性があります。

ただし、最初のバージョンを規律正しく使用することは問題ありません。この関数はスペースを割り当てます。渡された元のスペースと戻された新しいスペースの両方を追跡し、両方を解放できる限り、問題はありません。

次の場合、「同じ」問題が発生する可能性があります。

xyz = realloc(xyz, newsize);

xyzが割り当てられたメモリへの唯一のポインタである場合、nullポインタでxyzを壊したばかりであるため、割り当ての失敗時にメモリリークが発生します。元のスペースを解放するために使用する別のポインターがある場合、このイディオムは重要ではありませんが、注意が必要です。


この回答の元のバージョンを書いたので、私は質問の追加情報を完全に消化していません。

于 2010-02-05T18:08:00.497 に答える
1

操作を適切に実行できる場合は、バグ(少なくともメモリ関連のバグ)を防ぐのに役立つ可能性があり、少なくともmalloc()操作にかかる時間だけ高速になります。関数の実際の戻りタイプは、おそらく速度にまったく影響しません。

于 2010-02-05T18:08:34.917 に答える
1

コードを実行しました (いくつかの小さなエラーを修正した後)。次に、いくつかのスタックショットを撮りました。mallocあなたの犯人だろうと言った人々は正しかった。ほぼすべての時間をそこで過ごします。それに比べて、コードの残りの部分はそれほど重要ではありません。コードは次のとおりです。

#include <math.h>
#include <stdlib.h>
const double PI = 3.1415926535897932384626433832795;

void cos_taper(double *arr_in, double *arr_out, int npts){ 
    int i; 
//  double taper[npts];
    double* taper = (double*)malloc(sizeof(double) * npts); 
    int M;  
    M = (int)floor( ((npts - 2) / 10) + .5); 

    for (i=0; i<npts; i++){ 
        if (i<M) { 
            taper[i] = .5 * (1-cos(i * PI / (M + 1))); 
        } 
        else if (i<npts - M - 2) { 
            taper[i] = 1; 
        } 
        else if (i<npts) { 
            taper[i] = .5 * (1-cos((npts - i - 1) * PI / (M + 1))); 
        } 
        arr_out[i] = arr_in[i] * taper[i]; 
    }
    free(taper);
    return;
}

void doit(){
    int i;
    int npts = 100; 
    double *data, *cos_tapered; 

    data = (double*)malloc(sizeof(double) * npts); 
    cos_tapered = (double*)malloc(sizeof(double) * npts); 

    //fill data 
    for (i = 0; i < npts; i++) data[i] = 1;

    cos_taper(data, cos_tapered, npts); 
    free(data); 
    free(cos_tapered); 
}

int main(int argc, char* argv[]){
    int i;
    for (i = 0; i < 1000000; i++){
        doit();
    }
    return 0;
}

編集: 上記のコードの時間を計測しましたが、私のマシンでは 22us かかりました (ほとんどの場合malloc)。次に、malloc を外側で 1 回だけ実行するように変更しました。これにより、時間は 5.0us に短縮されましたが、これは主にcos関数内にありました。次に、デバッグ ビルドからリリース ビルドに切り替えたところ、時間は 3.7us に短縮されました (cos明らかに、関数内ではさらに多くなっています)。したがって、本当に高速化したい場合は、スタックショットを使用して、主に何を行っているかを確認し、それを回避できるかどうかを確認することをお勧めします。

于 2010-02-06T01:44:12.777 に答える
1

double自体を返すことは、実行時間の点でそれほど費用がかかりません。

さらに重要なのは、関数に入るたびにメモリを割り当てることです。あなたが提案したように結果を事前に割り当てるか、その場所に保存することができれば、速度が大幅に向上するはずです。

考慮すべきもう 1 つのことは、(float 型に対して) double が提供するすべての精度が実際に必要かどうかです。多くの場合、フロートの方がはるかに高速です。

于 2010-02-05T18:11:02.720 に答える
1

必要に応じて呼び出し元にメモリを割り当てさせることを選択しますが、操作を適切に実行するか、割り当てを行うかを選択することもできます。

その場で実行できない操作については、発信者が同じ入力場所と出力場所を指定したかどうかを手動で確認し、入力のコピーを自分で作成できます。次に、そのコピーを入力として使用して処理します。これにより、関数の呼び出し元に適切に見えます。

たとえば、次のようにインデックスの配列をシャッフルする関数を作成するとしますoutput[i] == input[ input[i] ](ばかげた関数ですが、その場で実行するのは簡単ではありません)。

#include <stdlib.h> 
#include <string.h>
int shuffle(size_t const * input, size_t const size, size_t ** p_output)
{
    int retval = 0;
    size_t i;
    char in_place = 0;
    char cleanup_output = 0;

    if (size == 0)
    {
        return 0; // nothing to do
    }
    // make sure we can read our input and write our output
    else if (input == NULL || p_output == NULL)
    {
        return -2; // illegal input
    }
    // allocate memory for the output
    else if (*p_output == NULL)
    {
        *p_output = malloc(size * sizeof(size_t));
        if (*p_output == NULL) return -1; // memory allocation problem
        cleanup_output = 1; // free this memory if we run into errors
    }
    // use a copy of our input, since the algorithm doesn't operate in place.
    // and the input and output overlap at least partially
    else if (*p_output - size < input && input < *p_output + size)
    {
        size_t * const input_copy = malloc(size * sizeof(size_t));
        if (input_copy == NULL) return -1; // memory allocation problem
        memcpy( input_copy, input, size * sizeof(size_t));
        input = input_copy;
        in_place = 1;
    }

    // shuffle
    for (i = 0; i < size; i++)
    {
        if (input[i] >= size)
        {
            retval = -2; // illegal input
            break;
        }
        (*p_output)[i] = input[ input[i] ];
    }

    // cleanup
    if (in_place)
    {
         free((size_t *) input);
    }
    if (retval != 0 && cleanup_output)
    {
         free(*p_output);
         *p_output = NULL;
    }

    return retval;
}

これにより、関数がより堅牢になります。関数の呼び出し元は、出力にメモリを割り当てたり (入力を維持したい場合)、入力と同じ場所に出力を表示したり、出力にメモリを割り当てたりすることができます。これは、入力場所と出力場所を別の場所から取得していて、それらが異なるかどうかわからない場合に特に便利です。関数の動作について何も知る必要はありません。

// caller allocated memory
my_allocated_mem = malloc( my_array_size * sizeof(size_t) );
if(my_allocated_mem == NULL) { /*... */ }
shuffle( my_array, my_array_size, &my_allocated_mem );

// function allocated memory
my_allocated_mem = NULL;
shuffle( my_array, my_array_size, &my_allocated_mem );

// in place calculation
shuffle( my_array, my_array_size, &my_array);

// (naughty user isn't checking the function for error values, but you get the idea...)

ここで完全な使用例を見ることができます。

C には例外がないため、関数の戻り値を使用してエラーを報告し、計算された値を関数ポインターを介して返すことはかなり標準的です。

于 2010-02-05T19:46:51.383 に答える
0

あなたの職務で

void do_something(double * arr_in、...){
   にとって (...) {
      arr_in = do_that_something;
   }
}

do_something関数がスコープから外れると配列を戻すための参照によるパラメーターがないため、これは正しくありません。次のようになります。

void do_something(double ** arr_in、...){
   にとって (...) {
      * arr_in = do_that_something;
   }
}
/ *
**次のように呼び出されます:
** do_something(&array、...);
* /

読みやすいので、最初の例に固執してください。の呼び出しが失敗した場合は、最初の例でエラーチェックを追加mallocし、NULLポインターで処理を続行する必要があります...

これがお役に立てば幸いです、よろしく、トム。

于 2010-02-05T18:09:52.790 に答える
0

さて、あなたは質問をスピードについて話し始めましたが、この主題が本当に答えられたとは思いません. 最初に言うことは、パラメーターの受け渡しに取り組むことは、物事を高速化するためのより良い方法ではないようだということです...

私は他の答えに同意します:mallocを使用した最初の提案はメモリリークへの高速道路です(そしておそらくとにかく遅いです)、あなたが思いついた他の提案ははるかに優れています。コメントで ergosys の提案に従うと、簡単に拡張して優れた C コードを取得できます。

いくつかの数学を使えば、さらに良くなることができます。

まず、整数を計算するために double と floor 呼び出しを使用する必要はありません。M = (nbelts-2) / 10; と書くだけで、床も 0.5 も追加せずに同じ M が得られます。(ヒント: 整数除算は整数に切り捨てます)。

また、常に M < nbelt - M - 2 < nbelt であることに気付いた場合 (まあ、すでにご存知でしょう)、ループを 3 つの独立した部分に分割することで、ループ内の制限のテストを回避できます。これは、in 配列が out 配列と同じ場合でも最適化できます。

関数は次のようになります。

void cos_taper(double *arr_in, double *arr_out, int npts)
{
int i;
int M; 
M = (npts - 2) / 10;

if (arr_out == arr_in) {
    for (i=0; i<M; i++) {
        arr_out[i] *= .5 * (1-cos(i * PI / (M + 1)));
    }
    for (i = npts - M - 2; i<npts; i++) {
        arr_out[i] *= .5 * (1-cos((npts - i - 1) * PI / (M + 1)));
    }
}
else {
    for (i=0; i<M; i++) {
        arr_out[i] = arr_in[i] * (.5 * (1-cos(i * PI / (M + 1))));
    }
    for (; i<npts - M - 2; i++) {
        arr_out[i] = arr_in[i];
    }
    for (; i<npts; i++) {
        arr_out[i] = arr_in[i] * (.5 * (1-cos((npts - i - 1) * PI / (M + 1))));
    }
}
}

これで終わりではなく、もう少し考えれば、より多くの最適化が可能です。たとえば、次のような式は(.5 * (1-cos(i * PI / (M + 1))));、比較的少数の値を取得できるように見えます (i と nbelt の関数であるため、nbelt のサイズによって異なります)。結果は 2 乗則ですが、cos は周期的であるため、その数を再び減らす必要があります)。しかし、すべては必要なパフォーマンスのレベルによって異なります。

于 2010-02-05T23:48:55.803 に答える
0

サブ関数内にメモリを割り当てる場合は、対応するラッパーを作成してクリーンアップするか、割り当てられたメモリを解放するか、関数がメモリを割り当てていることを盲目的に明らかにして、メモリを解放するのを忘れないようにすることをお勧めします.

メモリ フットプリントに関しては、2 番目のアプローチの方がメモリの使用量は少なくなりますが、関数が初期配列のサイズを変更しない場合にのみ機能します。使用状況によっては、これが常に正しいとは限りません。

速度に関しては、関数呼び出し ( do_something)の最後にスタックにプッシュされるポインターが 1 つ少ないため、理論的には 2 番目のアプローチの方が高速です。インライン化を検討することは、すでに検討する必要があります。したがって、関数呼び出しのオーバーヘッドを問題として実際に測定していない限り (プロファイリングによって)、正当な理由 (メモリ フットプリントまたはプロファイリング) がなければ、そのようなマイクロ最適化を気にすることはありません。

于 2010-02-05T18:20:27.317 に答える
0

2 番目のパラメーターを出力パラメーターとして渡すオプションもあります。例えば

int do_something (double * in , double * out) {
   /*
    * Do stuff here
    */
   if (out is modified)
      return 1;
   return 0;
}

または返品なしで同様。

于 2010-02-05T18:16:25.217 に答える
0

malloc を使用しないことで少し時間を節約できますが、タイトなループで do_something を呼び出すと、これがすぐに加算されて顕著な違いが生じる可能性があります。また、double * を返す必要がないため、少し時間を節約できますが、do_something が頻繁に呼び出されると、これが加算される可能性があります。

処理自体に関しては、どちらの場合も double * で動作するため、違いはありません。

提案された方法では動的メモリ割り当てを使用していないため、メモリ リークの可能性はなくなりました。

于 2010-02-05T18:13:37.243 に答える
0

関数の型は、関数とそれを呼び出すコード内の場所との間のインターフェイスを決定します。つまり、選択には重要なコード設計の問題が含まれる可能性があります。原則として、これらは速度よりも考慮する価値があります (ただし、速度の問題が、アプリケーションがスラッシングによって DOS に苦しむほど大きなメモリ リークの 1 つでない場合...)。

2 番目のタイプは、配列を変更する意図がほとんどないことを示しています。1 つ目はあいまいです: 常に配列を変更するかもしれませんし、常に新しく割り当てた結果を提供するかもしれませんし、コードが 1 つを行い、別のことを行う場合もあります。自由には、コードが正しいことを確認するのが困難な地雷原が伴います。このルートに進むと、ポインターの鮮度と共有性に関する不変条件を主張するために、コードに s を自由に散りばめた努力はassert()、デバッグ時に十分な関心を持って報われる可能性があります。

于 2010-02-05T20:41:40.803 に答える