高效计算两个巨大向量中每个条目的总和

问题描述 投票:0回答:1

我有两个包含一组数字的大向量。典型情况下,每个向量中大约有 150,000 个数字,范围从 0 到大约 2,000,000。我想尽快计算第三个向量,其中包含第一个向量中每个数字与第二个向量中每个数字的所有总和。

我当前的代码:

#include <vector>

namespace
{
    // This function is purely for benchmarking, the numbers are retrieved
    // from other sources in reality, and have the following properties:
    // - The numbers in the vector are sorted
    // - The numbers are guaranteed unique
    std::vector<uint32_t> populate(size_t pRange, size_t pValues)
    {
        std::vector<uint32_t> result;
        std::srand((unsigned)std::time(0));
        result.reserve(pValues);
        for (uint32_t i = 0; i < pValues; i++)
        {
            uint32_t randomValue = std::rand() % pRange;
            result.push_back(randomValue);
        }
        std::sort(result.begin(), result.end());
        return result;
    }
}

// The function to profile, currently complexity O(n^2)
void calculateVectorSums(std::vector<uint32_t> const & pVector1,
                         std::vector<uint32_t> const & pVector2,
                         std::vector<uint8_t> & pResult)
{
    pResult.resize(pVector1.back() + pVector2.back() + 1, 0);
    for (auto nr1 : pVector1)
    {
        for (auto nr2 : pVector2)
        {
            pResult[nr1+nr2] = 1;
        }
    }
}

int main(void)
{
    auto vector1 = populate(2000000, 150000);
    auto vector2 = populate(2000000, 150000);

    // Loop for averaging the profiling numbers
    std::vector<uint8_t> output;
    calculateVectorSums(vector1, vector2, output);
}

正如预期的那样,大部分时间都花在

pResult[nr1+nr2] = 1;
线上。我怀疑缓存未命中会导致巨大的性能损失。

我尝试使用位集作为目标缓冲区,但由于位操作的开销,速度慢了大约 2 倍。

我强烈怀疑重新组织加法的顺序可能会导致整体执行速度更快,或者可能有硬件扩展(GPU可用)可以加速计算,但我在这方面的经验很少领域。

c++ optimization
1个回答
0
投票

我没有看到在逻辑方面改进算法的选项(提高时间复杂度)。

我能看到的唯一改进空间是使代码对缓存更加友好。 我的想法是改变迭代的完成方式。从第一个向量中获取子范围并使用它来生成结果,然后更新子范围::

template<size_t SecSize>
void lessCacheMiss(std::vector<uint32_t> const & pVector1,
                         std::vector<uint32_t> const & pVector2,
                         std::vector<uint8_t> & pResult)
{
    auto n = pVector1.size();
    auto it = pVector1.begin();
    for (; it + SecSize < pVector1.end(); it += SecSize) {
        for (auto nr2 : pVector2)
        {
            for (auto nr1 : std::ranges::subrange(it, it + SecSize))
            {
                pResult[nr1+nr2] = 1;
            }
        }
    }

    for (auto nr2 : pVector2)
    {
        for (auto nr1 : std::ranges::subrange(it, pVector1.end()))
        {
            pResult[nr1+nr2] = 1;
        }
    }
}

结果应该是相同的(请编写单元测试来证明此代码是正确的)。

执行时间也有显着改善: Performance results

https://quick-bench.com/q/xtyp6mvP8e94Qxtw7LtYtkKHcKM

在不同的机器上做一些实验来选择

SecSize
的最佳值。 还有进步的空间。

IMO,您可以尝试使用一些并行性来进一步改进这一点。问题是如何在不需要同步的情况下做到这一点?

© www.soinside.com 2019 - 2024. All rights reserved.