欧美性猛交XXXX免费看蜜桃,成人网18免费韩国,亚洲国产成人精品区综合,欧美日韩一区二区三区高清不卡,亚洲综合一区二区精品久久

利用模板元編程實(shí)現解循環(huán)優(yōu)化
Unroll Loops Optimization with Template Meta Programming

作者：王鵬

簡(jiǎn)介

在《C++ Templates: The Complete Guide》一書(shū)中（以下簡(jiǎn)稱(chēng)書(shū)），提出了模板元編程最早的實(shí)際應用之一：在數值運算中進(jìn)行解循環(huán)優(yōu)化。
而本文的標題是噱頭！本文的真正目的是指出這種優(yōu)化措施在增加復雜性的同時(shí)，并不一定能明顯改善效率。應當謹慎使用該技術(shù)——默認不使用該技術(shù)，在點(diǎn)積計算確實(shí)是效率瓶頸時(shí)考慮采用該技術(shù)，并認真測試該技術(shù)是否真能提高效率。

背景

數值運算庫中常常需要提供向量點(diǎn)積（dot_product）運算。其定義用C++代碼描述也許更清楚～

template<typename T>T dot_product(int dim,const T v1[],const T v2[]) {	T result=0;	for (int i=0;i<dim;++i)		result += v1[i]*v2[i];	return result;}

int v1[] = {1,2,3};int v2[] = {4,5,6};int r1 = dot_product(3,v1,v2);

書(shū)中指出：“這個(gè)結果是正確的，但是在要求高效率的應用中，它耗費了太多的時(shí)間”，對于這類(lèi)特殊的問(wèn)題，“簡(jiǎn)單的把循環(huán)展開(kāi)”，如：r1=v1[0]*v2[0]+v1[1]*v2[1]+v1[2]*v2[2]
“反而會(huì )好得多”。

如何便捷的展開(kāi)循環(huán)？將每個(gè)dot_product(dim,...) 手工重寫(xiě)成展開(kāi)式？還是設計一整套函數: dot_product_dim_2，dot_product_dim_3，... ？
無(wú)疑這是一個(gè)冗長(cháng)乏味易出錯的方案。

書(shū)中提出了一種使用模板元編程解決該問(wèn)題的方案，讓我們來(lái)看看他是怎么做的。

模板元編程——解循環(huán)

// 首先是遞歸模板template<int DIM,typename T>struct DotProduct {	static T execute(const T v1[],const T v2[]);}template<int DIM,typename T>T DotProduct<DIM,T>::execute(const T v1[],const T v2[]) {	return v1[0]*v2[0] + DotProduct<DIM-1,T>::execute(v1+1,v2+1);}// 遞歸邊界模板template<typename T>struct DotProduct<1,T> {	static T execute(const T v1[],const T v2[]);}template<typename T>T DotProduct<1,T>::execute(const T v1[],const T v2[]) {	return v1[0]*v2[0];}

int v1[] = {1,2,3}; int v2[] = {4,5,6};int r2 = DotProduct<3,int>::execute(v1,v2);

int DotProduct<3,int>::execute(const int v1[],const int v2[]) {	return v1[0]*v2[0] + DotProduct<2,int>::execute(v1+1,v2+1);}

int DotProduct<2,int>::execute(const int v1[],const int v2[]) {	return v1[0]*v2[0] + DotProduct<1,int>::execute(v1+1,v2+1);}

int DotProduct<1,int>::execute(const int v1[],const int v2[]) {	return v1[0]*v2[0];}

r2 = v1[0]*v2[0]+v1[1]*v2[1]+v1[2]*v2[2];

template<int DIM,typename T>T dot_product(const T v1[],const T v2[]) {	return DotProduct<DIM,T>::execute(v1,v2);}

如同STL的make_pair、bind2nd，這個(gè)模板函數將模板參數T的推導工作交給編譯器，使DotProduct的界面更友好，更不容易出錯。當然，維度DIM必須指定。

現在可以按如下方式使用 ：

int r2 = dot_product<3>(v1,v2); // 是不是和 int r1 = dot_product(3,v1,v2); 十分相似？

本文以下部分將從編譯器生成的機器碼層次來(lái)驗證這一技術(shù)，同時(shí)與普通循環(huán)點(diǎn)積計算做比較。
測試環(huán)境 ：Windows Xp sp2，Microsoft Visual Studio 2005 Team Suite，release默認設置

驗證1：

該技術(shù)真的能和預想的一樣，實(shí)例化多個(gè)函數，并將它們inline，達到解循環(huán)的效果嗎？
讓我們寫(xiě)個(gè)短小程序驗證一下：

