東方和風語: Practical Java Programming Language Guide-第四章效率

昨天回宿舍後我開始在想，我打這些文章有什麼意義，只是點出大概不如直接去看書
而我只需要推薦書就好，將裡面的內容打出來是否多此一舉
後來我想過了，既然要做就貫徹到底，這些文章不只是為了分享，更是為了驗證我倒底對看過的書理解了沒，這是個隨手筆記，加深我對書中的內容的印象才是我打出這些文章的目的

這個章節個人認為是這本書裏面最有趣的一章，他提到很多對performanace如何改進的手法，提供當我們要最佳化程式的時候一種思維，我們重構程式其中一個目的，不就是為了讓最佳化更有彈性嗎?

書中提到，要最佳化有幾個手段，像是最佳化用編譯器最佳化bytecode或是最佳化JVM，但是最常用的仍應該是手動最佳化自己的程式碼，程式效率往往被不佳的設計給破壞掉

java要驗證效率最簡單的方法就是去抓時間差，以前我用C#測試演算法的時候也常用這套手法
不過java的System.currentTimeMillis()精準度不是很高，印象中只有40毫秒
C#雖然也差不多但是他可以抓kernel的timegettime等函式來將精準度提升到毫秒甚至微秒
如果要寫FPS遊戲計算FPS的話務必用kernel提供的函式才能正確計算


long begin=System.currentTimeMillis();
//do something
System.out.println(System.currentTimeMillis()-begin);

case 28：先把焦點放在設計、資料結構和演算法身上
這個case一開始用一句話開頭

大約97%的時間裡，我們應該忘掉小幅效率這東西，過早最佳化是一切錯誤根源
We should forget about small efficiencies,about 97% of the time.
Premature optimization is the root of all evil.

主要是說不要為了那一點點不可靠的效率而放棄了良好的設計，這將使程式碼難以閱讀及最佳化
典型情況80~90%的程式執行時間是花在10~20%的程式碼身上(80-20法則)
這點在許多重構或是XP的書也都有提及
高效能程式碼與三個原則息息相關

良好的設計

明智的選擇資料結構(data structures)

明智的選擇演算法(algorithm)

case 29：不要依賴編譯期(Compile-time)最佳化技術
這個case提到，編譯器最佳化的效果有限，比起依賴他不如手動最佳化
舉個例子


void f(){
  int a=10;
  int b=20;
  int arr[20000];
  for(int i=0;i<20000;i++)
  {
    arr[i]=a+b;//效率低
  }
}
////////////////
void f(){
  int a=10;
  int b=20;
  int c=a+b;
  int arr[20000];
  for(int i=0;i<20000;i++)
  {
    arr[i]=c;//改良
  }
}

諸如此類，一點點改變就能提高程式碼效率
java要最佳化bytecode的方法是利用 -o這個參數
javac -o XXX.java
但是書上有提到他帶來的效果極低，而且對大多數的bytecode這選項也無法做到實質的提升，所以也有人提倡捨棄他
最後提到了幾個最佳化程式的選擇

手工最佳化程式碼

使用第三方最佳化編譯器(thrid-party optimizing compiler)將原始碼最佳化

依賴JIT或是Hotspot等執行期最佳化策略

case 30：理解執行期(runtime)程式碼最佳化技術
這篇提到使用JIT來提升執行效率的相關議題，優秀的JIT可以提升效能，但是要啟動JIT也要付出相對的代價

case 31：要進行字串接合，StringBuffer優於String
這個幾乎每本java的書都會提到


String buf="Hello";
buf+=" Tom";

效能比不上


StringBuffer buf=new StringBuffer("Hello");
buf.append(" Tom");

因為String是不可變的，他每次都會產生一個新的字串來當接合的結果，而非擴展原物件
String在做字串接合時，會先new一個StringBuffer 再用他的append，再用toString()回傳接合結果，短短一行程式碼就做了三個步驟，這效率非常恐怖

case 32：將物件的創建成本降到最小
簡單來說，慎用new產生物件
物件創造幾個步驟

