使用宏在C中实现泛型向量.这是一个好主意吗？

Question

我是一名熟悉C和C++的程序员.我在自己的项目中使用过两种语言,但我不知道哪种语言比我更喜欢.

当我在C中编程时,我最想从C++中获取的功能std::vector来自STL(标准模板库)

我仍然没有弄清楚我应该如何在C中表示增长的数组.到目前为止,我在我的项目中重复了我的内存分配代码.我不喜欢代码重复,我知道这是不好的做法所以这对我来说似乎不是一个很好的解决方案.

我前段时间考虑过这个问题,想出了使用预处理器宏实现通用向量的想法.

这是实现的样子:

#ifndef VECTOR_H_
#define VECTOR_H_

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

/* Declare a vector of type `TYPE`. */
#define VECTOR_OF(TYPE) struct { \
    TYPE *data; \
    size_t size; \
    size_t capacity; \
}

/* Initialize `VEC` with `N` capacity. */
#define VECTOR_INIT_CAPACITY(VEC, N) do { \
    (VEC).data = malloc((N) * sizeof(*(VEC).data)); \
    if (!(VEC).data) { \
        fputs("malloc failed!\n", stderr); \
        abort(); \
    } \
    (VEC).size = 0; \
    (VEC).capacity = (N); \
} while (0)

/* Initialize `VEC` with zero elements. */
#define VECTOR_INIT(VEC) VECTOR_INIT_CAPACITY(VEC, 1)

/* Get the amount of elements in `VEC`. */
#define VECTOR_SIZE(VEC) (VEC).size

/* Get the amount of elements that are allocated for `VEC`. */
#define VECTOR_CAPACITY(VEC) (VEC).capacity

/* Test if `VEC` is empty. */
#define VECTOR_EMPTY(VEC) ((VEC).size == 0)

/* Push `VAL` at the back of the vector. This function will reallocate the buffer if
   necessary. */
#define VECTOR_PUSH_BACK(VEC, VAL) do { \
    if ((VEC).size + 1 > (VEC).capacity) { \
        size_t n = (VEC).capacity * 2; \
        void *p = realloc((VEC).data, n * sizeof(*(VEC).data)); \
        if (!p) { \
            fputs("realloc failed!\n", stderr); \
            abort(); \
        } \
        (VEC).data = p; \
        (VEC).capacity = n; \
    } \
    (VEC).data[VECTOR_SIZE(VEC)] = (VAL); \
    (VEC).size += 1; \
} while (0)

/* Get the value of `VEC` at `INDEX`. */
#define VECTOR_AT(VEC, INDEX) (VEC).data[INDEX]

/* Get the value at the front of `VEC`. */
#define VECTOR_FRONT(VEC) (VEC).data[0]

/* Get the value at the back of `VEC`. */
#define VECTOR_BACK(VEC) (VEC).data[VECTOR_SIZE(VEC) - 1]

#define VECTOR_FREE(VEC) do { \
    (VEC).size = 0; \
    (VEC).capacity = 0; \
    free((VEC).data); \
} while(0)

#endif /* !defined VECTOR_H_ */

此代码位于名为的头文件中"vector.h".

请注意,它确实错过了一些功能(比如VECTOR_INSERT和VECTOR_ERASE),但我认为显示我的概念已经足够了.

向量的使用如下所示:

int main()
{
    VECTOR_OF(int) int_vec;
    VECTOR_OF(double) dbl_vec;
    int i;

    VECTOR_INIT(int_vec);
    VECTOR_INIT(dbl_vec);

    for (i = 0; i < 100000000; ++i) {
        VECTOR_PUSH_BACK(int_vec, i);
        VECTOR_PUSH_BACK(dbl_vec, i);
    }

    for (i = 0; i < 100; ++i) {
        printf("int_vec[%d] = %d\n", i, VECTOR_AT(int_vec, i));
        printf("dbl_vec[%d] = %f\n", i, VECTOR_AT(dbl_vec, i));
    }

    VECTOR_FREE(int_vec);
    VECTOR_FREE(dbl_vec);

    return 0;
}

它使用相同的分配规则std::vector(大小开始时1,然后每次需要时加倍).

令我惊讶的是,我发现这段代码的运行速度是使用相同代码的两倍,std::vector 并生成一个较小的可执行文件!(-O3在两种情况下都使用GCC和G ++编译).

