65.9K
CodeProject 正在变化。 阅读更多。
Home

高效的字符串到无符号整数 ID 结构

Stephane Capo
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.58/5 (5投票s)

2020年1月27日

MIT

5分钟阅读

viewsIcon

11067

downloadIcon

99

C++ 优化 map 使用字符串键等

目录

引言

kigs框架的基类（CoreModifiable）通过字符串名称提供对某些成员变量（称为属性）的访问。

// set "IntValue" parameter to 16
instance->setValue("IntValue", 16);
// retrieve value using templated "getValue" method 
int v = instance->getValue<int>("IntValue");
// or with reference parameter
int v1;
if(!instance->getValue("IntValue",v1))
{
    // instance does not own "IntValue" parameter
}

实例工厂也使用字符串名称来标识类。

myApplicationTimer = KigsCore::GetInstanceOf("ApplicationTimer", "Timer");

还有许多其他情况，我们使用字符串来访问存储在映射（有序或无序）中的值。

但出于性能考虑，使用std::string作为映射的键不是一个好的选择。

KigsID结构

我们一直在寻找一种高效的方法将string（const char*或std::string）转换为unsigned int ID。我们使用的字符串通常是一个或两个字母数字单词，并且映射中最多包含几十个值。对于这种用途，我们希望避免（为两个不同的string产生相同的ID）冲突。

这是KigsID struct的代码

struct KigsID
{
    KigsID() = default;
    KigsID(const KigsID& other) = default;
    KigsID(KigsID&& other) = default;

    KigsID& operator=(const KigsID& other) = default;
    KigsID& operator=(KigsID&& other) = default;

    bool operator==(const KigsID& other) const
    {
        return (_id == other._id);
    }

    bool operator<(const KigsID& other) const
    {
        return _id < other._id;
    }
    unsigned int toUInt() const { return _id; }

#ifdef KEEP_NAME_AS_STRING
    template<size_t _Size> KigsID(const char(&aid)[_Size]) : _id_name(aid), 
                                  _id(CharToID::GetID(aid)) {};
    KigsID(const kstl::string& aid) : _id_name(aid), _id(CharToID::GetID(aid)) {};
    KigsID(const kstl::string_view& aid) : _id_name(aid), _id(CharToID::GetID(aid)) {};

    KigsID(unsigned int aid) : _id_name("*unknown*"), _id(aid) {};

    KigsID& operator=(const kstl::string& aid) 
            { _id_name = aid; _id = CharToID::GetID(aid); return *this; };
    template<size_t _Size> KigsID& operator=(const char(&aid)[_Size]) 
            { _id_name = aid; _id = CharToID::GetID(aid); return *this; };

    KigsID& operator=(unsigned int aid) 
            { _id_name = "*unknown*"; _id = aid; return *this; };
    
    // Extra name
    // Don't set this field manually!
    kstl::string _id_name;

#else
    template<size_t _Size>
    KigsID(const char(&aid)[_Size]) : _id(CharToID::GetID<_Size>(aid)) {};
    KigsID(const kstl::string& aid) : _id(CharToID::GetID(aid)) {};
    KigsID(const kstl::string_view& aid) : _id(CharToID::GetID(aid)) {};
    //KigsID(const char*& aid) : _id(CharToID::GetID(aid)) {};
    KigsID(unsigned int aid) : _id(aid) {};

    template<size_t _Size>
    KigsID& operator=(const char(&aid)[_Size]) 
                     { _id = CharToID::GetID<_Size>(aid); return *this; };
    KigsID& operator=(const kstl::string& aid) 
                     { _id = CharToID::GetID(aid); return *this; };
    KigsID& operator=(const kstl::string_view& aid) 
                     { _id = CharToID::GetID(aid); return *this; };
    //KigsID& operator=(const char*& aid) { _id = CharToID::GetID(aid); return *this; };
    KigsID& operator=(unsigned int aid) { _id = aid; return *this; };

#endif

    // Don't set this field manually!
    unsigned int _id;
};

定义KEEP_NAME_AS_STRING是在调试模式下设置的，这样在调试时可以轻松地看到用于初始化ID的原始string。

这里有一个示例代码来说明这一点

void    Sample::KigsIDTest(const KigsID& id)
{
    printf("KigsID unsigned int value = %08x\n", id._id);
    printf("sizeof(KigsID) = %d\n", sizeof(KigsID));
}

