6 个技巧，提升 C++11 的 vector 性能
AmparoQKDI
8年前
<p>Vector 就像是 C++ STL 容器的瑞士军刀。Bjarne Stoutsoup 有一句话 – “一般情况下，如果你需要容器，就用 vector”。像我们这样的普通人把这句话当作真理，只需要照样去做。然而，就像其它工具一样，vector 也只是个工具，它能提高效率，也能降低效率。</p> <p>这篇文章中我们可以看到 6 种优化使用 vector 的方法。我们会在最常见的使用 vector 的开发任务中看到有效的方法和无效的方法，并以此衡量有效使用 vector 会带来怎样的性能提升，并试图理解为什么能得到这样的性能提升。</p> <h3><strong>性能测试的搭建和方法:</strong></h3> <ul> <li> <p>所有测试都在我的 Surface Book 中运行，这台笔记本拥有主频 2.6Ghz 的酷睿 i7 处理器，8 GB 内存，安装了 Windows 10 操作系统并使用 VS2015 C++ 编译器编译运行。</p> </li> <li> <p>我们会使用 Stopwatch。这个工具由 Kjell 创建，在 https://github.com/KjellKod/Stopwatch 可以找到。</p> </li> <li> <p>我们会运行每个测试 100 次，然后计算平均运行时间来作为依据。运行测试的代码在这里 。你可以自由下载，用于在你自己的系统中评估 vector 的性能。那里提供的代码段只反映了一次循环，这让事件变得简单。</p> </li> <li> <p>我们在 vector 中存入 TestStruct 结构的数据，并使用 FillVector() 来填充 vector。它们的定义如下。</p> </li> </ul> <pre> <code class="language-cpp">// Test struct to be inserted/removed from vector struct BigTestStruct { int iValue = 1; float fValue; long lValue; double dValue; char cNameArr[10]; int iValArr[100]; };</code></pre> <pre> <code class="language-cpp">// Helper function to populate the test vectors void FillVector(vector<BigTestStruct>& testVector) { for (int i = 0; i < 10000; i++) { BigTestStruct bt; testVector.push_back(bt); } }</code></pre> <p>马上开始在 C++ 11 中优化 vector 用法的介绍 。</p> <h2><strong>#1 提前分配足够的空间以避免不必要的重新分配和复制周期</strong></h2> <p>程序员喜欢使用 vector，因为他们只需要往向容器中添加元素，而不用事先操心容器大小的问题。但是，如果由一个容量为 0 的 vector 开始，往里面添加元素会花费大量的运行性能。如果你之前就知道 vector 需要保存多少元素，就应该提前为其分配足够的空间。</p> <p>这里有一个简单的示例，往 vector 里添加 1 万个测试结构的实例——先进行不预分配空间的测试再进行有预分配的测试。</p> <pre> <code class="language-cpp">vector<BigTestStruct> testVector1; vector<BigTestStruct> testVector2; sw.Restart(); FillVector(testVector1); cout << "Time to Fill Vector Without Reservation:" << sw.ElapsedUs() << endl; sw.Restart(); testVector2.reserve(10000); FillVector(testVector2); cout << "Time to Fill Vector With Reservation:" << sw.ElapsedUs() << endl;</code></pre> <p>在我的计算机中，未预分配空间的情况用了 5145 微秒(us)，而预分配了空间的情况下只用了 1279 微秒，性能提高了 75.14%！！！</p> <p>这个情况在 Scott Meyers 的书中得到了很好的解释，这本书叫 Effective STL- <a href="https://www.amazon.com/Effective-STL-Specific-Standard-Template/dp/0201749629/ref=sr_1_1?ie=UTF8&qid=1479660921&sr=8-1&keywords=Effective+STL" rel="nofollow,noindex">50条有效使用STL的经验</a> :</p> <p>“对于 vector 和 string，在需要更多空间的时候，会做与 realloc 等效的事情。这种类似 realloc 的操作有4个步骤：</p> <p>1. 分别一个新的内存块，其容量是容器当前容量的数倍。多数实现中，vector 和 string 容量的提升因子在 1.5 和 2 之间。</p> <p>2. 从容器原来占用的内存中将元素拷贝到新分配的内存中。</p> <p>3. 释放原有内存中的对象。</p> <p>4. 释放原有内存。</p> <p>有了所有这些操作：分配、回收、拷贝和释放，如果说这些步骤（对于性能）极其昂贵，你一点都不应该感到惊讶。当然，你肯定不希望频繁的进行这样的操作。如果这还没有打动你，那么想想每次进行这些步骤的时候，vector 和 string 中所有的迭代器、指针和引用都会失效。这意味着一个简单的插入操作，对于其它使用了当前 vector 或 string 中的迭代器、指针或引用的数据结构，都有可能引起对它们进行更新。 <em>”</em></p> <h2><strong>#2使用 shrink_to_fit() 释放 vector 占用的内存， – clear() 或 erase() 不会释放内存。</strong></h2> <p>与大家所想的相反，使用 erase() 或 clear() 从 vector 中删除元素并不会释放分配给 vector 的内存。做个简单的实验就可以证明这一点。我们往一个 vector 中添加 100 个元素，然后在这个 vector 上调用 clear() 和 erase()。然后我们可以让 capacity() 函数告诉我们为这个容器分配的内存可以存入多少元素。</p> <pre> <code class="language-cpp">FillVector(testVector1); size_t capacity = testVector1.capacity(); cout << "Capacity Before Erasing Elements:" << capacity << endl; testVector1.erase(testVector1.begin(), testVector1.begin() + 3); // capacity = testVector1.capacity(); cout << "Capacity After Erasing 3 elements Elements:" << capacity << endl; testVector1.clear(); capacity = testVector1.capacity(); cout << "Capacity After clearing all emements:" << capacity << endl; testVector1.shrink_to_fit(); capacity = testVector1.capacity(); cout << "Capacity After shrinking the Vector:" << capacity << endl;</code></pre> <p>下面是输出：</p> <pre> <code class="language-cpp">Capacity Before Erasing Elements:12138 Capacity After Erasing 3 elements Elements:12138 Capacity After clearing all emements:12138 Capacity After shrinking the Vector:0</code></pre> <p>从上面的输出可以看到，erase() 或 clear() 不会减少 vector 占用的内存。如果在代码中到达某一点，不再需要 vector 时候，请使用 <strong>std::vector::shrink_to_fit()</strong> 方法释放掉它占用的内存。</p> <p>请注意，shrink_to_fit() 可能没有被所有编译器供应商完全支持。这种情况下，可以使用“Swap 惯用法”来清空 vector，代码如下：</p> <p><em>container<T>( c ).swap( c );</em> // shrink-to-fit 惯用法，用于清空存储空间</p> <p><em>container<T>().swap( c ); </em> // 用于清空所有内容和存储空间的惯用法 </p> <h2><strong>#3在填充或者拷贝到 vector 的时候，应该使用赋值而不是 insert() 或push_back().</strong></h2> <p>从一个 vector 取出元素来填充另一个 vector 的时候，常有三种方法 – 把旧的 vector 赋值给新的 vector，使用基于迭代器的 <strong>std::vector::insert()</strong> 或者使用基于循环的 <strong>std::vector::push_back()。</strong> 这些方法都展示在下面：</p> <pre> <code class="language-cpp">vector<BigTestStruct> sourceVector, destinationVector; FillVector(sourceVector); // Assign sourceVector to destination vector sw.Restart(); destinationVector = sourceVector; cout << "Assigning Vector :" << sw.ElapsedUs() << endl; //Using std::vector::insert() vector<BigTestStruct> sourceVector1, destinationVector1; FillVector(sourceVector1); sw.Restart(); destinationVector1.insert(destinationVector1.end(), sourceVector1.begin(), sourceVector1.end()); cout << "Using insert() :" << sw.ElapsedUs() << endl;</code></pre> <p>这是它们的性能：</p> <p>赋值: 589.54 us</p> <p>insert(): 1321.27 us</p> <p>push_back(): 5354.70 us</p> <p>我们看到vector 赋值比 insert() 快了 55.38%，比 push_back() 快了 89% 。</p> <p>为什么会这样???</p> <p>赋值非常有效率，因为它知道要拷贝的 vector 有多大，然后只需要通过内存管理一次性拷贝 vector 内部的缓存。</p> <p>所以，想高效填充 vector，首先应尝试使用 assignment，然后再考虑基于迭代器的 insert()，最后考虑 push_back。当然，如果你需要从其它类型的容器拷贝元素到 vector 中，赋值的方式不可行。这种情况下，只好考虑基于迭代器的 insert()。</p> <h2><strong>#4遍历 std::vector 元素的时候，避免使用 std::vector::at() 函数。</strong></h2> <p>遍历 vector 有如下三种方法：</p> <ol> <li> <p>使用迭代器</p> </li> <li> <p>使用 std::vector::at() 成员函数</p> </li> <li> <p>使用下标 – [ ] 运算符</p> </li> </ol> <p>下面展示了每种用法：</p> <pre> <code class="language-cpp">//Using an iterator vector<BigTestStruct> testVectorSum; FillVector(testVectorSum); sw.Restart(); int sum = 0; for (auto it = testVectorSum.begin(); it != testVectorSum.end(); ++it) { sum = sum + it->iValue; } cout << "Using Iterator:" << sw.ElapsedUs() << endl; //Using the at() member function sw.Restart(); sum = 0; for (unsigned i = 0; i < testVectorSum.size(); ++i) { sum = sum + testVectorSum.at(i).iValue; } cout << "Using at() :" << sw.ElapsedUs() << endl; // Using the subscript notation sw.Restart(); sum = 0; for (unsigned i = 0; i < testVectorSum.size(); ++i) { sum = sum + testVectorSum[i].iValue; } cout << "Using subscripting:" << sw.ElapsedUs() << endl;</code></pre> <p>输出是：</p> <pre> <code class="language-cpp">Using Iterator:0 Using at() :3.73 Using subscripting:0</code></pre> <p>显而易见，用 std::vector::at() 函数访问 vector 元素是最慢的一个。</p> <h2><strong>#5 尽量避免在 vector 前部插入元素</strong></h2> <p>任何在 vetor 前部部做的插入操作其复杂度都是 O(n) 的。在前部插入数据十分低效，因为 vector 中的每个元素项都必须为新的项腾出空间而被复制。如果在 vector 前部连续插入多次，那可能需要重新评估你的总体架构。</p> <p>做个有趣的尝试，下面是在 std::vector 前部做插入和在 std::list 前部部做插入的对比：</p> <pre> <code class="language-cpp">vector<BigTestStruct> sourceVector3, pushFrontTestVector; FillVector(sourceVector3); list<BigTestStruct> pushFrontTestList; //Push 100k elements in front of the new vector -- this is horrible code !!! sw.Restart(); for (unsigned i = 1; i < sourceVector3.size(); ++i) { pushFrontTestVector.insert(pushFrontTestVector.begin(), sourceVector3[i]); } cout << "Pushing in front of Vector :" << sw.ElapsedUs() << endl; // push in front of a list sw.Restart(); for (unsigned i = 0; i < sourceVector3.size(); ++i) { pushFrontTestList.push_front(sourceVector3[i]); } cout << "Pushing in front of list :" << sw.ElapsedUs() << endl;</code></pre> <p>如果我运行这个测试10，其中使用一个包含100个元素的vector，那么输出结果如下：</p> <pre> <code class="language-cpp">Average of Pushing in front of Vector :11999.4 Average of Pushing in front of list :20.36</code></pre> <p>在 list 前部部插入操作比在 vector 前部部快大约58836%。不用感到奇怪，因为在 list 前部做元素插入的算法，其复杂度为 O(1)。显然，vector 包含元素越多，这个性能测试的结果会越差。</p> <h2><strong>#6在向 vector 插入元素的时候使用 emplace_back() 而不是 push_back()。</strong></h2> <p>几乎赶上 C++11 潮流的每个人都明确地认同“安置”这种往 STL 容器里插入元素的方法。理论上来说，“安置”更有效率。然而所有实践都表明，有时候性能差异甚至可以忽略不计。</p> <p>思考下面的代码：</p> <pre> <code class="language-cpp">vector<BigTestStruct> sourceVector4, pushBackTestVector, emplaceBackTestVector; FillVector(sourceVector4); //Test push back performance sw.Restart(); for (unsigned i = 0; i < sourceVector4.size(); ++i) { pushBackTestVector.push_back(sourceVector4[i]); } cout << "Using push_back :" << sw.ElapsedUs() << endl; //Test emplace_back() sw.Restart(); for (unsigned i = 0; i < sourceVector4.size(); ++i) { emplaceBackTestVector.emplace_back(sourceVector4[i]); } cout << "Using emplace_back :" << sw.ElapsedUs() << endl;</code></pre> <p>如果运行100次，会得到这样的输出：</p> <pre> <code class="language-cpp">Average Using push_back :5431.58 Average Using emplace_back :5254.64</code></pre> <p>可以清楚的看到，“安置”函数比插入函数性能更好 – 但只有 177 微秒的差距。在所有情况下，他们大致是相当的。</p> <p>仅在以下情况下，Emplacement 函数可能会更快：</p> <ol> <li> <p>要添加的值是在 vector 中构造的，而不是赋值的。</p> </li> <li> <p>传递的参数类型与 vector 中保存的类型不同。例如，如果一个向量包含 std :: string，但我们传递一个字符串值到该 vector。</p> </li> </ol> <p>即使上述两个条件都不成立，如本例所示的，你也不要因为在插入时使用 emplacement 而掉以轻心。</p> <p> </p> <h3><strong>结语</strong></h3> <p>与任何第三方统计数据一样，你不应盲目地依赖此处提供的结果和建议。在不同的操作系统、处理器体系结构和编译器设置上测试时，你可能遇到很多不确定因素。因此，你需要根据实际数据，自己做出衡量。</p> <p> </p> <p>来自：https://www.oschina.net/translate/6-tips-supercharge-cpp-11-vector-performance</p> <p> </p>