技术控

    今日:10| 主题:49195
收藏本版 (1)
最新软件应用技术尽在掌握

[其他] 6 个技巧,提升 C++11 的 vector 性能

[复制链接]

立即注册CoLaBug.com会员,免费获得投稿人的专业资料,享用更多功能,玩转个人品牌!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
Vector 就像是 C++ STL 容器的瑞士军刀。Bjarne Stoutsoup 有一句话 – “一般情况下,如果你需要容器,就用 vector”。像我们这样的普通人把这句话当作真理,只需要照样去做。然而,就像其它工具一样,vector 也只是个工具,它能提高效率,也能降低效率。
    这篇文章中我们可以看到 6 种优化使用 vector 的方法。我们会在最常见的使用 vector 的开发任务中看到有效的方法和无效的方法,并以此衡量有效使用 vector 会带来怎样的性能提升,并试图理解为什么能得到这样的性能提升。
        性能测试的搭建和方法:   

   
          
  •         所有测试都在我的 Surface Book 中运行,这台笔记本拥有主频 2.6Ghz 的酷睿 i7 处理器,8 GB 内存,安装了 Windows 10 操作系统并使用 VS2015 C++ 编译器编译运行。
          
  •         我们会使用 Stopwatch。这个工具由 Kjell 创建,在          https://github.com/KjellKod/Stopwatch可以找到。        
          
  •         我们会运行每个测试 100 次,然后计算平均运行时间来作为依据。运行测试的代码在          这里。你可以自由下载,用于在你自己的系统中评估 vector 的性能。那里提供的代码段只反映了一次循环,这让事件变得简单。        
          
  •         我们在 vector 中存入 TestStruct 结构的数据,并使用 FillVector() 来填充 vector。它们的定义如下。
       
   
  1. // Test struct to be inserted/removed from vector
  2. struct BigTestStruct
  3. {
  4.   int iValue = 1;
  5.   float fValue;
  6.   long lValue;
  7.   double dValue;
  8.   char cNameArr[10];
  9.   int iValArr[100];
  10. };
复制代码
  
  1. // Helper function to populate the test vectors
  2. void FillVector(vector<BigTestStruct>& testVector)
  3. {
  4.   for (int i = 0; i < 10000; i++)
  5.   {
  6.     BigTestStruct bt;
  7.     testVector.push_back(bt);
  8.   }
  9. }
复制代码
   马上开始在 C++ 11 中优化      vector 用法的介绍。   
        #1 提前分配足够的空间以避免不必要的重新分配和复制周期   

    程序员喜欢使用 vector,因为他们只需要往向容器中添加元素,而不用事先操心容器大小的问题。但是,如果由一个容量为 0 的 vector 开始,往里面添加元素会花费大量的运行性能。如果你之前就知道 vector 需要保存多少元素,就应该提前为其分配足够的空间。
    这里有一个简单的示例,往 vector 里添加 1 万个测试结构的实例——先进行不预分配空间的测试再进行有预分配的测试。
   
  1. vector<BigTestStruct> testVector1;
  2. vector<BigTestStruct> testVector2;
  3. sw.Restart();
  4. FillVector(testVector1);
  5. cout << "Time to Fill Vector Without Reservation:" << sw.ElapsedUs() << endl;
  6. sw.Restart();
  7. testVector2.reserve(10000);
  8. FillVector(testVector2);
  9. cout << "Time to Fill Vector With Reservation:" << sw.ElapsedUs() << endl;
复制代码
   在我的计算机中,未预分配空间的情况用了 5145 微秒(us),而预分配了空间的情况下只用了 1279 微秒,性能提高了 75.14%!!!
        这个情况在 Scott Meyers 的书中得到了很好的解释,这本书叫      Effective STL-      50条有效使用STL的经验:   
    “对于 vector 和 string,在需要更多空间的时候,会做与 realloc 等效的事情。这种类似 realloc 的操作有4个步骤:
    1. 分别一个新的内存块,其容量是容器当前容量的数倍。多数实现中,vector 和 string 容量的提升因子在 1.5 和 2 之间。
    2. 从容器原来占用的内存中将元素拷贝到新分配的内存中。
    3. 释放原有内存中的对象。
    4. 释放原有内存。
          有了所有这些操作:分配、回收、拷贝和释放,如果说这些步骤(对于性能)极其昂贵,你一点都不应该感到惊讶。当然,你肯定不希望频繁的进行这样的操作。如果这还没有打动你,那么想想每次进行这些步骤的时候,vector 和 string 中所有的迭代器、指针和引用都会失效。这意味着一个简单的插入操作,对于其它使用了当前 vector 或 string 中的迭代器、指针或引用的数据结构,都有可能引起对它们进行更新。         
        #2使用 shrink_to_fit() 释放 vector 占用的内存, – clear() 或 erase() 不会释放内存。   

    与大家所想的相反,使用 erase() 或 clear() 从 vector 中删除元素并不会释放分配给 vector 的内存。做个简单的实验就可以证明这一点。我们往一个 vector 中添加 100 个元素,然后在这个 vector 上调用 clear() 和 erase()。然后我们可以让 capacity() 函数告诉我们为这个容器分配的内存可以存入多少元素。
   
  1. FillVector(testVector1);
  2. size_t capacity = testVector1.capacity();
  3. cout << "Capacity Before Erasing Elements:" << capacity << endl;
  4.   
  5. testVector1.erase(testVector1.begin(), testVector1.begin() + 3); //
  6. capacity = testVector1.capacity();
  7. cout << "Capacity After Erasing 3 elements Elements:" << capacity << endl;
  8. testVector1.clear();
  9. capacity = testVector1.capacity();
  10. cout << "Capacity After clearing all emements:" << capacity << endl;
  11. testVector1.shrink_to_fit();
  12. capacity = testVector1.capacity();
  13. cout << "Capacity After shrinking the Vector:" << capacity << endl;