int main() {	int v1[] = {1,2,3};	int v2[] = {4,5,6};	int r1 = dot_product(3,v1,v2);		//循環(huán)版本	int r2 = dot_product<3>(v1,v2);	//解循環(huán)版本	cout<<r1<<endl;	cout<<r2<<endl;	return 0;}

cout<<r1<<endl; // 生成7條指令mov		eax,dword ptr [__imp_std::endl (402040h)mov		ecx,dword ptr [__imp_std::cout (402044h)]push		eaxpush		20hcall	dword ptr [__imp_std::basic_ostream<char,std::char_traits<char> >::operator<< (40203Ch)]mov	ecx,eaxcall	dword ptr [__imp_std::basic_ostream<char,std::char_traits<char> >::operator<< (402038h)]

我們知道 cout<<r1<<endl; 的完整形式是
(cout<<r1)<<endl; 即是 cout.operator<<(r1).operator<<(endl);
cout.opeator<<(...) 返回的是自身引用，所以可以進(jìn)行鏈式輸出

前4條指令執行后：
堆棧應該是：
std::endl
20h
ECX 保存的是 std::cout

std::cout 的類(lèi)型是std::basic_ostream<char,std::char_traits<char> > 
所以第5條指令正是對cout的成員函數“ opeator<<”進(jìn)行調用
(this指針 std::cout,已經(jīng)存入ECX，而且可以猜想這個(gè)成員函數正是 operator(int) 重載)
而參數，對的，是call指令前，堆棧棧頂“20h”—— 32的16進(jìn)制。
第5條指令將執行 cout.operator<<(20h); ！

讓我們把 r1被編譯器偷偷替換成20h的事放在一邊，繼續解析后2條指令：
cout.operator<< 使用__thiscall調用約定，函數自己彈出堆棧中參數20h， 返回自身引用，返回值存入EAX。
所以第5條指令執行后：
堆棧應該是：
std::endl;
EAX 保存的是返回值，即是std::cout

第6條指令 mov ecx,eax 將返回值重新放入ECX，設置好this指針。
第7條指令 繼續調用 operator<< 的另一個(gè)重載版本。（這時(shí) std::endl 在棧頂）
完成語(yǔ)句 cout.operator<<(endl);

cout<<r2<<endl; 生成了相似的7條指令。

這個(gè)原本就短小的程序，被編譯器“篡改”為更短小的程序：

int main() {	cout<<32<<endl;cout<<32<<endl;	return 0;}

printf(“%d\n”,r1); printf(“%d\n”,r2);

printf(“%d\n”,0x20); printf(“%d\n”,0x20);

（詳細代碼見(jiàn) sample1）

比較合理的解釋是，編譯器知道了太多的上下文，做出了足夠的優(yōu)化，將本來(lái)應該運行時(shí)得出的結果—— 一個(gè)不變的結果 ——放入的可執行文件中，直接輸出。

為了驗證模板元解循環(huán)技術(shù)，我們要另外想辦法。

驗證2：

我們需要“阻撓”編譯器，讓它不能猜測出運行結果，從而生成真正的計算代碼。
這里使用了一個(gè)比較簡(jiǎn)單的方案：

template<class OutIt>void __stdcall MyGenerate(OutIt first,OutIt last,const char *name) {	cout<<"generating "<<name<<" with clock\n";	generate(first,last,clock);	ostream_iterator<int> oit(cout," ");	copy(first,last,oit);	cout<<endl;}

用clock 函數返回值填充一個(gè)序列，即使編譯器“膽大包天”，也不敢猜測clock返回結果了～
多余的 name 參數和一些輸出語(yǔ)句是因為在release模式下，watch窗口中看不到值。
而__stdcall 是讓 MyGenerate后不生成多余的平衡堆棧代碼。

MyGenerate(v1,v1+3,”v1”);MyGenerate(v2,v2+3,”v2”);int r1 = dot_product(3,v1,v2);MyGenerate(v1,v1+3,”v1”);MyGenerate(v2,v2+3,”v2”);int r2 = dot_product<3>(v1,v2);cout<<r1<<endl;cout<<r2<<endl;

仍然不夠， 編譯器會(huì )將r2的計算，推遲到 cout<<r2<<endl;中，使得r2的計算不夠清晰。

所以我們再加入一個(gè)函數

void ForceCalcResult(int result) { }

強制編譯器立刻計算點(diǎn)積。
同時(shí)，使用函數指針調用，避免編譯器對該函數inline。

程序主干如下 ：

int main() {	const int dim = 3;	int v1[dim];	int v2[dim];void ( *const ForceCalcResult_non_inline)(int) = ForceCalcResult;	MyGenerate(v1,v1+dim,"v1");	MyGenerate(v2,v2+dim,"v2");	int r1 = dot_product(dim,v1,v2);	ForceCalcResult_non_inline(r1);	MyGenerate(v1,v1+dim,"v1");	MyGenerate(v2,v2+dim,"v2");	int r2 = dot_product<dim>(v1,v2);	ForceCalcResult_non_inline(r2);	cout<<r1<<endl;	cout<<r2<<endl;	return 0;}

//MyGenerate(v1,v1+dim,"v1");mov		eax,offset string "v1" (402134h) lea		edi,[esp+24h] lea		ebx,[esp+18h] call		MyGenerate<int *> (401220h) //MyGenerate(v2,v2+dim,"v2");mov		eax,offset string "v2" (402138h) lea		edi,[esp+18h] lea		ebx,[esp+0Ch] call		MyGenerate<int *> (401220h)

v1[0]:esp+18h, v1[1]:esp+1Ch, v1[2]:esp+20h, v1[dim]:esp+24hv2[0]:esp+0Ch, v2[1]:esp+10h, v2[2]:esp+14h, v2[dim]:esp+18h

//int r2 = dot_product<dim>(v1,v2);mov		edi,dword ptr [esp+10h] mov		edx,dword ptr [esp+14h] imul		edi,dword ptr [esp+1Ch] imul		edx,dword ptr [esp+20h] // edi = v2[1]*v1[1]// edx = v2[2]*v1[2]mov		eax,dword ptr [esp+0Ch] imul		eax,dword ptr [esp+18h] // eax = v2[0]*v1[0]add		edi,edx add		edi,eax // edi = edi+edx+eax = v2[1]*v1[1]+v2[2]*v1[2]+v2[0]*v1[0]

循環(huán)被解開(kāi)了！利用3個(gè)寄存器edi,edx,eax，最終結果應該是保存在edi中。
再看接下來(lái)的代碼

//ForceCalcResult_non_inline(r2);push		edicall		ForceCalcResult (401000h)

//int r1 = dot_product(dim,v1,v2);mov		esi,dword ptr [esp+10h] mov		eax,dword ptr [esp+14h] imul		esi,dword ptr [esp+1Ch] imul		eax,dword ptr [esp+20h] // esi = v2[1]*v1[1]// eax = v2[2]*v1[2]mov		ecx,dword ptr [esp+0Ch] imul		ecx,dword ptr [esp+18h] // ecx = v2[0]*v1[0]add		esi,eax add		esi,ecx // esi = esi+eax+ecx = v2[1]*v1[1] + v2[2]*v1[2] + v2[0]*v1[0]//ForceCalcResult_non_inline(r1);push		esi  call		ForceCalcResult (401000h)

幾乎相同的代碼，使用的是esi,ecx,eax，結果保存在esi中。
循環(huán)同樣被解開(kāi)了！

編譯器在我們的重重算計下，被迫在運行時(shí)計算結果，同時(shí)將運算方法展現出來(lái)；但同時(shí)，它依然不屈不饒的向我們展示它的強大優(yōu)化能力！

（詳細代碼見(jiàn)sample2）

驗證2+：

在驗證2中，編譯器知道了 const int dim = 3; 這一上下文。從而將普通循環(huán)版本的點(diǎn)積函數進(jìn)行展開(kāi)。

讓我們來(lái)看看，dim取更大值時(shí)，編譯器會(huì )如何。

dim=10：
普通“循環(huán)”點(diǎn)積計算被展開(kāi)，使用esi,eax,ecx,edx，10條mov與imul指令，9條add指令，最終將計算結果存入esi
模板元點(diǎn)擊計算也被展開(kāi)，使用edi,eax,ecx,edx，10條mov與imul指令，9條add指令，最終將計算結果存入edi

dim=11：
循環(huán)點(diǎn)積計算發(fā)生了變化，代碼如下：

//MyGenerate(v1,v1+dim,"v1");00401017  mov	eax,offset string "v1" (402134h) 0040101C  lea	edi,[esp+68h] 00401020  lea	ebx,[esp+3Ch] 00401024  call	MyGenerate<int *> (401280h) //MyGenerate(v2,v2+dim,"v2");00401029  mov	eax,offset string "v2" (402138h) 0040102E  lea	edi,[esp+3Ch] 00401032  lea	ebx,[esp+10h] 00401036  call	MyGenerate<int *> (401280h) // v1[0]:esp+3Ch, v2[0]:esp+10h//int r1 = dot_product(dim,v1,v2);0040103B  xor	ebp,ebp // int result = ebp=0;0040103D  xor	eax,eax // eax=0;0040103F  nop// align// i=eax;// loops:00401040  mov	ecx,dword ptr [esp+eax+10h]// ecx = *(v2+i);00401044  imul	ecx,dword ptr [esp+eax+3Ch]// ecx *= *(v1+i);00401049  add	eax,4// ++i;0040104C  add	ebp,ecx // result+=ecx0040104E  cmp	eax,2Ch // if (i<11)00401051  jl		main+30h (401040h) // goto loops;

編譯器已經(jīng)不能“忍受”這樣長(cháng)度的循環(huán)展開(kāi)，將其老老實(shí)實(shí)的翻譯成真正的循環(huán)。
但是，編譯器仍然對函數做了inline工作。

對于模板元解循環(huán)，因為代碼要求11層函數調用，編譯器能做的只有將11層調用inline，得到的是就地展開(kāi)的計算。

dim=12：

循環(huán)點(diǎn)積計算： 編譯器甚至連inline也不做了，進(jìn)行正式的函數調用。
模板元點(diǎn)擊計算：依然就地展開(kāi)。

dim=32：

循環(huán)點(diǎn)積計算：不展開(kāi)，調用
模板元點(diǎn)積計算：
比較有趣的是，編譯器也沒(méi)有將函數就地展開(kāi)，而是分成3步。就地計算前9個(gè)乘法然后與DotProduct<23,int>的返回值相加。DP<23>也沒(méi)有就地計算全部，而是計算前11個(gè)，然后與DP<12>的返回值相加。
3步計算當中都沒(méi)有循環(huán)。

值得注意的是，循環(huán)點(diǎn)積計算函數也沒(méi)有很老實(shí)的按照源代碼的方式進(jìn)行計算，而是進(jìn)行了不完全的循環(huán)展開(kāi)，類(lèi)似于如下代碼：

template< typename T>T dot_product(int DIM,const T v1[],const T v2[]) {	const int step = complierKnow;	T results[step] = {0};	int i=0;	for (;i+step-1<DIM;i+=step) {		results[0] += v1[i]*v2[i];		results[1] += v1[i+1]*v2[i+1];		...		results[step-1] += v1[i+step-1]*v2[i+step-1];	}	for (;i<DIM;++i)		results[0] += v1[i]*v2[i];	return results[0]+result[1]+...result[step-1];}

DIM和step似乎沒(méi)有什么固定的規律。

（詳細代碼見(jiàn)sample2，取不同的dim值即可。）

驗證3：

sample2中，編譯器對被計算的向量的上下文依然知情：v1,v2在main函數的棧中。

sample3做了小小的改動(dòng)：dot_product_loop和dot_product_unloop將無(wú)從得知傳遞給它們的向量在何處。（當然，在main函數中，仍然使用函數指針來(lái)調用這2個(gè)函數，使得編譯器不做inline）

sample3得到的結果和sample2基本相同，只是對向量尋址由esp+v1_offset,esp+v2_offset變?yōu)閇esp+4],[esp+8]

