为什么这个程序分配了比必要更多的内存？

Question

我正在用 C 编写一个需要从标准输入读取的程序。我不希望它分配比必要更多的内存，所以我以块的形式读取输入，每次读取新块时 malloc 分配更多内存。

代码如下（allocd 变量仅用于跟踪它分配了多少内存）：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZ 20

int main(int argc, char *argv[])
{
    char *str = malloc(1), *p = NULL;
    *str = '[=10=]';
    char buf[SIZ];
    int bufs = 0;
    int allocd = 0;

    while (p = fgets(buf, sizeof(buf), stdin))
    {
        /* grow str */
        str = realloc(str, bufs * SIZ + SIZ);
        allocd = bufs * SIZ + SIZ;
        strcat(str, buf);
        bufs++;

        if (!p)
            break;
    }

    printf("ALLOC'D: %i", allocd);

    free(str);
}

为了测试，我有一个名为 file.txt 的文件，它有 966 个字符，当我使用 wc:

时你可以看到

$ wc -m file.txt
966 file.txt

问题是我的程序分配的内存字节数似乎比文件中的字符多得多，如您所见：

$ ./code <file.txt
ALLOC'D: 1680

为什么会发生这种情况，我该如何解决？

Answer 1

您正在为您（尝试）阅读的每个行分配一个新的内存块，而不管该行实际有多长。我认为 fgets 是错误的工具，你想要的是 fread 而不是：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZ 20

int main(int argc, char *argv[])
{
    char *str = malloc(1);
    *str = '[=10=]';
    char buf[SIZ];
    int allocd = 0;

    int p;

    // Note: fread() returns size_t number of records read, NOT a char*
    while ((p = fread(buf, 1, sizeof(buf), stdin)))
    {
        str = realloc(str, allocd + p + 1);

        // Concatenate the buffer
        memcpy(str + allocd, buf, p);

        allocd += p;
    }

    str[allocd + 1] = 0;

    printf("ALLOC'D: %i", allocd);

    free(str);
}

Answer 2

I am writing a program in C that needs to read from stdin. I don't want it to allocate more memory than necessary, so I am reading the input in chunks, mallocing more memory each time a new chunk is read.

好吧，你的储蓄意图对程序员来说是个好主意，但你在储蓄方面是错误的，因为你没有考虑很多对你隐藏的东西，但支持有效实施 malloc.

首先是 malloc 需要将额外的内存关联到您请求的块，以维护堆并且不被分配任务弄乱。这意味着，假设它与您请求的每一组内存相关联的结构是一个常量，假设它有 8 个字节大，malloc(1) 将需要使用 8bytes + 1（这是最后一个一个你要求的）来管理你的任务。这意味着如果您进行一百万次这样的分配，您将在您的责任中分配一百万字节，但您将在 malloc 开销中浪费 800 万字节。您拥有活动计数的 malloc 数量。
第二个是，当您 malloc 时，您在总开销中增加了用于记住 malloc 给您的位置的指针的大小。这不在最后一个地方，因为你可以只做一个分配来存储一个数组，在该数组中存储一百万个连续的结构，并只用一个指针引用它们。但是，如果您是那些在对象之间进行引用的指针，这通常是没有用的，您将需要在会计中包含所有这些指针。如果我们将此开销添加到上面分配的 100 万字节中，您将产生 4-8 百万字节的额外开销。这意味着您分配了 100 万字节，但为了维护这些字节，您需要额外的 800 万字节开销，以及隐藏在 malloc 中的 800 万字节开销。
代码中的初始 malloc(1) 可以避免。如果你阅读 the documentation of realloc()，你会发现 realloc 不需要有一个非空指针来操作，如果你传递一个 NULL 指针给它，它的行为就像最初的 malloc() 调用，但包含您需要的实际存储量。

你的代码中的方法是正确的，你一直使用一个活动的 malloc，你决定以 SIZ 的步长增长（大的 SIZ 有利于最小化开销malloc 个调用，但平均而言，您会招致未使用内存的开销——分配的内存，但未填充字符，大约是 SIZ 值的一半更多）由于线长应该遵循有害分布，SIZ 的最佳值将是平均线长（或者如果您使用平均值的两倍更好，以获得更好的性能）

您的代码在更正后将是：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZ 60 /* assumed an average line length of 30 chars */

int main(int argc, char *argv[])
{
    char *str = NULL; /* <<< use null, don't allocate something you don't need */
    char buf[SIZ];
    /* you don't need to know how many times you repeated the loop */
    int allocd = 0; /* allocated capacity */
    int strsz = 0;  /* filled size */

    while (fgets(buf, sizeof(buf), stdin)) /* the p pointer is not necessary */
    {
        /* grow str */
        int read_chars = strlen(buf);           /* (1 & 2) see below */
        printf("read: [%s]\n", buf);
        int pos_to_cp  = strsz;                 /* (3) we need this at the end
*/
        strsz         += read_chars;
        if (strsz >= allocd) {                  /* need to grow */
            printf("growing from %d to %d\n", allocd, allocd + (int)sizeof buf);
            allocd    += sizeof buf;            /* new size */
            str        = realloc(str, allocd);  /* reallocate to allocd */
        }
        strcpy(str + pos_to_cp, buf);           /* (3) see below */
                                                /* (4) see below */
    }

    printf("ALLOC'D: %i\n", allocd);
    printf("string: %s\n", str);

    free(str);
}

(1) read_chars表示读取字符串的大小，它会标记我们需要复制字符串的点在buf.

(2) 这里我们不使用指针变量，因为realloc的结果是，原来的指针可以改变，所以一旦有了新的指针，我们就必须计算复制点。

(3) 我们这里使用指针算法来找到复制字符串的点。通过这种方式，我们总是（以相同的成本）复制一个大小为 sizeof buf 的简单字符串，而不是在迭代缓冲区时附加到越来越长的字符串。

(4) 你不需要检查 if (!p) 因为如果 p 是 NULL 你永远不会进入循环，所以检查是无用的。

你的程序的问题是你假设缓冲区总是被填满，所以你总是需要增长，这是不正确的，而 fgets 在接收到一个 \n 特点。因此并不总是需要缓冲区的增长。我在程序中穿插了一些痕迹，大家可以跟着执行。

为什么这个程序分配了比必要更多的内存？

Why is this program allocating more memory than necessary?

c

malloc