66

驚くほど単純/愚か/基本的な質問ですが、私にはわかりません。関数の最初で長さがわからないC文字列を関数のユーザーに返したいとします。最初は長さの上限しか設定できず、加工によってはサイズが小さくなる場合があります。

問題は、十分なヒープスペース(上限)を割り当ててから、処理中にそれよりもかなり短い文字列を終了することに何か問題がありますか?つまり、割り当てられたメモリの中央に「\ 0」を貼り付けてfree()も、(a。)は正常に機能し、(b。)「\ 0」の後のスペースは重要ではなくなりますか?'\ 0'が追加されると、メモリは返されるだけですか、free()それとも呼び出されるまでそこにホギングスペースがありますか?mallocを呼び出す前に必要なスペースを計算するための事前のプログラミング時間を節約するために、このハンギングスペースをそこに残すのは一般的に悪いプログラミングスタイルですか?

これにコンテキストを与えるために、次のように、連続する重複を削除したいとします。

「HellooOOOo!!」と入力します ->「HelooOo!」を出力

...そして、以下のコードは、操作の結果として生じるサイズを事前に計算し、ヒープサイズを正しくするために2回処理を効果的に実行する方法を示しています。

char* RemoveChains(const char* str)
{
    if (str == NULL) {
        return NULL;
    }
    if (strlen(str) == 0) {
        char* outstr = (char*)malloc(1);
        *outstr = '\0';
        return outstr;
    }
    const char* original = str; // for reuse
    char prev = *str++;       // [prev][str][str+1]...
    unsigned int outlen = 1;  // first char auto-counted

    // Determine length necessary by mimicking processing
    while (*str) {
        if (*str != prev) { // new char encountered
            ++outlen;
            prev = *str; // restart chain
        }
        ++str; // step pointer along input
    }

    // Declare new string to be perfect size
    char* outstr = (char*)malloc(outlen + 1);
    outstr[outlen] = '\0';
    outstr[0] = original[0];
    outlen = 1;

    // Construct output
    prev = *original++;
    while (*original) {
        if (*original != prev) {
            outstr[outlen++] = *original;
            prev = *original;
        }
        ++original;
    }
    return outstr;
}
4

11 に答える 11

51

割り当てられたメモリの中央に「\0」を貼り付けると、

(a。)free()は引き続き正しく機能し、

はい。

(b。)「\ 0」の後のスペースは重要ではなくなりますか?'\ 0'が追加されると、メモリは返されるだけですか、それともfree()が呼び出されるまでそこにホギングスペースがありますか?

依存します。多くの場合、大量のヒープスペースを割り当てると、システムは最初に仮想アドレススペースを割り当てます。ページに書き込むときに、実際の物理メモリが割り当てられます(OSに仮想メモリがある場合は、後でディスクにスワップアウトされる可能性があります)。サポート)。有名なことに、仮想アドレス空間の無駄な割り当てと実際の物理/スワップメモリ​​のこの区別により、スパースアレイはそのようなOSで適度にメモリ効率が高くなります。

さて、この仮想アドレス指定とページングの粒度はメモリページサイズにあります-それは4k、8k、16kかもしれません...?ほとんどのOSには、ページサイズを調べるために呼び出すことができる関数があります。したがって、小さな割り当てをたくさん行う場合は、ページサイズに切り上げるのは無駄です。また、実際に使用する必要のあるメモリの量に比べてアドレススペースが限られている場合は、上記の方法で仮想アドレスに依存します。スケーリングされません(たとえば、32ビットアドレス指定の4GB RAM)。一方、たとえば32GBのRAMで実行されている64ビットプロセスがあり、そのような文字列の割り当てが比較的少ない場合は、膨大な量の仮想アドレススペースを操作する必要があり、ページサイズへの切り上げは行われません。 tはかなりの量になります。

ただし、バッファ全体に書き込んでから、以前の時点でそれを終了すること(この場合、一度書き込まれたメモリにはバッキングメモリがあり、スワップになってしまう可能性があります)と、書き込みのみを行う大きなバッファがあることの違いに注意してください。次に、最初のビットまで終了します(この場合、バッキングメモリは、ページサイズに切り上げられた使用済みスペースにのみ割り当てられます)。

また、多くのオペレーティングシステムでは、プロセスが終了するまでヒープメモリがオペレーティングシステムに戻されない場合があることも指摘しておく価値があります。代わりに、malloc / freeライブラリは、ヒープを拡張する必要があるときにOSに通知します(sbrk()UNIXまたはVirtualAlloc()Windowsでの使用など)。 )。その意味で、free()メモリはプロセスが再利用できるように解放されていますが、他のプロセスが使用できるように解放されているわけではありません。一部のオペレーティングシステムはこれを最適化します。たとえば、非常に大きな割り当てに対して、個別の独立して解放可能なメモリ領域を使用します。

mallocを呼び出す前に必要なスペースを計算するための事前のプログラミング時間を節約するために、このハンギングスペースをそこに残すのは一般的に悪いプログラミングスタイルですか?