從Heap中配置記憶體，用以存放全部的instance變數及物件的superclass的實作專屬資料(implementation-specific data)，包括指向"class and method data"的指標

將物件的instance變數初始化其相應的預設值

叫用most derived class(最深層延伸類別)的建構式。建構式第一個要做的就是呼叫superclass的建構式，此過程反覆直到呼叫到java.lanh.Object的建構式為止

在建構式本體執行之前，所有的instance變數初始值設定跟初始化區段(initialization block)先換得執行，之後才執行建構式本體。

舉個例子



...
long begin=System.currentTimeMillis();
for(int i=0;i<20000000;i++)
{
 //什麼都不做的for迴圈跑兩億次
}
System.out.println(System.currentTimeMillis()-begin);
//印出結果：141毫秒
...
long begin=System.currentTimeMillis();
for(int i=0;i<20000000;i++)
{
     int j=0;
     j+=i;
     //產生一個local變數跟一個簡單的運算
}
System.out.println(System.currentTimeMillis()-begin);
//印出結果：156毫秒

...
class Base{//這是一個什麼都沒有的類別 
}
long begin=System.currentTimeMillis();
for(int i=0;i<20000000;i++)
{
  new Base();//創建一個空類別的for迴圈跑兩億次
}
System.out.println(System.currentTimeMillis()-begin);
//印出結果：1516毫秒

這之間的差距非常明顯，而這只是創建一個什麼都沒有的空類別就有如此差距

書中提到以下特徵會增加物件的創建成本

建構式中有大量程式碼

類別有數量眾多或是體積龐大的member物件，他的初始化是建構式的一部份

太深的繼承階層(inheritance hierarchy)

case 33：慎防未用上的物件
小心不要創造無謂甚至會擱置太久的物件，會增加不必要的成本

case 34：將同步化(synchrinization)降至最低
多執行緒的同步化會對效能有很大的傷害，應該盡量避免
因為lock的或取還是釋放都是一個高成本的動作
簡單舉個例子


class Foo{
   void run(){};//一個空函式
}
...
Foo f=new Foo();
long begin=System.currentTimeMillis();
for(int i=0;i<20000000;i++)
{
    f.run();
}
System.out.println(System.currentTimeMillis()-begin);
//印出結果：203毫秒
...
class Foo{
   synchronized void run(){};//有synchronized修飾的空函式
}
...
Foo f=new Foo();
long begin=System.currentTimeMillis();
for(int i=0;i<20000000;i++)
{
    f.run();
}
System.out.println(System.currentTimeMillis()-begin);
//印出結果：10594毫秒
...

看到沒有!竟然有如此的差距，比建構式還恐怖，多緒的時候要很小心諸如此類陷阱
為了提升效率而使用多緒執行反而降低了執行效率

之後書中有提到一些容器的效能
array比ArrayList快，ArrayList又比Vector快上兩倍，對於容器的選擇應該謹慎

case 35：盡可能使用stack變數
嗯...這個case是說JVM是一種stack-based的虛擬機器，因此取用stack data的時候效率最佳
如果想從constant pool存取實體變數還是static變數的時候效率會沒那麼好
直接來實地測是一下


int var=0;//stack 變數
long begin=System.currentTimeMillis();
for(int i=0;i<20000000;i++)
{
    var++;
}
System.out.println(System.currentTimeMillis()-begin);
//印出結果：204毫秒
...
class VData{
 int _var;//instance變數
}
....
long begin=System.currentTimeMillis();
VData var=new VData();
for(int i=0;i<20000000;i++)
{
    var._var++;
}
System.out.println(System.currentTimeMillis()-begin);
//印出結果：641毫秒
...
static int v=0;//靜態變數
long begin=System.currentTimeMillis();
VData var=new VData();
for(int i=0;i<20000000;i++)
{
    v++;
}
System.out.println(System.currentTimeMillis()-begin);
//印出結果：609毫秒