（詳細代碼見(jiàn)sampl3）

驗證4：

在sample3的基礎上，通過(guò)控制臺輸入讀取dim，使得編譯對其不知情。
當然，在這種情況下，是無(wú)法使用模板元解循環(huán)的，因為它要求dim是編譯時(shí)常量。

在這種情況下，循環(huán)點(diǎn)積計算終于被編譯器翻譯成真正的“循環(huán)”了。

總結：

循環(huán)版本有更大的靈活性：在dim為編譯時(shí)常量時(shí)，編譯器會(huì )根據其大小，進(jìn)行完全解循環(huán)或部分解循環(huán)。同時(shí)也支持dim為運行時(shí)的值。
模板元版本必須使用編譯時(shí)常量作為dim，而且總是完全解開(kāi)循環(huán)。

循環(huán)版本與模板元版本最終都會(huì )使用相同次數的乘法與運算，區別在于乘法指令和跳轉指令的數目。
模板元版本在dim較大的時(shí)候，可能會(huì )使用跳轉指令，將部分工作交給更小維度的點(diǎn)積計算。但是乘法指令數目與維數一樣。
循環(huán)版本可能會(huì )使用更多的跳轉指令，使得乘法指令數目大大減少。

多出的跳轉指令會(huì )占用運行時(shí)間，但也能減少目標代碼體積。權衡應該使用那一種版本與權衡某個(gè)函數是否應該inline十分相似。
書(shū)中17章最后部分也提醒讀者，不計后果的解循環(huán)并不總是能優(yōu)化運行時(shí)間。

借用大師的觀(guān)點(diǎn)來(lái)結束本文 —— 優(yōu)化的第一原則是：不要優(yōu)化。優(yōu)化的第二原則（僅適用于專(zhuān)家）是：還是不要優(yōu)化。再三測試，而后優(yōu)化。
《C++編程規范》 第8條