繰り返しますが、それはあなたが扱っているそのような割り当ての数に依存します。仮想アドレス空間/RAMに関連して非常に多くの場合、メモリライブラリに、最初に要求されたすべてのメモリが実際に必要なわけではないことを明示的に通知する必要があります。または、実際に基づいて新しいブロックをより厳密に割り当てるためにrealloc()使用することもできます。strdup()ニーズ(当時free()はオリジナル)-malloc / freeライブラリの実装によっては、うまくいくか悪くなるかによって異なりますが、違いによって大きな影響を受けるアプリケーションはほとんどありません。

場合によっては、呼び出し元のアプリケーションが管理する文字列インスタンスの数を推測できないライブラリにコードが含まれていることがあります。そのような場合は、悪化することのない低速な動作を提供することをお勧めします。元の文字列バッファの未知の割合が無駄になるのではなく(病理学的な場合-任意に大きな割り当ての後に0または1文字が使用される)、文字列データを適合させます(追加操作の設定数はbig-O効率に影響しません)。パフォーマンスの最適化として、未使用のスペースが> =使用済みスペースである場合にのみ、メモリを返す必要があります。好みに合わせて調整するか、呼び出し元で構成可能にします。

あなたは別の答えにコメントします:

では、reallocに時間がかかるかどうかを判断するのか、それとも前処理のサイズを決定するのかということです。

パフォーマンスが最優先事項である場合は、そうです。プロファイルを作成する必要があります。CPUに縛られていない場合は、原則として「前処理」ヒットを取得し、適切なサイズの割り当てを実行します。断片化や混乱が少なくなります。これに対抗して、ある関数のために特別な前処理モードを作成する必要がある場合、それはエラーとコードを維持するための余分な「表面」です。(このトレードオフの決定は、asprintf()から独自の実装を行う場合に一般的に必要ですsnprintf()が、少なくともsnprintf()、文書化されたとおりに動作することを信頼でき、個人的にそれを維持する必要はありません)。

于 2012-04-16T09:30:28.443 に答える
35

'\ 0'が追加されると、メモリは返されるだけですか、それともfree()が呼び出されるまでそこにホギングスペースがありますか?

魔法のようなものは何もありません\0realloc割り当てられたメモリを「縮小」する場合は、を呼び出す必要があります。それ以外の場合、メモリは、を呼び出すまでそこに留まりますfree

割り当てられたメモリの中央に「\0」を貼り付けても、(a。)free()は引き続き正しく機能しますか

そのメモリで 何をするにしてfreeも、によって返されるのとまったく同じポインタを渡すと、常に正しく機能しますmalloc。もちろん、あなたがそれの外に書くならば、すべての賭けはオフです。

于 2012-04-16T08:27:35.167 に答える
11

\0mallocは、観点から見るともう1つの文字でありfree、メモリにどのデータを入れるかは関係ありません。したがって、途中で追加する場合でも、まったく追加しないfree場合でも、引き続き機能します。割り当てられた余分なスペースは引き続き存在し、メモリに追加してもすぐにプロセスに戻されることはありません。個人的には、リソースを浪費するだけなので、上限を割り当てるのではなく、必要な量のメモリのみを割り当てることを好みます。\0\0\0

于 2012-04-16T08:30:18.130 に答える
7

これ\0は、文字配列を刺し傷として解釈するための純粋な規則です。これは、メモリ管理とは無関係です。つまり、お金を取り戻したい場合は、に電話する必要がありますrealloc。文字列はメモリを気にしません(多くのセキュリティ問題の原因は何ですか)。

于 2012-04-16T08:29:28.990 に答える
7

malloc()を呼び出してヒープからメモリを取得するとすぐに、そのメモリを使用できます。\ 0を挿入することは、他の文字を挿入することと同じです。このメモリは、解放するか、OSが要求するまで、所有し続けます。

于 2012-04-16T08:29:49.960 に答える
5

mallocはメモリのチャンクを割り当てるだけです..好きなように使用し、最初のポインタ位置から自由に呼び出すのはあなた次第です...途中に「\0」を挿入しても結果はありません...

具体的には、mallocは必要なメモリの種類を認識していません(voidポインタのみを返します)。

0x10から0x19までの10バイトのメモリを割り当てたいと仮定します。

char * ptr = (char *)malloc(sizeof(char) * 10);

5番目の位置(0x14)にヌルを挿入しても、0x15以降のメモリは解放されません。

ただし、0x10から解放すると、10バイトのチャンク全体が解放されます。

于 2012-04-16T08:29:27.643 に答える
4
  1. free()メモリ内のNULバイトで引き続き機能します

  2. free()が呼び出されるまで、または後で割り当てを縮小しない限り、スペースは無駄になります

于 2012-04-16T08:28:02.960 に答える
3