KigsIDTest方法是这样调用的

KigsIDTest("HelloWorld");

这是在Visual Studio C++调试器中调试模式下的id变量检查

如果未定义KEEP_NAME_AS_STRING，则只能使用unsigned int _id成员。

关注点

因此，现在有趣的部分是，在发布模式下，并激活优化后，调用KigsIDTest("HelloWorld");会输出以下结果：

所以sizeof(KigsID)是4个字节（32位unsigned int）。

另一个有趣的事情是，在这里，"HelloWorld"string到int的转换是**在编译时**求值的，如果我们查看反汇编代码，就可以看到这一点。

对于Visual C++编译器（x86构建），长度最多为19个字符的const char*字符串是这种情况。

对于更长的string或std::string，ID是在运行时使用对4字节包的几次逻辑运算（XOR，ROL）来求值的。

基准测试

为了测试该结构的性能，我们设置了一个小型的基准测试代码。对于我们对它的使用，关键部分是访问映射值，因此基准测试侧重于这一点。

基准代码

template<typename maptype, typename vectorkeys>
double TestKigsIDPerfs::testUMap()
{
    // get start time
    double startTime = mApplicationTimer->GetTime();

    // create empty unordered_map 
    maptype                                    testMap;
    // create a vector containing all the keys we are going to test
    std::vector<vectorkeys>                    testVector;
    // some "similar keys"
    testVector.push_back("testString1");
    testVector.push_back("testString2");
    testVector.push_back("testString3");
    testVector.push_back("testString4");
    testVector.push_back("testString5");
    // some random keys
    testVector.push_back("ajzhgjhsqfd");
    testVector.push_back("xcwvksqjdfh");
    testVector.push_back("nzsbdocdsdf");
    testVector.push_back("zieulkjvsqd");
    testVector.push_back("poizerbhncs");
    // some incremental length keys
    testVector.push_back("az");
    testVector.push_back("aze");
    testVector.push_back("azer");
    testVector.push_back("azert");
    testVector.push_back("azerty");
    testVector.push_back("azertyu");
    testVector.push_back("azertyui");
    testVector.push_back("azertyuio");
    testVector.push_back("azertyuiop");
    testVector.push_back("azertyuiopq");

    // fill map, associating a unsigned int to each key 
    for (unsigned loop = 0; loop < testVector.size(); loop++)
    {
        testMap[testVector[loop]] = (loop + 1) * (loop + 1);
    }

    // test a lot of map access
    int vectorSize = testVector.size();
    unsigned int voidComputation = 0;
    for (unsigned int accessloop = 0; accessloop < (1000 * 1000 * 100); accessloop++)
    {
        // some computation, just to be sure the compiler really access the map
        voidComputation = voidComputation << 2;
        voidComputation ^= testMap[testVector[accessloop % vectorSize]];
    }
    // get end time
    double endTime = mApplicationTimer->GetTime();

    // print computation result, should be the same for all the different tests
    printf("voidComputation = %d\n", voidComputation);

    // return benchmark time
    return endTime - startTime;
}

我们测试了两种无序映射：std::unordered_map和robin_hood::unordered_map（https://github.com/martinus/robin-hood-hashing）。

我们还测试了默认哈希方法，以及仅返回ID本身的KigsIDHash方法。

struct KigsIDHash
{
    std::size_t operator()(const KigsID& k) const
    {
        return k._id;
    }
};

