时间戳

首页 > 解决方案 > 如何使用并行性来提高我的代码的性能？（尝试了一些东西）

c++ - 如何使用并行性来提高我的代码的性能？（尝试了一些东西）

问题描述

所以问题来了：我有一个自定义对象的向量，我需要用向量中每个唯一的对象组合计算一些东西，如果结果是某个值，我需要构建一个 2 路关联列表。这是我按顺序执行的操作，并且有效：

#include <itertools/combinations.hpp> //I'm using cppitertools library (installed through vcpkg)

class MyClass{
private:
    int x;
    std::string abc;
public:
    MyClass();
    GetX();
}

...

std::vector<MyClass> _myObjects;
std::unordered_map<const MyClass*, std::vector<const MyClass*>> _relationships;//list all other objects in relation with a specific object, based on custom computation on all possible combination

...
int ComputeRelation(const MyObject* obj0, const MyObject* obj1){
    //some random stuff
    return obj0->GetX() + obj1->GetX();
}
...

void BuildRelationship(){
    for(auto& combination : iter::Combination(_myObject,2)){
        //combination is a pair of MyObject
        if(ComputeRelation(combination[0],combination[1]) == 1){
            //build 2-way associative list
            _relationships[combination[0]].push_back(combination[1]);
            _relationships[combination[1]].push_back(combination[0]);
        }
    }
}

我最初到处都有引用而不是指针，但是 unordered_map 在使用引用时会引发错误。

现在，这工作正常，但我想通过并行化循环来加速它，因为组合的数量可以很快变得非常大（100 万个对象的数据集有5000 亿个组合）

这是我尝试过的：

我没有找到一种方法来简单地拆分组合集，而不必先将所有组合推入另一个容器（我认为这是低效的）

我觉得我错过了一些明显、简单的方法来做到这一点，但我的大脑有点卡住了。

谢谢！

编辑：我最初只想保留一个包含 的所有结果的地图ComputeRelation，但是有 5000 亿个元素，我达到了疯狂的 RAM 使用量（>>100G），这就是为什么我决定只保留具有特定值的关系兴趣

更新＃1：所以我想我找到了解决方法。我向 MyClass 添加了一个成员属性，用作 ID 或键。我使用了一个简单的散列库来散列我的类的一些属性（将字符串转换为 int）。然后，我没有构建指针容器，而是构建 int 容器，并在需要时使用哈希值从映射中检索实际对象，如下所示：

#include <itertools/combinations.hpp> //I'm using cppitertools library (installed through vcpkg)

class MyClass{
private:
    int x;
    std::string abc;
    uint64_t hash;
public:
    MyClass(int x, string abc){
        this.hash=SomeHashFn(abc);
    };
    GetX();
}

...

std::vector<uint64_t> _myHashes;//keeps order and duplicates
std::unordered_map<uint64_t, MyObject> _myObjects;
std::unordered_map<uint64_t, std::vector<uint64_t>> _relationships;//list all other objects in relation with a specific object, based on custom computation on all possible combinations

...
int ComputeRelation(const MyObject& obj0, const MyObject& obj1){
    //some random stuff
    return obj0.GetX() + obj1.GetX();
}
...

void BuildRelationship(){
    auto combinations = iter::Combination(_myHashes,2);
    std::for_each(std::execution::par, combinations.begin(), combinations.end(), [&](auto combination){
        //combination is a pair of hash
        MyObject obj0=_myObjects[combination[0]];
        MyObject obj1=_myObjects[combination[1]];
        if(ComputeRelation(obj0, obj1) == 1){
            //build 2-way associative list using hashes
            _relationships[combination[0]].push_back(combination[1]);
            _relationships[combination[1]].push_back(combination[0]);
        }
    }
}

更新＃2：没关系更新＃1，由于iter::Combination返回的迭代器（我需要向前或更强std::for_each），我仍然无法并行处理组合。所以我尝试创建一个包含所有组合的向量，但又遇到了 RAM 问题。一个快速的计算告诉我，我需要大约 80Gb 来存储这个向量。

标签： c++multithreadingiteratorcombinations

解决方案

  1. std::unordered_map可能非常慢（在今天可用的大多数实现中）。尝试另一个容器，例如dense_hash_map.

  2. 您可以通过键的某些属性“分片”结果映射。例如，给定一个类型为 的键MyClass*，您可以散列指针值并使用hash % n，其中n是分片的数量，作为子映射向量的索引。然后，您将能够在并行线程中填充n子映射（理想情况下= 可用处理器的数量）。 缺点是查找变得有点复杂 - 您还需要在查找期间进行计算。您可以使用散列函数来找到性能和均匀性之间的最佳平衡。例如，可能是一个足够好但非常快​​的哈希函数。nn
    hash % n(uintptr_t)key >> 4

推荐阅读