在 C 中模拟可变大小的结构；对齐，性能问题

Question

可以在 C 中的结构中的任何位置放置自定义长度的数组，但在这种情况下需要额外的 malloc 调用。一些编译器允许在结构中的任何位置使用 VLA，但这不符合标准。所以我决定在标准 C 的结构中模拟 VLA。

我现在确实必须获得最佳性能。 C 中的代码将自动生成，因此在这种情况下可读性或风格并不重要。

在静态大小成员之间将有包含许多自定义大小数组成员的结构。下面是这种结构的一种非常简单的形式。

struct old_a {
    int n_refs;
    void **refs;
    int count;
};

struct old_a *old_a_new(int n_refs, int count) {
    struct old_a *p_a = malloc(sizeof(struct old_a));
    p_a->n_refs = n_refs;
    p_a->refs = malloc(n_refs * sizeof(void *));
    p_a->count = count;
    return p_a;
}

#define old_a_delete(p_a) do {\
    free(p_a->refs);\
    free(p_a);\
} while (0)

可以通过以下方式避免对 refs 的额外 malloc 调用。

#define a_get_n_refs(p_a) *(int *)p_a
#define a_set_n_refs(p_a, rval) *(int *)p_a = rval
#define a_get_count(p_a) *(int *)((char *)p_a + sizeof(int) + a_get_n_refs(p_a) * sizeof(void *))
#define a_set_count(p_a, rval) *(int *)((char *)p_a + sizeof(int) + a_get_n_refs(p_a) * sizeof(void *)) = rval
#define a_get_refs(p_a, i) *(void **)((char *)p_a + sizeof(int) + i * sizeof(void *))
#define a_set_refs(p_a, i, rval) *(void **)((char *)p_a + sizeof(int) + i * sizeof(void *)) = rval

static void *a_new(int n_refs, int count) {
    void *p_a = malloc(sizeof(int) + n_refs * sizeof(void *) + sizeof(int));
    a_set_n_refs(p_a, n_refs);
    a_set_count(p_a, count);
    return p_a;
}

#define a_delete(p_a) do {\
    free(p_a);\
} while (0)

模拟版本在我的机器上似乎运行比带有指针数组的版本快 12~14%。我认为这是由于对 malloc 和 free 的调用次数减半，以及取消引用的次数减少。测试代码如下

int main(int argc, char **argv) {
    const int n_as = atoi(argv[1]) * 10000;
    const int n_refs = n_as;
    const int count = 1;
    unsigned int old_sum = 0;
    unsigned int sum = 0;
    clock_t timer;

    timer = clock();
    struct old_a **old_as = malloc(n_as * sizeof(struct old_a));
    for (int i = 0; i < n_as; ++i) {
        old_as[i] = old_a_new(n_refs, count);
        for (int j = 0; j < n_refs; ++j) {
            old_as[i]->refs[j] = (void *)j;
            old_sum += (int)old_as[i]->refs[j];
        }
        old_sum += old_as[i]->n_refs + old_as[i]->count;
        old_a_delete(old_as[i]);
    }
    free(old_as);
    timer = clock() - timer;
    printf("old_sum = %u; elapsed time = %.3f\n", old_sum, (double)timer / CLOCKS_PER_SEC);

    timer = clock();
    void **as = malloc(n_as * sizeof(void *));
    for (int i = 0; i < n_as; ++i) {
        as[i] = a_new(n_refs, count);
        for (int j = 0; j < n_refs; ++j) {
            a_set_refs(as[i], j, (void *)j);
            sum += (int)a_get_refs(as[i], j);
        }
        sum += a_get_n_refs(as[i]) + a_get_count(as[i]);
        a_delete(as[i]);
    }
    free(as);
    timer = clock() - timer;
    printf("sum = %u; elapsed time = %.2f\n", sum, (double)timer / CLOCKS_PER_SEC);
    return 0;
}

使用 gcc test.c -otest -std=c99 编译：

>test 4
old_sum = 3293684800; elapsed time = 7.04
sum = 3293684800; elapsed time = 6.07

>test 5
old_sum = 885958608; elapsed time = 10.74
sum = 885958608; elapsed time = 9.44

如果我的代码有任何未定义的行为、实现定义的行为等，请告诉我。对于具有健全（符合标准）C 编译器的机器，它意味着 100% 可移植。

我知道内存对齐问题。这些模拟结构的成员只会是int、double和void *，所以我认为不会有对齐问题，但我不确定。此外，尽管模拟结构在我的机器中运行更快（Windows 7 64 位，MinGW/gcc），但我不知道它如何可能运行与其他硬件或编译器。除了检查标准保证行为外，我确实需要有关硬件知识的帮助；哪一个是对机器更友好的代码（一般情况下最好）？

Answer 1

需要注意的一件事 - 在某些系统上，int 将是 2 个字节而不是 4 个字节。在这种情况下，int 只会达到 32767。由于您将输入乘以 10000，因此几乎肯定会在此类机器上引起问题.请改用 long。

Answer 2

It is possible to put arrays with custom length anywhere in a struct in C, but in that case additional malloc calls are required

不，不是

有名的"struct hack"一次性得到数组分配的结构体

struct name {
    int namelen;
    char namestr[1];
};

然后

struct name *makename(char *newname)
{
    struct name *ret = malloc(sizeof(struct name)-1 + strlen(newname)+1);
            /* -1 for initial [1]; +1 for [=11=] */
    if(ret != NULL) {
        ret->namelen = strlen(newname);
        strcpy(ret->namestr, newname);
    }

    return ret;
}

详情见http://c-faq.com/struct/structhack.html

更新

如前所述，数组是结构的最后一个成员，这可能是不合理的限制

更新

在 C99 中，这是现在被祝福的方式，称为 flexible array member，声明应修改为

struct name {
    int namelen;
    char namestr[];
};

然后就可以工作，一次性分配

Answer 3

除非你的程序有相当大的一部分工作是分配和释放这些数据结构，否则你在分配/释放速度上观察到的差异不太可能对程序的整体执行时间产生重大影响。

此外，请注意这两种方法并不等同。后者不产生 struct old_a 的表示，因此使用所产生的数据结构的任何其他代码必须使用提供的访问宏（或等效的）来这样做。

此外，roll-your-own-struct 方法存在潜在的对齐问题。根据各种类型的依赖于实现的大小和对齐要求，它可能会导致伪结构内部指针数组的成员未对齐。如果是这样，则会导致速度下降甚至可能导致程序崩溃。

更一般地说，几乎没有关于类型表示大小的安全假设。肯定 un 可以安全地假设 int 的大小与 void * 的大小相同，或者任何一个与double.

在 C 中模拟可变大小的结构；对齐，性能问题

emulating a variable size struct in C; allignment, performance issues

c

struct

memory-management

memory-alignment