c - 在 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 代替。