如何优化 C++ 中关于 CPU 和内存的大量映射插入

Question

我正在迭代地图，我需要根据未找到元素的条件（可能是任何其他条件）在该地图上添加元素。

我的主要问题是要添加大量更新，应用程序会占用整个 CPU 和所有内存。

状态Class：

class State {

    int id;

    int timeStamp;

    int state;

}

状态中的方法：

void State::updateStateIfTimeStampIsHigher(const State& state) {
    if (this->id == state.getId() && state.getTimeStamp() > this->getTimeStamp()) {
        this->timeStamp = state.getTimeStamp();
        this->state = state.getState();
    }
}

循环代码：

std::map<int, State> data;

const std::map<int, State>& update;

for (auto const& updatePos : update) {
    if (updatePos.first != this->toNodeId) {
        std::map<int, State>::iterator message = data.find(updatePos.first);
        if (message != data.end() && message->first) {
            message->second.updateStateIfTimeStampIsHigher(updatePos.second);
        } else {
            data.insert(std::make_pair(updatePos.first, updatePos.second));
        }
    }
}

观察 KCacheGrind 数据，看起来 data.insert() 行占用了大部分时间/内存。我是KCacheGrind的新手，但是这条线似乎是成本的72%左右。

你有什么改进的建议吗？

Answer 1

你的问题很笼统，但我看到了一些可以使运行更快的事情：

使用提示插入/放置。当您添加新元素时，将返回其迭代器。假设两个地图都以相同的方式排序，您可以知道最后一个插入的位置，因此查找应该更快（可以在此处使用一些基准测试）。
使用 emplace_hint 以加快插入速度

示例代码在这里：

std::map<int, long> data;

const std::map<int, long> update;
auto recent = data.begin();

for (auto const& updatePos : update) {
    if (updateElemNotFound) { 
        recent = data.emplace_hint(recent, updatePos);
    }
}

此外，如果您想用 CPU 交换内存，您可以使用 unordered_map (Is there any advantage of using map over unordered_map in case of trivial keys?)，但第一个点不再重要。

Answer 2

由于研究了对问题的评论，我找到了令人满意的答案。从 map 更改为 unordered_map 确实有点帮助，但我仍然得到了不满意的结果。

我最终使用了 Google 的 sparsehash，它提供了更好的资源使用，尽管擦除条目（我这样做）有一些缺点。

代码解决方案如下。首先，我包括所需的库：

#include <sparsehash/sparse_hash_map>

然后，我的新 data 定义如下：

struct eqint {
    bool operator()(int i1, int i2) const {
        return i1 == i2;
    }
};

google::sparse_hash_map<int, State, std::tr1::hash<int>, eqint> data;

因为我必须使用 "erase" 我必须在 sparsemap 构造之后执行此操作：

data.clear_deleted_key();
data.set_deleted_key(-1);

最后我的循环代码变化很小：

for (auto const& updatePos : update) {
    if (updatePos.first != this->toNodeId) {
        google::sparse_hash_map<int, State, std::tr1::hash<int>, eqint>::iterator msgIt = data.find(updatePos.first);
        if (msgIt != data.end() && msgIt->first) {
            msgIt->second.updateStateIfTimeStampIsHigher(updatePos.second);
        } else {
            data[updatePos.first] = updatePos.second;
        }
    }
}

在对特定参数下的整个应用程序运行进行更改之前的时间是：

real    0m28,592s
user    0m27,912s
sys     0m0,676s

在对整个应用程序运行在相同具体参数下进行更改后的时间是：

real    0m37,464s
user    0m37,032s
sys     0m0,428s

我运行它与其他案例和结果相似（从定性的角度来看）。系统时间和资源使用（CPU 和内存）减少，用户时间增加。

总的来说，我对权衡感到满意，因为我更关心资源使用而不是执行时间（该应用程序是一个模拟器，它无法在非常重的负载下完成并获得结果，现在可以了）。

如何优化 C++ 中关于 CPU 和内存的大量映射插入

How to optimize heavy map insertion in C++ regarding CPU and memory

c++

unordered-map

c++11