复制代码
   下面是输出:
   
  1. Capacity Before Erasing Elements:12138
  2. Capacity After Erasing 3 elements Elements:12138
  3. Capacity After clearing all emements:12138
  4. Capacity After shrinking the Vector:0
复制代码
   从上面的输出可以看到,erase() 或 clear() 不会减少 vector 占用的内存。如果在代码中到达某一点,不再需要 vector 时候,请使用      std::vector::shrink_to_fit()方法释放掉它占用的内存。   
        请注意,shrink_to_fit() 可能没有被所有编译器供应商完全支持。这种情况下,可以使用“Swap 惯用法”来清空 vector,代码如下:
            container<T>( c ).swap( c );            // shrink-to-fit 惯用法,用于清空存储空间   
            container<T>().swap( c );          // 用于清空所有内容和存储空间的惯用法     
    如果你对此感兴趣,请查看“      C++ Coding Standards: 101 Rules, Guidelines, and Best Practices”一书的条款# 82,其中有针对 swap 惯用法的细节介绍。   
        #3在填充或者拷贝到 vector 的时候,应该使用赋值而不是 insert() 或push_back().   

    从一个 vector 取出元素来填充另一个 vector 的时候,常有三种方法 – 把旧的 vector 赋值给新的 vector,使用基于迭代器的      std::vector::insert()或者使用基于循环的       std::vector::push_back()。这些方法都展示在下面:   
   
  1. vector<BigTestStruct> sourceVector, destinationVector;
  2. FillVector(sourceVector);
  3. // Assign sourceVector to destination vector
  4. sw.Restart();
  5. destinationVector = sourceVector;
  6. cout << "Assigning Vector :" << sw.ElapsedUs() << endl;
  7. //Using std::vector::insert()
  8. vector<BigTestStruct> sourceVector1, destinationVector1;
  9. FillVector(sourceVector1);
  10. sw.Restart();
  11. destinationVector1.insert(destinationVector1.end(),
  12.   sourceVector1.begin(),
  13.   sourceVector1.end());
  14. cout << "Using insert() :" << sw.ElapsedUs() << endl;
复制代码
   这是它们的性能:
    赋值: 589.54 us
    insert(): 1321.27 us
    push_back(): 5354.70 us
    我们看到vector 赋值比 insert() 快了 55.38%,比 push_back() 快了 89% 。

    为什么会这样???

    赋值非常有效率,因为它知道要拷贝的 vector 有多大,然后只需要通过内存管理一次性拷贝 vector 内部的缓存。
    所以,想高效填充 vector,首先应尝试使用 assignment,然后再考虑基于迭代器的 insert(),最后考虑 push_back。当然,如果你需要从其它类型的容器拷贝元素到 vector 中,赋值的方式不可行。这种情况下,只好考虑基于迭代器的 insert()。
        #4遍历 std::vector 元素的时候,避免使用 std::vector::at() 函数。   

    遍历 vector 有如下三种方法:
   
          
  •         使用迭代器
          
  •         使用 std::vector::at() 成员函数
          
  •         使用下标 – [ ] 运算符
       
    下面展示了每种用法:
   
  1. //Using an iterator
  2. vector<BigTestStruct> testVectorSum;
  3. FillVector(testVectorSum);
  4. sw.Restart();
  5. int sum = 0;
  6. for (auto it = testVectorSum.begin(); it != testVectorSum.end(); ++it)
  7. {
  8.   sum = sum + it->iValue;
  9. }
  10. cout << "Using Iterator:" << sw.ElapsedUs() << endl;
  11.   
  12. //Using the at() member function
  13. sw.Restart();
  14. sum = 0;
  15. for (unsigned i = 0; i < testVectorSum.size(); ++i)
  16. {
  17.   sum = sum + testVectorSum.at(i).iValue;
  18. }
  19. cout << "Using at() :" << sw.ElapsedUs() << endl;
  20.   
  21. // Using the subscript notation
  22. sw.Restart();
  23. sum = 0;
  24. for (unsigned i = 0; i < testVectorSum.size(); ++i)
  25. {
  26.   sum = sum + testVectorSum[i].iValue;
  27. }
  28. cout << "Using subscripting:" << sw.ElapsedUs() << endl;
