另一个向量与动态分配的数组

Question

人们经常读到动态分配的数组和std::vector之间几乎没有性能差异。

以下是欧拉测试项目问题 10 的两个版本，有两个版本：

与std::vector ：

const __int64 sum_of_primes_below_vectorversion(int max) 
{
        auto primes = new_primes_vector(max);
        __int64 sum = 0;
        for (auto p : primes) {
                sum += p;
        }
        return sum;
}
const std::vector<int> new_primes_vector(__int32 max_prime)
{
        std::vector<bool> is_prime(max_prime, true);
        is_prime[0] = is_prime[1] = false;
        for (auto i = 2; i < max_prime; i++) {
                is_prime[i] = true;
        }
        for (auto i = 1; i < max_prime; i++) {
                if (is_prime[i]) {
                        auto max_j = max_prime / i;
                        for (auto j = i; j < max_j; j++) {
                                is_prime[j * i] = false;
                        }
                }
        }
        auto primes_count = 0;
        for (auto i = 0; i < max_prime; i++) {
                if (is_prime[i]) {
                        primes_count++;
                }
        }
        std::vector<int> primes(primes_count, 0);
        for (auto i = 0; i < max_prime; i++) {
                if (is_prime[i]) {
                        primes.push_back(i);
                }
        }
        return primes;
}

请注意，我还通过调用默认构造函数 std::vector 来测试版本版本，并且没有预先计算其最终大小。

下面是阵列版本：

const __int64 sum_of_primes_below_carrayversion(int max)
{
        auto p_length = (int*)malloc(sizeof(int));
        auto primes = new_primes_array(max, p_length);
        auto last_index = *p_length - 1;
        __int64 sum = 0;
        for (int i = 0; i < last_index; i++) {
                sum += primes[i];
        }
        free((__int32*)(primes));
        free(p_length);
        return sum;
}

const __int32* new_primes_array(__int32 max_prime, int* p_primes_count)
{
        auto is_prime = (bool*)malloc(max_prime * sizeof(bool));
        is_prime[0] = false;
        is_prime[1] = false;
        for (auto i = 2; i < max_prime; i++) {
                is_prime[i] = true;
        }
        for (auto i = 1; i < max_prime; i++) {
                if (is_prime[i]) {
                        auto max_j = max_prime / i;
                        for (auto j = i; j < max_j; j++) {
                                is_prime[j * i] = false;
                        }
                }
        }
        auto primes_count = 0;
        for (auto i = 0; i < max_prime; i++) {
                if (is_prime[i]) {
                        primes_count++;
                }
        }
        *p_primes_count = primes_count;
        int* primes = (int*)malloc(*p_primes_count * sizeof(__int32));
        int index_primes = 0;
        for (auto i = 0; i < max_prime; i++) {
                if (is_prime[i]) {
                        primes[index_primes] = i;
                        index_primes++;
                }
        }
        free(is_prime);
        return primes;
}

这是使用 MVS2013 编译器编译的，优化标志为 O2。我真的看不出应该有什么大区别，因为移动语义（允许按值返回大向量而不复制）。

以下是输入为 2E6 的结果：

C array version
avg=    0.0438
std=    0.00928224
vector version
avg=    0.0625
std=    0.0005
vector version (no realloc)
avg=    0.0687
std=    0.00781089

统计数据涉及10项试验。我认为这里有很多差异。是因为我的代码中的某些内容需要改进吗？

编辑：在更正我的代码（以及另一项改进）后，这是我的新结果：

C array version
avg=    0.0344
std=    0.00631189
vector version
avg=    0.0343
std=    0.00611637
vector version (no realloc)
avg=    0.0469
std=    0.00997447

这证实了与 C 数组相比没有std::vector的惩罚（并且应该避免重新分配）。

Answer 1

向量和动态数组之间不应该有性能差异，因为向量是动态数组。

代码中的性能差异来自于您实际上在向量和数组版本之间执行不同操作的事实。例如：

    std::vector<int> primes(primes_count, 0);
    for (auto i = 0; i < max_prime; i++) {
            if (is_prime[i]) {
                    primes.push_back(i);
            }
    }
    return primes;

这将创建一个大小为 primes_count 的向量，全部初始化为 0，然后将一堆素数推回它。但它仍然从primes_count 0开始！因此，从初始化和迭代的角度来看，这都是浪费内存。您要做的是：

std::vector<int> primes;
primes.reserve(primes_count);
// same push_back loop
return primes;

同样，这个块;

    std::vector<int> is_prime(max_prime, true);
    is_prime[0] = is_prime[1] = false;
    for (auto i = 2; i < max_prime; i++) {
            is_prime[i] = true;
    }

你构造了一个初始化为 true 的 max_prime 个整数的向量...然后再次将它们中的大多数分配给 true。您在此处执行两次初始化，而在数组实现中，您只执行一次。您应该删除此循环。

我敢打赌，如果你解决了这两个问题——这将使这两种算法具有可比性——你会得到相同的性能。