我的问题是:

• 这种方法有严重缺陷吗？
• 你会建议在一个严肃的项目中使用它吗？
• 如果没有,那么我希望你解释原因并告诉我什么是更好的选择.

Answer 1

令我惊讶的是,我发现这个代码的运行速度是使用std :: vector编写的相同代码的两倍,并生成一个较小的可执行文件!(在两种情况下使用-O3使用GCC和G ++编译).

C版本比C++版本更快/更小的原因有三个:

1. 的实施new所使用的标准C++库g++是次优的.如果您实现void* operator new (size_t size)呼叫,则malloc()可以获得比内置版本更好的性能.

2. 如果realloc()必须使用新的内存块,它会以旧的方式移动旧数据memmove(),即它忽略数据的逻辑结构并简单地移动这些位.该操作可以很容易地加速到内存总线是瓶颈的程度.std::vector<>另一方面,必须正确地调用构造函数/析构函数,它不能只是调用memmove().在的情况下int和double其归结为移动数据的一个int/ double在一个时间,循环是在用于生成的代码std::vector<>.这不是太糟糕,但它比使用SSE指令更糟糕,而SSE指令是一个好的memmove()实现方式.

3. 该realloc()函数是标准C库的一部分,它与您的可执行文件动态链接.std::vector<>然而,由...生成的内存管理代码正是:生成的.因此,它必须是可执行文件的一部分.

这种方法有严重缺陷吗？

这是一个品味问题,但我认为,这种方法很臭:你的宏定义远离它们的用途,并且它们并不都像简单的常量或内联函数.事实上,它们可疑地像编程语言的元素(即模板),这对预处理器宏来说不是一件好事.尝试使用预处理器修改语言通常是个坏主意.

您的宏实现也存在严重问题:VECTOR_INIT_CAPACITY(VEC, N)宏评估其VEC参数四次,N参数两次评估.现在考虑一下如果进行调用会发生什么VECTOR_INIT_CAPACITY(foo, baz++):存储在capacity新向量字段中的大小将大于为其分配的内存大小.带malloc()调用的行将增加baz变量,并且新值将在第二次递增capacity之前存储在成员中baz.您应该以一种只评估其参数一次的方式编写所有宏.

你会建议在一个严肃的项目中使用它吗？

我想,我不会打扰.该realloc()代码非常琐碎,有些复制不会伤害太大.但同样,您的里程可能会有所不同.

如果没有,那么我希望你解释原因并告诉我什么是更好的选择.

正如我之前所说的,我不打算尝试以std::vector<>(ab)使用预处理器或(ab)使用的方式编写通用容器类void*.

但是我会仔细研究一下我编写的系统上的内存处理:对于许多内核,你不可能NULL从malloc()/ realloc()调用中获得返回值.他们过度承诺他们的记忆,做出他们无法肯定能够实现的承诺.当他们意识到他们无法支持他们的承诺时,他们开始通过OOM杀手开始射击过程.在这样的系统上(linux就是其中之一),你的错误处理毫无意义.它永远不会被执行.因此,您可以避免添加它并将其复制到需要动态增长的数组的所有位置的痛苦.

我在C中的内存重新分配代码通常如下所示:

if(size == capacity) {
    array = realloc(array, (capacity *= 2) * sizeof(*array));
}
array[size++] = ...;

如果没有无功能的错误处理代码,这个代码很短,可以根据需要安全地复制多次.

Answer 2

这种方法有严重缺陷吗？

您正在以与C类型系统交互不良的方式重新发明模板.例如,你的VECTOR类型是匿名的,所以我不能写一个以a VECTOR_OF(int)作为参数的函数.

即使你以某种方式命名你的类型,我也无法编写一个泛型函数 - 这个函数需要一个VECTOR_OF(T)随意的函数T并用它做一些事情.

这些可能不是严重的错误,但是我在C中看到的每个泛型使用宏方法都有一百个这样的小缺点.这一切都是因为语言根本不试图支持泛型编程.

你会建议在一个严肃的项目中使用它吗？

当然; 你可以使用像这样的容器类型开发一个严肃的项目,它们甚至不一定会在你的脸上.你可能需要用流量void *来传递这些东西,这导致一些有点容易出错的演员.