矢量vs数组性能

在另一个帖子中，我开始讨论向量和数组，我在很大程度上扮演了魔鬼的倡导者，以按按钮。然而，在这个过程中，我偶然发现了一个让我有点困惑的测试用例，我想对它进行一次真正的讨论，关于我扮演魔鬼拥护者的"滥用"，现在不可能在这个线程上开始真正的讨论。然而，这个特殊的例子引起了我的兴趣，我不能令人满意地解释给自己听。

讨论的是Vector vs Arrays的一般性能，忽略了动态元素。例如:显然，在向量中不断使用push_back()会减慢它的速度。我们假设向量和数组都预先填充了数据。我给出的示例(随后由线程中的个人修改)如下:

#include <iostream>
#include <vector>
#include <type_traits>
using namespace std;
const int ARRAY_SIZE = 500000000;
// http://stackoverflow.com/a/15975738/500104
template <class T>
class no_init_allocator
{
public:
    typedef T value_type;
    no_init_allocator() noexcept {}
    template <class U>
        no_init_allocator(const no_init_allocator<U>&) noexcept {}
    T* allocate(std::size_t n)
        {return static_cast<T*>(::operator new(n * sizeof(T)));}
    void deallocate(T* p, std::size_t) noexcept
        {::operator delete(static_cast<void*>(p));}
    template <class U>
        void construct(U*) noexcept
        {
            // libstdc++ doesn't know 'is_trivially_default_constructible', still has the old names
            static_assert(is_trivially_default_constructible<U>::value,
            "This allocator can only be used with trivally default constructible types");
        }
    template <class U, class A0, class... Args>
        void construct(U* up, A0&& a0, Args&&... args) noexcept
        {
            ::new(up) U(std::forward<A0>(a0), std::forward<Args>(args)...);
        }
};
int main() {
    srand(5);  //I use the same seed, we just need the random distribution.
    vector<char, no_init_allocator<char>> charArray(ARRAY_SIZE);
    //char* charArray = new char[ARRAY_SIZE];
    for(int i = 0; i < ARRAY_SIZE; i++) {
        charArray[i] = (char)((i%26) + 48) ;
    }
    for(int i = 0; i < ARRAY_SIZE; i++) {
        charArray[i] = charArray[rand() % ARRAY_SIZE];
    }
}

当我在我的机器上运行它时，我得到以下终端输出。第一次运行时向量行没有注释，第二次运行时数组行没有注释。我使用了最高级别的优化，以给予向量最好的成功机会。下面是我的结果，前两次运行时数组行没有注释，后两次运行时向量行没有注释。

//Array run # 1
clang++ -std=c++11 -stdlib=libc++ -o3 some.cpp -o b.out && time ./b.out
real    0m20.287s
user    0m20.068s
sys 0m0.175s
//Array run # 2
clang++ -std=c++11 -stdlib=libc++ -o3 some.cpp -o b.out && time ./b.out
real    0m21.504s
user    0m21.267s
sys 0m0.192s
//Vector run # 1
clang++ -std=c++11 -stdlib=libc++ -o3 some.cpp -o b.out && time ./b.out
real    0m28.513s
user    0m28.292s
sys 0m0.178s
//Vector run # 2
clang++ -std=c++11 -stdlib=libc++ -o3 some.cpp -o b.out && time ./b.out
real    0m28.607s
user    0m28.391s
sys 0m0.178s

数组优于向量并不让我感到惊讶，但是，差异在50%的量级上让我感到非常惊讶，我期望它们可以忽略不计，我觉得这个测试用例的性质模糊了结果的性质。当您在较小的数组大小上运行此测试时，性能差异会显着消失。

我的解释:

向量的额外实现指令导致向量指令在内存中对齐不好，甚至可能在这个例子中，在两个不同的"块"上的一个非常糟糕的点上分裂。这导致内存在缓存、数据缓存和指令缓存之间来回跳转的频率比您预期的要高。我还怀疑LLVM编译器可能夸大了弱点，并且由于一些较新的c++ 11元素而优化得很差，尽管除了假设和猜想之外，我没有任何理由支持这些解释。

我感兴趣的是，如果A:有人可以复制我的结果，B:如果有人能更好地解释计算机是如何运行这个特定的基准测试的，以及为什么向量在这个实例中表现得如此之差。

我的设置:http://www.newegg.com/Product/Product.aspx?Item=N82E16834100226

一个更简单的解释:你正在构建禁用优化。您想要-O3，而不是-o3。

我没有可用的clang来精确地复制您的测试，但我的结果如下:

//Array run # 1
$ g++ -std=c++11 -O3 test.cpp -o b.out && time ./b.out
real    0m25.323s
user    0m25.162s
sys 0m0.148s
//Vector run #1
$ g++ -std=c++11 -O3 test.cpp -o b.out && time ./b.out
real    0m25.634s
user    0m25.486s
sys 0m0.136s

我可以保证LLVM实际上没有对std::vector进行错误优化(如果您实际上在进行优化的话)，至少目前是这样。它没有正确内联所涉及的许多函数调用。使用GCC将获得更好的性能。

相关内容

最新更新

热门标签：