复制代码
   输出是:
   
  1. Using Iterator:0
  2. Using at() :3.73
  3. Using subscripting:0
复制代码
   显而易见,用 std::vector::at() 函数访问 vector 元素是最慢的一个。
        #5 尽量避免在 vector 前部插入元素   

    任何在 vetor 前部部做的插入操作其复杂度都是 O(n) 的。在前部插入数据十分低效,因为 vector 中的每个元素项都必须为新的项腾出空间而被复制。如果在 vector 前部连续插入多次,那可能需要重新评估你的总体架构。
    做个有趣的尝试,下面是在 std::vector 前部做插入和在 std::list 前部部做插入的对比:
   
  1. vector<BigTestStruct> sourceVector3, pushFrontTestVector;
  2. FillVector(sourceVector3);
  3. list<BigTestStruct> pushFrontTestList;
  4. //Push 100k elements in front of the new vector -- this is horrible code !!!
  5. sw.Restart();
  6. for (unsigned i = 1; i < sourceVector3.size(); ++i)
  7. {
  8.   pushFrontTestVector.insert(pushFrontTestVector.begin(), sourceVector3[i]);
  9. }
  10. cout << "Pushing in front of Vector :" << sw.ElapsedUs() << endl;
  11. // push in front of a list
  12. sw.Restart();
  13. for (unsigned i = 0; i < sourceVector3.size(); ++i)
  14. {
  15.   pushFrontTestList.push_front(sourceVector3[i]);
  16. }
  17. cout << "Pushing in front of list :" << sw.ElapsedUs() << endl;
复制代码
   如果我运行这个测试10,其中使用一个包含100个元素的vector,那么输出结果如下:
   
  1. Average of Pushing in front of Vector :11999.4
  2. Average of Pushing in front of list :20.36
复制代码
   在 list 前部部插入操作比在 vector 前部部快大约58836%。不用感到奇怪,因为在 list 前部做元素插入的算法,其复杂度为 O(1)。显然,vector 包含元素越多,这个性能测试的结果会越差。   
        #6在向 vector 插入元素的时候使用 emplace_back() 而不是 push_back()。   

    几乎赶上 C++11 潮流的每个人都明确地认同“安置”这种往 STL 容器里插入元素的方法。理论上来说,“安置”更有效率。然而所有实践都表明,有时候性能差异甚至可以忽略不计。
    思考下面的代码:
   
  1. // Helper function to populate the test vectors
  2. void FillVector(vector<BigTestStruct>& testVector)
  3. {
  4.   for (int i = 0; i < 10000; i++)
  5.   {
  6.     BigTestStruct bt;
  7.     testVector.push_back(bt);
  8.   }
  9. }0
复制代码
   如果运行100次,会得到这样的输出:
   
  1. // Helper function to populate the test vectors
  2. void FillVector(vector<BigTestStruct>& testVector)
  3. {
  4.   for (int i = 0; i < 10000; i++)
  5.   {
  6.     BigTestStruct bt;
  7.     testVector.push_back(bt);
  8.   }
  9. }1
复制代码
   可以清楚的看到,“安置”函数比插入函数性能更好 – 但只有 177 微秒的差距。在所有情况下,他们大致是相当的。
        仅在以下情况下,Emplacement 函数可能会更快:
   
          
  •         要添加的值是在 vector 中构造的,而不是赋值的。
          
  •         传递的参数类型与 vector 中保存的类型不同。例如,如果一个向量包含 std :: string,但我们传递一个字符串值到该 vector。
       
      即使上述两个条件都不成立,如本例所示的,你也不要因为在插入时使用 emplacement 而掉以轻心。
      更多关于 emplacement vs. insertion 的详细信息,请查看 Scott Meyer 的“        Effective Modern C++: 42 Specific Ways to Improve Your Use of C++11 and C++14“一书中的条目#42。      
            结语

    与任何第三方统计数据一样,你不应盲目地依赖此处提供的结果和建议。在不同的操作系统、处理器体系结构和编译器设置上测试时,你可能遇到很多不确定因素。因此,你需要根据实际数据,自己做出衡量。
友荐云推荐




上一篇:Best Free jQuery Plugins of 2016
下一篇:未来已到——HTTP/2
酷辣虫提示酷辣虫禁止发表任何与中华人民共和国法律有抵触的内容!所有内容由用户发布,并不代表酷辣虫的观点,酷辣虫无法对用户发布内容真实性提供任何的保证,请自行验证并承担风险与后果。如您有版权、违规等问题,请通过"联系我们"或"违规举报"告知我们处理。

ppguo 发表于 6 天前
占位编辑
回复 支持 反对

使用道具 举报

*滑动验证:
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

我要投稿

推荐阅读

扫码访问 @iTTTTT瑞翔 的微博
回页顶回复上一篇下一篇回列表手机版
手机版/CoLaBug.com ( 粤ICP备05003221号 | 文网文[2010]257号 )|网站地图 酷辣虫

© 2001-2016 Comsenz Inc. Design: Dean. DiscuzFans.

返回顶部 返回列表