case 36：使用static、final和private修飾讓函式inline
也就是說當函式有static或final、private等修飾的時候，他會變成inline候補
這樣可以提升效率，不過他只是成為候補，如果函式內容太複雜仍然不會inline
這個在重構的Extract Method的時候很好用
實地測是一下


class Foo{
   void run(){};//一個空函式
}
...
Foo f=new Foo();
long begin=System.currentTimeMillis();
for(int i=0;i<20000000;i++)
{
    f.run();
}
System.out.println(System.currentTimeMillis()-begin);
//印出結果：203毫秒
...
class Foo{
  static void run(){};//加上static
}
...
Foo f=new Foo();
long begin=System.currentTimeMillis();
for(int i=0;i<20000000;i++)
{
    f.run();
}
System.out.println(System.currentTimeMillis()-begin);
//印出結果：141毫秒

就像這樣，程式碼效能獲得提升

case 37：instance變數初使化一次就好
由於建構式是一個高成本的動作，不要讓他做多於的指派
跟C++不同，java再創建物件的時候就會給變數預設值像是，0,false,null等等
除非要透過建構式給予新值，否則不應該在給予重複的預設值
書中舉了兩個簡單的例子


class Foo{
    private int count;
    private boolean done;
    Foo(){
        //多此一舉
       count=0;
       done=false;
    }

}


class Foo{
    //多此一舉
    private int count=0;
    private boolean done=false;
}

諸如此類，對於同個變數賦予相同的初始值，因為java自動會給予
不過這點是有盲點的，在標準化編程裡面，有人提倡程式碼行為應該一致
因而不贊成這種論點


class Foo{
    private int count;
    private ArrayList list;
    Foo(){
         list=new ArrayList();
   }
}

如上面例子，既然list在Constructor裡面作初始化動作，為何cout不做
諸如此類的程式碼行為不一致，也有人提倡不該為了讓那一點幾乎看不見的效率破壞了程式碼的可讀性

case 38：使用基本型別(primitive types)使程式碼更快更小
用前面提過的一個例子


int i=5;
Integer j=new Integer(10);

基本型別小巧快速，是很多人的最愛
接下來實地探測一下


static int usePrimitive(int income)  //Primitive
{
 int i=5;
 i+=income;
 return i;
}
static int useObject(Integer income) //Object
{
 int i=5;
 i+=income.intValue();
 return i;
}
...
long begin=System.currentTimeMillis();
for(int i=0;i<200000000;i++)
{
 usePrimitive(1);
}
System.out.println(System.currentTimeMillis()-begin);
//印出結果：156毫秒
...
long begin=System.currentTimeMillis();
for(int i=0;i<200000000;i++)
{
 useObject(1);
}
System.out.println(System.currentTimeMillis()-begin);
//印出結果：422毫秒

但是同上一個case，這之中會有讓程式碼難以重構的可能性
太過依賴primitive也不好，在重構(Refactoring)中提到，這犯了基本型別偏執(Primitive Obsession)這個壞味道

case 39：不要使用Enumeration或Iterator來尋訪Vector
Vector提供幾種尋訪的方法

Iterator

ListIterator

Enumeration

get()函式

書中提到Enumeration比兩個Iterator快了約12%，get()函式則比其他三個快了29%~34%
這邊就不實地測試了

case 40：使用System.arraycopy()來複製arrays
System.arraycopy()是以原生函式(native method)實作，他的效率會比一般for迴圈指定更快
測試內容

使用for迴圈


