dFi*_*nov 4 c++ algorithm c++11
我决定对简单类型(例如int,或者struct,或者class在其字段中仅使用简单类型的交换函数)的实现进行基准测试,并在其中使用statictmp变量来防止每次交换调用中的内存分配.所以我写了这个简单的测试程序:
#include <iostream>
#include <chrono>
#include <utility>
#include <vector>
template<typename T>
void mySwap(T& a, T& b) //Like std::swap - just for tests
{
T tmp = std::move(a);
a = std::move(b);
b = std::move(tmp);
}
template<typename T>
void mySwapStatic(T& a, T& b) //Here with static tmp
{
static T tmp;
tmp = std::move(a);
a = std::move(b);
b = std::move(tmp);
}
class Test1 { //Simple class with some simple types
int foo;
float bar;
char bazz;
};
class Test2 { //Class with std::vector in it
int foo;
float bar;
char bazz;
std::vector<int> bizz;
public:
Test2()
{
bizz = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
}
};
#define Test Test1 //choosing class
const static unsigned int NUM_TESTS = 100000000;
static Test a, b; //making it static to prevent throwing out from code by compiler optimizations
template<typename T, typename F>
auto test(unsigned int numTests, T& a, T& b, const F swapFunction ) //test function
{
std::chrono::system_clock::time_point t1, t2;
t1 = std::chrono::system_clock::now();
for(unsigned int i = 0; i < NUM_TESTS; ++i) {
swapFunction(a, b);
}
t2 = std::chrono::system_clock::now();
return std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - t1).count();
}
int main()
{
std::chrono::system_clock::time_point t1, t2;
std::cout << "Test 1. MySwap Result:\t\t" << test(NUM_TESTS, a, b, mySwap<Test>) << " nanoseconds\n"; //caling test function
t1 = std::chrono::system_clock::now();
for(unsigned int i = 0; i < NUM_TESTS; ++i) {
mySwap<Test>(a, b);
}
t2 = std::chrono::system_clock::now();
std::cout << "Test 2. MySwap2 Result:\t\t" << std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - t1).count() << " nanoseconds\n"; //This result slightly better then 1. why?!
std::cout << "Test 3. MySwapStatic Result:\t" << test(NUM_TESTS, a, b, mySwapStatic<Test>) << " nanoseconds\n"; //test function with mySwapStatic
t1 = std::chrono::system_clock::now();
for(unsigned int i = 0; i < NUM_TESTS; ++i) {
mySwapStatic<Test>(a, b);
}
t2 = std::chrono::system_clock::now();
std::cout << "Test 4. MySwapStatic2 Result:\t" << std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - t1).count() << " nanoseconds\n"; //And again - it's better then 3...
std::cout << "Test 5. std::swap Result:\t" << test(NUM_TESTS, a, b, std::swap<Test>) << " nanoseconds\n"; //calling test function with std::swap for comparsion. Mostly similar to 1...
return 0;
}
一些Test定义为Test1(g ++(Ubuntu 4.8.2-19ubuntu1)4.8.2的结果称为g ++ main.cpp -O3 -std = c ++ 11):
测试1. MySwap结果:625,105,480纳秒
测试2. MySwap2结果:528,701,547纳秒
测试3. MySwapStatic结果:338,484,180纳秒
测试4. MySwapStatic2结果:228,228,156纳秒
测试5. std :: swap结果:564,863,184纳秒
我的主要问题是:使用此实现来交换简单类型是否合适？我知道,如果你使用它来交换带向量的类型,那么std::swap就更好了,你可以通过将Testdefine 更改为来看到它Test2.
第二个问题:为什么测试1,2,3和4中的结果如此不同？我在测试功能实现方面做错了什么？
首先回答你的第二个问题:在你的测试2和4中,编译器正在内联函数,因此它提供了更好的性能(测试4还有更多,但我将在后面介绍).
总的来说,使用静态临时变量可能是个坏主意.
为什么？首先,应该注意的是,在x86汇编中,没有指令从内存复制到内存.这意味着在交换时,CPU寄存器中不存在一个,而是两个临时变量.并且这些临时变量必须在CPU寄存器中,您不能将mem复制到mem,因此静态变量将添加第三个存储位置以进行传输.
静态温度的一个问题是它会阻碍内联.想象一下,如果您交换的变量已经在CPU寄存器中.在这种情况下,编译器可以内联交换,并且永远不会将任何内容复制到内存,这要快得多.现在,如果您强制使用静态临时值,则编译器会将其删除(无用),或者强制添加内存副本.这就是测试4中发生的情况,其中GCC删除了对静态变量的所有读取.它只是毫无意义地为它写了更新的值,因为你告诉它这样做.读取删除解释了良好的性能增益,但它可能更快.
您的测试用例存在缺陷,因为它们没有显示这一点.
现在您可能会问:那为什么我的静态功能表现更好？我不知道.(最后回答)
我很好奇,所以我用MSVC编译你的代码,结果证明MSVC做得对,GCC做得很奇怪.在O2优化级别,MSVC检测到两个交换是无操作并将其快捷,但即使在O1,非内联生成的代码也比在O3处使用GCC的所有测试情况更快.(编辑:实际上,MSVC也没有做到正确,最后请看解释.)
由MSVC生成的程序集看起来确实更好,但是当比较GCC生成的静态和非静态程序集时,我不知道为什么静态表现更好.
无论如何,我认为即使GCC生成奇怪的代码,内联问题应该值得使用std :: swap,因为对于更大的类型,额外的内存副本可能是昂贵的,而较小的类型提供更好的内联.
以下是所有测试用例生成的程序集,如果有人知道为什么GCC静态比非静态更好,尽管更长并且使用更多的内存移动.编辑:最后回答
GCC非静态(性能为570ms):
00402F90 44 8B 01 mov r8d,dword ptr [rcx]
00402F93 F3 0F 10 41 04 movss xmm0,dword ptr [rcx+4]
00402F98 0F B6 41 08 movzx eax,byte ptr [rcx+8]
00402F9C 4C 8B 0A mov r9,qword ptr [rdx]
00402F9F 4C 89 09 mov qword ptr [rcx],r9
00402FA2 44 0F B6 4A 08 movzx r9d,byte ptr [rdx+8]
00402FA7 44 88 49 08 mov byte ptr [rcx+8],r9b
00402FAB 44 89 02 mov dword ptr [rdx],r8d
00402FAE F3 0F 11 42 04 movss dword ptr [rdx+4],xmm0
00402FB3 88 42 08 mov byte ptr [rdx+8],al
GCC静态和MSVC静态(性能275ms):
00402F10 48 8B 01 mov rax,qword ptr [rcx]
00402F13 48 89 05 66 11 00 00 mov qword ptr [404080h],rax
00402F1A 0F B6 41 08 movzx eax,byte ptr [rcx+8]
00402F1E 88 05 64 11 00 00 mov byte ptr [404088h],al
00402F24 48 8B 02 mov rax,qword ptr [rdx]
00402F27 48 89 01 mov qword ptr [rcx],rax
00402F2A 0F B6 42 08 movzx eax,byte ptr [rdx+8]
00402F2E 88 41 08 mov byte ptr [rcx+8],al
00402F31 48 8B 05 48 11 00 00 mov rax,qword ptr [404080h]
00402F38 48 89 02 mov qword ptr [rdx],rax
00402F3B 0F B6 05 46 11 00 00 movzx eax,byte ptr [404088h]
00402F42 88 42 08 mov byte ptr [rdx+8],al
MSVC非静态(性能215ms):
00000 f2 0f 10 02 movsdx xmm0, QWORD PTR [rdx]
00004 f2 0f 10 09 movsdx xmm1, QWORD PTR [rcx]
00008 44 8b 41 08 mov r8d, DWORD PTR [rcx+8]
0000c f2 0f 11 01 movsdx QWORD PTR [rcx], xmm0
00010 8b 42 08 mov eax, DWORD PTR [rdx+8]
00013 89 41 08 mov DWORD PTR [rcx+8], eax
00016 f2 0f 11 0a movsdx QWORD PTR [rdx], xmm1
0001a 44 89 42 08 mov DWORD PTR [rdx+8], r8d
std :: swap版本都与非静态版本相同.
在进行了一些有趣的调查之后,我发现了GCC非静态版本性能不佳的可能原因.现代处理器具有称为存储到负载转发的功能.当内存加载与先前的内存存储匹配时,此功能启动,并快速执行内存操作以使用已知的值.在这种情况下,GCC以某种方式对参数A和B使用非对称加载/存储.使用4 + 4 + 1字节复制A,使用8 + 1字节复制B. 这意味着该类的8个第一个字节将不会被存储到加载转发匹配,从而失去了宝贵的CPU优化.为了检查这一点,我手动将8 + 1副本替换为4 + 4 + 1副本,并且性能如预期的那样上升(代码如下).最后,海湾合作委员会因不考虑这一点而有过错.
GCC修补代码,更长时间但利用存储转发(性能220ms):
00402F90 44 8B 01 mov r8d,dword ptr [rcx]
00402F93 F3 0F 10 41 04 movss xmm0,dword ptr [rcx+4]
00402F98 0F B6 41 08 movzx eax,byte ptr [rcx+8]
00402F9C 4C 8B 0A mov r9,qword ptr [rdx]
00402F9F 4C 89 09 mov qword ptr [rcx],r9
00402F9C 44 8B 0A mov r9d,dword ptr [rdx]
00402F9F 44 89 09 mov dword ptr [rcx],r9d
00402FA2 44 8B 4A 04 mov r9d,dword ptr [rdx+4]
00402FA6 44 89 49 04 mov dword ptr [rcx+4],r9d
00402FAA 44 0F B6 4A 08 movzx r9d,byte ptr [rdx+8]
00402FAF 44 88 49 08 mov byte ptr [rcx+8],r9b
00402FB3 44 89 02 mov dword ptr [rdx],r8d
00402FB6 F3 0F 11 42 04 movss dword ptr [rdx+4],xmm0
00402FBB 88 42 08 mov byte ptr [rdx+8],al
实际上,这个复制指令(对称4 + 4 + 1)是正确的方法.在这些测试中我们只做副本,在这种情况下,MSVC版本无疑是最好的.问题是在实际情况下,将单独访问类成员,从而生成4个字节的读/写.MSVC 8字节批量复制(也由GCC为一个参数生成)将阻止个别成员的未来存储转发.我在副本旁边进行的成员操作的新测试表明,修补后的4 + 4 + 1版本确实胜过其他所有版本.并且系数接近x2.遗憾的是,没有现代编译器生成此代码.
| 归档时间： |
|
| 查看次数： |
339 次 |
| 最近记录： |