c++ - std::map(和系列)查找性能问题

Question

我正在编写一个位域抽象类，它环绕一 block 32 位内存 (u32 = unsigned int) 并提供对该内存中各个位或范围的访问。

为了实现这一点，我使用了一个 std::map，其中唯一键是指向表示助记符的 C 字符数组的指针(不是 std::string)，值为包含位域属性(例如助记符、起始位置、长度、初始值和字段值)的结构。所有这些属性都是常量并在启动时定义，除了仅在基础 u32 值更改时更改的字段值。(另请注意:我刚刚将助记符指针值重新用作唯一键)。

这在模拟器中使用，其中每秒调用多次返回位域值(只读)的 getBitfieldValue()。

在 VS 2015 update 3 下编译和分析代码(使用 -O2 和我能找到的任何速度优化)，它显示 getBitfieldValue() 函数，并通过扩展 std::find() 占用了大约 60-70% 的总 CPU 时间……太慢了。

我尝试过使用其他 map 实现，例如 Boost::flat_map、google::dense_hash_map 或 std::unordered_map，以及它们有些帮助，但最终还是太慢了 (~50-60%)。

我的猜测是我将映射用于错误的目的，但考虑到只有 5-20 个位域映射(小查找大小)，我不确定...它似乎太慢了。大部分时间也会花在查找同一字段上。

相关类源代码可以在这里找到:BitfieldMap32

map 在启动时如何初始化的示例(仅运行一次):

struct Fields
{
    static constexpr char * ADDR = "ADDR";
    static constexpr char * SPR = "SPR";
};
ExampleClass() // constructor
{
    // registerField(mnemonic, start position, length, initial value)
    registerField(Fields::ADDR, 0, 31, 0);
    registerField(Fields::SPR, 31, 1, 0);
}

以及如何访问字段值(只读):

// getFieldValue definition.
const u32 & BitfieldMap32_t::getFieldValue(const char* fieldName)
{
    return mFieldMap.find(fieldName)->second.mFieldValue;
}

// Field access.
const u32 value = ExampleClassPointer->getFieldValue(Fields::ADDR)

关于如何减少查找时间的任何想法？还是我需要一起更改实现？

Answer 1

IIUC，使用字典(std::map 或 std::unordered_map)是一个巨大的矫枉过正。也许您应该使用以下内容:

1. 这个类应该只是一个整数内部存储的包装器(或者至多是一个 std::bitset)。

2. 助记符应该是enum，而不是std::string。

3. 在内部，有一个 std::vector 有效地将每个 enum 值映射到 bitmask . (如果您使用的是 c++11 enum，请参阅 here 如何将 enum 值转换为 std::vector).

4. 每个操作应该只需要助记符，通过索引找到位掩码，并将其应用于内部存储。