int [] arr1=new int[10];
int [] arr2=new int[10];
long begin=System.currentTimeMillis();
for(int i=0;i<200000000;i++)
{
      for(int j=0;j<arr1.length;j++)
      {
  arr2[j]=arr1[j];//size為10空陣列的copy，使用for迴圈
      }
}
System.out.println(System.currentTimeMillis()-begin);
//印出結果：9672毫秒
...
int [] arr1=new int[20];
int [] arr2=new int[20];
long begin=System.currentTimeMillis();
for(int i=0;i<200000000;i++)
{
      for(int j=0;j<arr1.length;j++)
      {
  arr2[j]=arr1[j];//size為20空陣列的copy，使用for迴圈
      }
}
System.out.println(System.currentTimeMillis()-begin);
//印出結果：17344毫秒
...
int [] arr1=new int[50];
int [] arr2=new int[50];
long begin=System.currentTimeMillis();
for(int i=0;i<200000000;i++)
{
      for(int j=0;j<arr1.length;j++)
      {
  arr2[j]=arr1[j];//size為50空陣列的copy，使用for迴圈
      }
}
System.out.println(System.currentTimeMillis()-begin);
//印出結果：43203毫秒

使用System.arraycopy();


int [] arr1=new int[10];
int [] arr2=new int[10];
long begin=System.currentTimeMillis();
for(int i=0;i<200000000;i++)
{
        //size為10空陣列的copy，使用System.arraycopy();
 System.arraycopy(arr1, 0, arr2, 0, arr1.length);
}
System.out.println(System.currentTimeMillis()-begin);
//印出結果：11188毫秒
...
int [] arr1=new int[20];
int [] arr2=new int[20];
long begin=System.currentTimeMillis();
for(int i=0;i<200000000;i++)
{
        //size為20空陣列的copy，使用System.arraycopy();
 System.arraycopy(arr1, 0, arr2, 0, arr1.length);
}
System.out.println(System.currentTimeMillis()-begin);
//印出結果：12453毫秒
...
int [] arr1=new int[50];
int [] arr2=new int[50];
long begin=System.currentTimeMillis();
for(int i=0;i<200000000;i++)
{
        //size為50空陣列的copy，使用System.arraycopy();
 System.arraycopy(arr1, 0, arr2, 0, arr1.length);
}
System.out.println(System.currentTimeMillis()-begin);
//印出結果：15546毫秒

令人訝異的結果，在size為10的時候，使用for迴圈竟然比System.arraycopy()還快
但是隨著資料的增長，System.arraycopy的效率卻遠遠超越for迴圈

這或許意味著在少量的copy時候，可以使用for迴圈，但是到了大量資料copy的時候，for迴圈就變得相當沒有優勢並且非常的耗時間。

筆者我對System.arraycopy相當有印象，以前我寫過一個排版的函式，他必須做字串接合，那段時間研究了很多作法，還去看了StringBuffer跟StringUtil的source code，他裡面就是用System.arraycopy對char 陣列作多次copy來完成字串接合
我把當時寫的原始碼分享給大家看，這是參考各家網路版本跟StringUtil等source code所挑出速度最快的版本


 //將字串最大長度固定的函式 不足以空白補齊
 private String getLayoutString(String temp,int spaceNum)
 {
  if(temp==null)
  {
   return null;
  }
  int pads=spaceNum-temp.length();
  if(pads<=0)
  { //: 字串長度大於指定長度直接回傳
   return temp;
  }
  else
  {
   return padRe(temp,spaceNum);//spaceNum是要填充的字元
  }
 }

private char[] buffer = new char[0];
   public String pad(String str, char ch, int size){
     if(buffer.length < size) buffer = new char[size];
     if(size <= str.length()) return str;

     System.arraycopy(str.toCharArray(), 0, buffer, 0, str.length());
     java.util.Arrays.fill(buffer, str.length(), size, ch);
     return new String(buffer);
   }

case 41：優先使用array，然後再考慮Vector和ArrayList
主要是在說上面提到的array>ArrayList>Vector
其中Vector效率會差的的原因他的get()函式是synchronized，synchronized會讓函式效率低下

case 42：盡可能reuse物件
當物件非常龐大且非常耗效能的話，創造之後究竟可能共用
像是寫一個遊戲，對Image或是Sound的存取是非常耗時間的一件事，通常會有個pool，創造之後就放進pool讓大家共用