这是所有不同的基准测试调用：

    // unordered map
    double ti=testUMap<std::unordered_map<std::string,unsigned int>, std::string >();
    printf("Unordered map with string map keys and string access: %f s\n", ti);

    ti = testUMap<std::unordered_map<KigsID, unsigned int>, std::string >();
    printf("Unordered map with KigsID map keys and string access: %f s\n", ti);

    ti = testUMap<std::unordered_map<KigsID, unsigned int>, KigsID>();
    printf("Unordered map with KigsID map keys and KigsID access: %f s\n", ti);

    ti = testUMap<std::unordered_map<KigsID, unsigned int, KigsIDHash>, KigsID>();
    printf("Unordered map with KigsID map keys, KigsID access and KigsIDHash: %f s\n", ti);

    // robin hood unordered map
    ti = testUMap<robin_hood::unordered_map<std::string,unsigned int>, std::string>();
    printf("Robin hood unordered map with string map keys and string access: %f s\n", ti);

    ti = testUMap<robin_hood::unordered_map<KigsID, unsigned int>, std::string>();
    printf("Robin hood unordered map with KigsID map keys and string access: %f s\n", ti);

    ti = testUMap<robin_hood::unordered_map<KigsID, unsigned int>, KigsID>();
    printf("Robin hood unordered map with KigsID map keys and KigsID access: %f s\n", ti);

    ti = testUMap<robin_hood::unordered_map<KigsID, unsigned int, KigsIDHash>, KigsID>();
    printf("Robin hood unordered map with KigsID map keys, 
            KigsID access and KigsIDHash: %f s\n", ti);

构建基准测试

为了方便构建和测试代码（需要Git、Microsoft Visual Studio和CMake，请参阅Kigs框架的入门指南或观看此视频教程），请克隆https://github.com/Kigs-framework/kigs。然后将TestKigsIDPerfs.zip下载并解压到kigs/projects目录。

用您喜欢的文本编辑器打开kigs/projects/CMakeLists.txt，并添加以下行：

add_subdirectory(TestKigsIDPerfs)

保存并关闭CMakeLists.txt。

解决方案生成脚本：kigs/scripts/generateWinCMake.bat现在支持**Visual Studio 2022**。如果您使用Visual Studio 2019，请编辑generateWinCMake.bat并将"Visual Studio 17 2022"更改为"Visual Studio 16 2019"后启动脚本。

转到kigs/scripts目录并运行generateWinCMake.bat脚本（双击它）。

然后转到Build/solutionWinCMake/kigs/projects/TestKigsIDPerfs目录，双击TestKigsIDPerfs.sln在Visual Studio中打开解决方案。

在Visual Studio中，将TestKigsIDPerfs设置为"启动项目"，并将StaticRelease设置为构建配置。生成并运行。

基准测试结果

基准测试是在完全优化下构建的，并在以下平台上运行：

  • 一台Windows 10 PC（Core i7-4790K 4.00 Ghz），使用Visual Studio 2019编译器构建。
  • 同一台Windows 10 PC上的Firefox（HTML5），使用WSL下的Emscripten构建。
  • 一台Android Samsung Galaxy Tab S2（armebiv7a），使用Visual Studio 2019下的CLANG 5.0编译器构建。
  • Hololens 2（Arm64），使用Visual Studio 2019构建。

所有时间单位均为秒。

  Win10 HTML5 Android Hololens 2
std::unordered_map，string键，string访问，std::hash 2.765395 100% 5.633000 100% 25.914861 100% 8.705835 100%
std::unordered_map，KigsID键，string访问，std::hash 1.785608 155% 2.444000 230% 19.587981 132% 5.171553 168%
std::unordered_map，KigsID键，KigsID访问，std::hash 0.722537 383% 1.947000 289% 17.237732 150% 2.843732 306%
std::unordered_map，KigsID键，KigsID访问，KigsIDHash 1.002372 276% 1.916000 294% 17.229091 150% 2.866783 304%
robin_hood::unordered_map，string键，string访问，robin_hood::hash 3.930436 70% 4.103000 137% 15.034525 172% 7.228063 120%
robin_hood::unordered_map，KigsID键，string访问，robin_hood::hash 2.069901 134% 2.766000 204% 10.752449 241% 4.625862 188%
robin_hood::unordered_map，KigsID键，KigsID访问，robin_hood::hash 1.138290 243% 1.638000 344% 8.765440 296% 2.956348 294%
robin_hood::unordered_map，KigsID键，KigsID访问，KigsIDHash 1.142882 242% 1.647000 342% 8.845147 293% 2.946729 295%

结论

在Kigs框架的用法中，将KigsID结构用作无序映射的访问键始终是一个好选择。相反，使用KigsIDHash似乎是个坏主意。

在std::unordered_map和robin_hood::unordered_map之间选择很大程度上取决于编译器和目标平台。

如果您想更仔细地了解KigsID代码，可以在此处找到所有Kigs框架代码：

KigsID结构定义在此处：

您还可以开始阅读CodeProject上的Kigs框架系列文章的介绍：

 

    并在Twitter或YouTube上关注我们！

历史

  • 2020年1月27日：初始版本
  • 2020年2月19日：添加了目录、基准测试和源代码下载
  • 2022年6月21日：更改了Kigs-framework GitHub仓库的链接，修复了代码并添加了视频教程链接
© . All rights reserved.