一般的に、メモリはメモリです。何を書いてもかまいません。しかし、それは人種を持っています、またはあなたがフレーバー(malloc、new、VirtualAlloc、HeapAllocなど)を好むなら。これは、メモリの一部を割り当てるパーティが、メモリの割り当てを解除する手段も提供する必要があることを意味します。APIがDLLに入っている場合、それはある種の無料の機能を提供するはずです。もちろん、これは発信者に負担をかけますよね?では、発信者に全負担をかけてませんか?動的に割り当てられたメモリを処理する最良の方法は、自分で割り当てないことです。発信者に割り当ててもらい、あなたに渡します。彼は自分が割り当てたフレーバーを知っており、それを使い終わったときはいつでもそれを解放する責任があります。

発信者はどのくらい割り当てるかをどのように知るのですか?多くのWindowsAPIと同様に、関数はNULLポインターを使用して呼び出されたときに必要なバイト数を返し、NULL以外のポインターが提供されたときにジョブを実行します(アクセシビリティを再確認する場合はIsBadWritePtrを使用します)。

これは、はるかに効率的でもあります。メモリの割り当てには多くの費用がかかります。メモリ割り当てが多すぎると、ヒープの断片化が発生し、割り当てのコストがさらに高くなります。そのため、カーネルモードでは、いわゆる「ルックアサイドリスト」を使用します。実行されるメモリ割り当ての数を最小限に抑えるために、NTカーネルがドライバーライターに提供するサービスを使用して、すでに割り当てて「解放」したブロックを再利用します。呼び出し元にメモリ割り当ての責任を引き継ぐ場合、呼び出し元はスタック(_alloca)から安価なメモリを渡すか、追加の割り当てなしで同じメモリを何度も渡す可能性があります。もちろん気にしませんが、発信者が最適なメモリ処理を担当できるようにします。

于 2012-04-18T03:04:46.640 に答える
1

CでのNULLターミネータの使用について詳しく説明すると、「C文字列」を割り当てることはできません。char配列を割り当てて文字列を格納できますが、mallocとfreeは、要求された長さの配列として表示します。

AC文字列はデータ型ではありませんが、ヌル文字「\0」が文字列ターミネータとして扱われるchar配列を使用するための規則です。これは、長さの値を個別の引数として渡すことなく、文字列を渡す方法です。他のプログラミング言語の中には、文字データとともに長さを格納して単一のパラメーターで文字列を渡すことができる明示的な文字列型を持っているものがあります。

引数を「C文字列」として文書化する関数にはchar配列が渡されますが、nullターミネータがないと配列の大きさを知る方法がないため、存在しない場合はひどく間違ってしまいます。

必ずしも文字列として扱われないchar配列を期待する関数は、常にバッファ長パラメータを渡す必要があることに気付くでしょう。たとえば、ゼロバイトが有効な値であるcharデータを処理する場合、ターミネータ文字として「\0」を使用することはできません。

于 2012-04-18T00:39:24.910 に答える
1

一部のMSWindowsAPIは、自分(呼び出し元)がポインタと割り当てたメモリのサイズを渡す場合に実行できます。サイズが十分でない場合は、割り当てるバイト数が通知されます。十分な場合は、メモリが使用され、結果は使用されたバイト数になります。

したがって、メモリを効率的に使用する方法についての決定は、呼び出し元に任されています。固定の255バイト(Windowsでパスを操作する場合に一般的)を割り当て、関数呼び出しの結果を使用して、さらにバイトが必要かどうか(Win32 APIをバイパスせずにMAX_PATHが255であるためのパスの場合はそうではない)、またはバイトの一部は無視できます...呼び出し元は、メモリサイズとしてゼロを渡し、割り当てる必要のある量を正確に通知することもできます。処理に関しては効率的ではありませんが、スペースに関してはより効率的です。

于 2012-04-18T03:29:21.780 に答える
1

あなたは確かに上限に事前に割り当てて、全部かそれ以下のものを使うことができます。実際にすべてまたはそれ以下のものを使用していることを確認してください。

2つのパスを作成することも問題ありません。

あなたはトレードオフについて正しい質問をしました。

どうやって決めるの?

最初は2つのパスを使用します。理由は次のとおりです。

1. you'll know you aren't wasting memory.
2. you're going to profile to find out where
   you need to optimize for speed anyway.
3. upperbounds are hard to get right before
   you've written and tested and modified and
   used and updated the code in response to new
   requirements for a while.
4. simplest thing that could possibly work.

コードを少し厳しくすることもできます。通常は短い方が良いです。そして、コードが既知の真実を利用すればするほど、私はそれが言うことを実行するのがより快適になります。

char* copyWithoutDuplicateChains(const char* str)
    {
    if (str == NULL) return NULL;

    const char* s = str;
    char prev = *s;               // [prev][s+1]...
    unsigned int outlen = 1;      // first character counted

    // Determine length necessary by mimicking processing

    while (*s)
        { while (*++s == prev);  // skip duplicates
          ++outlen;              // new character encountered
          prev = *s;             // restart chain
        }

    // Construct output

    char* outstr = (char*)malloc(outlen);
    s = str;
    *outstr++ = *s;               // first character copied
    while (*s)
        { while (*++s == prev);   // skip duplicates
          *outstr++ = *s;         // copy new character
        }

    // done

    return outstr;
    }
于 2012-04-23T01:53:16.727 に答える