性能問題也不是僅僅用“技術”可以解決的，它往往是架構，測試，假設等綜合難題。不過，對於一個工程師來說，必須從小做起，把一些“明顯”的小問題解決。否則的話積小成多，千裡堤壩，潰於蟻穴。
C++ 的性能為什麼總是排在C之後 （見http://benchmarksgame.alioth.debian.org/u32/performance.php?test=binarytrees 等網站的最新測試結果）？我認為這是3個方面的原因：
1）用於測試的C++ 編譯器沒有使用最新的優化技術
2）C++ 附加的價值沒有考慮到測試之中
3）C++ 應用層面的“微妙性”（可參考我的關於C++的其他博客）使得一般程序員往往望而卻步，選擇“教科書用例”，使得一些副作用沒有在應用層面被剔出。
記得10多年前，我在微軟做開發時，曾向C++最早編譯器的作者李伯曼（Stan Lippman）(時任微軟VC++架構師）咨詢過一系列我們小組的C++性能難題，在他的幫助下，我們在關鍵地方用了諸如inline,RVO等技術，完全解決了性能問題，還找出了VC++ 的幾個不小的錯誤。我認識到，C++的性能問題多數在於我們對C++認識的淺薄，多數都是不難解決的。
下面用一例子，來做一下對比，看看一些微妙的細節是如何影響程序性能的。
struct intPair
{
int ip1;
int ip2;
intPair(int i1, int i2) : ip1(i1), ip2(i2) {}
intPair(int i1) : ip1(i1), ip2(i1) {}
};
// Calc sum (usinh value semantic)
Int Sum1(intPair p)
{
return p.ip1 + p.ip2;
}
// Calc sum (usinh ref semantic)
int Sum2(intPair &p)
{
return p.ip1 + p.ip2;
}
// Calc sum (usinh const ref semantic)
Int Sum3(const intPair& p)
{
return p.ip1 + p.ip2;
}
上面這個簡單的struct，有三個Sum函數，作的事情完全一樣，但是性能是否一樣呢？我們用下面的程序來測試：
double Sum(int t, int loop)
{
using namespace std;
if (t == 1)
{
clock_t begin = clock();
int x =0;
for(int i = 0; i < loop; ++i)
{
x += Sum1(intPair(1,2));
}
clock_t end = clock();
return double(end - begin) / CLOCKS_PER_SEC;
}
else if (t == 2)
{
clock_t begin = clock();
int x =0;
intPair p(1,2);
for(int i = 0; i < loop; ++i)
{
x += Sum1(p);
}
clock_t end = clock();
return double(end - begin) / CLOCKS_PER_SEC;
}
else if (t == 3)
{
clock_t begin = clock();
int x =0;
intPair p(1,2);
for(int i = 0; i < loop; ++i)
{
x += Sum2(p);
}
clock_t end = clock();
return double(end - begin) / CLOCKS_PER_SEC;
}
else if (t == 4)
{
clock_t begin = clock();
int x =0;
intPair p(1,2);
for(int i = 0; i < loop; ++i)
{
x += Sum3(p);
}
clock_t end = clock();
return double(end - begin) / CLOCKS_PER_SEC;
}
else if (t == 5)
{
clock_t begin = clock();
int x =0;
for(int i = 0; i < loop; ++i)
{
x += Sum3(10);
}
clock_t end = clock();
return double(end - begin) / CLOCKS_PER_SEC;
}
return 0;
}
我們用了5個案列，對Sum1和Sum3 風別用了兩種調用方式，對Sum2用了一種調用方式。我們測試了10萬次調用：
double sec = Sum(1, 100000);
printf("Sum1 (use ctor) time: %f \n", sec);
sec = Sum（2, 100000);
printf("Sum1 (use no c'tor) time: %f \n", sec);
sec = Sum(3, 100000);
printf("Sum2 time: %f \n", sec);
sec = Sum(4, 100000);
printf("Sum3 without conversion time: %f \n", sec);
sec = Sum(5, 100000);
printf("Sum3 with conversion time: %f \n", sec);
我們在VisualStidio 2010 中測試，結果是：
用例1 18ms
用例2 9ms
用例3 6ms
用例4 7ms
用例5 12ms
也就是說：用例1和5最慢，其他基本沒有差別。
細心的讀者不難看出，
1）用例5的性能問題，是因為Sum3用了C++的implicit conversion ，將整數自動轉化成intPair 的臨時變量。這是一個應用層面的問題，如果我們不得不將整數作這個轉換，也就不得不付出這個性能上的代價。
2）用例1的問題和5類似，都是因為不得不每次創建臨時變量。當然，可以強迫constructor inline 來使得臨時變量的生成成本降低。
3）用例2用了在函數調用前了編譯自生的copy constructor，不過因為 intPair object 很小，影響可以忽略不計了。
4）用例3性能是穩定的，但是它用了“間接”方式（詳情請看我關於reference的博克），所以產生的指令比用例2多兩條。但對性能的影響不大，估計和Intel的L1，L2 緩存有關。
*注意到OOP函數如果僅僅對 this 的成員存取數據，一般可以充分利用緩存，除非 object 過大。
5）用例4 和用例3生成代碼完全一樣，應該沒有差別。const 只是編譯時有用，生成的代碼與const 與否無關。
性能問題的話題太多，本文只是蜻蜓點水，但是已經觸及了C++的兩個最大的性能隱患：
a) 臨時變量
b) Implicit conversion (沉默轉換)
2014-6-20 西雅圖
沒時間幫你寫程序需說個思路就閃人了 你先把3種排序的書上的例子抄下來 寫成3個函數， 每個函數裡面開頭和結尾取一次系統時間 最後相減得出開銷時間 在打印出來
我把網上的程序修改了一下，並整合了，你看看
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define M 50
#define MAX 100000;
typedef struct
{
int weight;//結點權值
int parent,lchild,rchild;
}HTNODE,*HUFFMANTREE;
typedef char** HUFFMANCODE;//動態分配數組存儲哈夫曼編碼表
typedef struct
{
int key; /*關鍵字*/
}RecordNode; /*排序節點的類型*/
typedef struct
{
RecordNode *record;
int n; /*排序對象的大小*/
}SortObject; //待排序序列
HUFFMANTREE huffmantree(int n,int weight[])//構建哈夫曼樹
{
int m1,m2,k;
int i,j,x1,x2;
HUFFMANTREE ht;
ht=(HUFFMANTREE)malloc((2*n)*sizeof(HTNODE));
for(i=1;i<(2*n);i++)//初始化哈夫曼樹中各結點的數據，沒初始值的賦值為0
{
ht[i].parent=ht[i].lchild=ht[i].rchild=0;
if(i<=n)
ht[i].weight=weight[i];
else
ht[i].weight=0;
}
for(i=1;i<n;i++)//每一重循環從森林中選擇最小的兩棵樹組建成一顆新樹
{
m1=m2=MAX;
x1=x2=0;
for(j=1;j<(n+i);j++)
{
if((ht[j].weight<m1)&&(ht[j].parent==0))
{
m2=m1;
x2=x1;
m1=ht[j].weight;
x1=j;
}
else if((ht[j].weight<m2)&&(ht[j].parent==0))
{
m2=ht[j].weight;
x2=j;
}
}
k=n+i;
ht[x1].parent=ht[x2].parent=k;
ht[k].weight=m1+m2;
ht[k].lchild=x1;
ht[k].rchild=x2;
}
return ht;
}
void huffmancoding(int n,HUFFMANCODE hc,HUFFMANTREE ht,char str[])
{
int i,start,child,father;
char *cd;
hc=(HUFFMANCODE)malloc((n+1)*sizeof(char*));//分配n個字符編碼的頭指針
cd=(char*)malloc(n*sizeof(char));//分配求編碼的工作空間
cd[n-1]='\0';//編碼結束符
f......余下全文>>
