在另一个线程中,我开始讨论向量和数组,在其中我主要是在扮演魔鬼的拥护者,以按下按钮。但是,在此过程中,我偶然发现了一个让我有点困惑的测试用例,我想就它进行一次真正的讨论,关于我因扮演魔鬼代言人而受到的“虐待”,开始一个真正的现在不可能就该线程进行讨论。然而,这个特定的例子让我很感兴趣,我无法对自己做出令人满意的解释。
讨论是关于向量与数组的一般性能,忽略动态元素。例如:显然在向量中不断使用 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% 让我非常惊讶,我希望它们可以忽略不计,而且我觉得这个测试用例的性质让我模糊了性质的结果。当您在较小的数组大小上运行此测试时,性能差异会显着消失。
我的解释:
向量的附加实现指令导致向量指令在内存中对齐不佳,甚至在这个例子中,在 2 个不同的“块”上的一个非常糟糕的点上分裂。这导致内存在缓存级别、数据缓存和指令缓存之间来回跳转的频率比您预期的要高。我还怀疑 LLVM 编译器可能夸大了弱点,并且由于一些较新的 C++11 元素而优化不佳,尽管除了假设和猜想之外,我没有理由对这些解释中的任何一种进行解释。
如果 A:有人可以复制我的结果和 B:如果有人对计算机如何运行这个特定的基准测试以及为什么在这种情况下向量的性能如此显着低于数组有更好的解释,我很感兴趣。
我的设置: http ://www.newegg.com/Product/Product.aspx?Item=N82E16834100226