case 43：使用緩式評估(延遲求值，lazy evaluation)
當某件事非常龐大的時候，就讓他晚點執行，或是需要他的時候才執行
這個方法最典型的就是四人當的提出的Design Pattern裡面的Proxy
現在的Web Service的使用大概都是依照這個Pattern去實作出來的
把遠端的呼叫放到真正要取用的時候才去開啟
我簡單模擬一下(我自己想的例子，真實情況應該會更複雜)


class Service{
   Socket request;
 ....
   public void Request(String url)
   {
       if(request==null)request=new Socket(url);
       ....
   }

}

類似這樣，平常就讓他保持null的狀態，真正需要的時候才去產生他

case 44：以手工坊是將程式碼最佳化
上面有提過，編譯器提供的最佳化效果有限，他提出了幾個簡單最佳化的方法
我就直接用程式碼舉例子了

剔除空白函式(Empty method removal)

class Test{ void foo(); }
如上，儘管foo()函式空空如也，但是main仍回呼叫他們，將他移除替.class瘦身

剔除無用程式碼(Dead code removal)

for(int i=0;i<size;i++){ if(i<0)return; //do something }
可修改為
for(int i=0;i<size;i++){ //do something }
將永遠不會執行的程式碼刪除，書中提到替上面的for迴圈瘦身後執行效率可提高4%

削減強度(Strength reduction)

以效率更高的操作取代昂貴的動作
由於以前我對這方面都沒去注意，做個記號警惕一下
舉個例子
for(int i=0;i<N;i++) { a=a+b; }
改成
for(int i=0;i<N;i++) { a+=b; }
書中提到新版本會比就版本快10%，而且可以替bytecode瘦身
有很多operaror都是不同的動作同樣的效果，但是會有不同的效率

合併常數(Constant folding)

這個也蠻重要的，對於一些不變的變數加上final修飾，可以使他最佳化
static int a=30; static int b=60; int c=a+b;
可以改成
static final int a=30; static final int b=60; int c=a+b;
加上final修飾之後就可以讓bytecode得到最佳化

刪減相同的子運算式(Common subexpression elimination)

簡單來講就是刪除同樣的運算
arr[i+1].foo(1); arr[i+1].foo(2); arr[i+1].foo(3); arr[i+1].foo(4);
可以改成
int k=i+1; arr[k].foo(1); arr[k].foo(2); arr[k].foo(3); arr[k].foo(4);
不過在Refatoring裡面有提到可以用Query取代暫存變數，因為不用為了這一點雞毛蒜皮的效率犧牲程式碼的可讀性

展開迴圈(Loop unrolling)

迴圈小且固定的時候，可以展開以提升效率
for(int i=0;i<3;i++)arr[i]=10;
可以改成
arr[0]=10; arr[1]=10; arr[2]=10;

簡化代數(Algebraic simplification)

運算上的簡化
int x=(f*a)+(f*b)+(f*c);
改進
int x=f*(a+b+c);

移動迴圈內的不變式(Loop invariant code motion)

int a=10; int b=20; for(int i=0;i<3;i++) x=a+b;
可以改成
int a=10; int b=20; int c=a+b; for(int i=0;i<3;i++) x=c;
不過同樣的，以重構的想法是盡量去減少暫存變數，不須要為了那一點點效率犧牲了重構的可能性，暫存變數太多會讓重構變的困難

case 45：編譯為原生碼(Compile to native code)
書中提到有些程式設計師相信有必要的話，可以犧牲java的可移植性，直接編譯程原生碼(native binary code)來換取更高的效率。

東方和風語

2009年5月13日星期三

Practical Java Programming Language Guide-第四章效率

剔除空白函式(Empty method removal)

剔除無用程式碼(Dead code removal)

削減強度(Strength reduction)

合併常數(Constant folding)

刪減相同的子運算式(Common subexpression elimination)

展開迴圈(Loop unrolling)

簡化代數(Algebraic simplification)

移動迴圈內的不變式(Loop invariant code motion)

沒有留言:

最新文章

學習手札

下拉式標籤

個人連結

網誌存檔

追蹤者