2011年6月30日 星期四

Effective Java 讀書筆記: Item 8 - 覆寫 equals 時的注意事項

記錄讀書心得, 內容不一定和書上一致, 有些是我自己的看法。

先看個範例, 取自 AbstractSet 補加個 @Override:
@Override  // #1
    public boolean equals(Object o) {
        if (o == this)  // #2
            return true;

        if (!(o instanceof Set))  // #3
            return false;
        Collection c = (Collection) o;  // #4
        if (c.size() != size())  // #5
            return false;
        try {
            return containsAll(c);  // #6
        } catch (ClassCastException unused)   {
            return false;
        } catch (NullPointerException unused) {
            return false;
        }
    }
覆寫 equals 時的注意事項:
  1. 加 @Override 確保沒覆寫錯 method, 常見錯誤是參數寫成 MyClass o
  2. 先比 reference, 比較有效率
  3. 再來要檢查型別。由於 null 不屬於任何 class 或 interface, 用 instanceof 也可確保傳入的物件不是 null, 不必多加一步檢查 null
  4. 若是 interface 就轉 interface, 再用 method 比較; 若是 class 就能直接取 field 比值。比 field 時可用這個寫法同時考慮 null 的情況:
    (field == o.field || (field != null && field.equals(o.field))) 
  5. 先比低運算成本的項目。hashCode 或一些 summary value 是不錯的選擇
  6. 再比高運算成本的項目
  7. 寫 unit test 檢查 symmetric、transitive、consistent
  8. 有覆寫 equals 時, 一定要覆寫 hashCode (見 item 9)

2011年6月29日 星期三

Effective Java 讀書筆記: Item 7 - 別用 finalizer

記錄讀書心得, 內容不一定和書上一致, 有些是我自己的看法。

這篇有好幾頁, 但中心思想只有一句: 不要用、不要用、不要用。

若你堅持要用, 作者告訴你:
  • 沒人保證 finalizer 什麼時候被呼叫, 這表示若你用它來解 lock, 等著大家一起被鎖死。若你用它釋放記憶體, 有可能在執行 finalizer 途中不足記憶體然後掛掉
  • 當 finalizer 被呼叫時, 發生 uncaught exception 不會讓程式掛掉, 也不會丟出警告或錯誤訊息。之後程式若再用到同一物件, 沒人能說得準到底會發生什麼事
  • 用 finalizer 會拖慢速度, 作者測試建立和待一個物件被 gc, 有無用 finalizer 的時間比是 2,400ns vs 5.6ns
所以結論就是: 不要用、不要用、不要用。

若有需要釋放的資源, 明確地用 try { ... } finally { ... } 在 finally 裡執行較好, 不論有無 exception, 保證會執行 finally 裡的程式。題外話, Python 也有 finally 的語法, 並且在 2.6 開始多了 with 的語法 (2.5 也可「試用」這個語法)。with 相較於 finally, 明確地定義一個物件的生命週期, 並提供開始和結束的 hook, 方便控管資源的生成和銷毀。滿不錯的 syntax sugar。
回歸正題。那麼, finalizer 這麼雞肋的功能, 到底有什麼用? 答案是
  • 有總比沒有好, 用 finalizer 順手釋放資源 (如 file), 並 log warning, 這樣開發者就知道要該補上這個操作
  • 若有用到 native object (gc 不認得的東西), 得自己善後。在 finalizer 中做補救的動作, 不知何時釋放總比永遠不釋放來得好
實作 finalizer 時要注意, 它不會自動呼叫 superclass 的 finalizer, 要自己在 finally 裡呼叫:
try {
    ...
} finally {
    super.finalize();
}
或是用 "finalizer guardian" 保證執行 finalizer
class Class Foo {
    private final Object finalizerGuardian = new Object() {
        @Override protected finalize() throws Throwable {
            // Finalize outer Foo object.
        }
    }
}
這招還滿帥的, 不知什麼場合可以套用這個概念, 用在別的地方。

備註: 經 kcwu 提醒, Python 的 object.__del__(self) 行為和 Java 的 finalizer 相似, 雖然看起來有比較好, 但還是不夠可靠, 盡量別用比較好。

在 Ubuntu 上裝 CPAN

查太多次了, 乾脆記下來 (ref.)。
  1. sudo aptitude install build-essential
  2. cpan
  3. make install
  4. install Bundle::CPAN
  5. install X # 安裝 module X
若日後想重設 config (像是重設 CPAN server 列表), 進 cpan 後打 "o conf init" 再打 "no", 就會重回答一次設定問題。

2011-06-29 更新

DK 在留言提到改用 cpanm 較好, 之後來試試。

Effective Java 讀書筆記: Item 6 - 小心 memory leak

記錄讀書心得, 內容不一定和書上一致, 有些是我自己的看法。

即使 Java 有 gc, 仍然有可能寫出「memory leak」。描述不如看 code:

public class Stack {
    private Object[] elements;
    // ...
    public Object pop() {
        if (size == 0)
            throw new EmptyStackException();
        return elements[--size];
    }
   // ...
}

elements 會一直留著 push 進來的 objects, 形成 memory leak。解法就是在 pop 裡面將 elements[size] 設為 null:

public Object pop() {
        if (size == 0)
            throw new EmptyStackException();
        Object result = elements[--size];
        elements[size] = null;
        return result;
    }

作者強調, 別矯枉過正四處狂設 null, 反而會讓程式很難讀。大部份情況讓物件離開 scope 自然地被回收即可。

幾個要點:

  • 若 class 自己有管記憶體 (比方說 object pool), 開發者就該留意 memory leak, 記得設 null
  • cache 常造成 memory leak。特殊情況下可用 WeakHashMap 自動解套。我還在參透 WeakHashMap 的效果和對應的情境, 以及為何它能做到這樣的效果。
  • listener 和 callback 也常造成 memory leak
  • 可用 heap profiler 找 memory leak

2011年6月28日 星期二

Effective Java 讀書筆記: Item 5 - 避免生成不必要的物件

記錄讀書心得, 內容不一定和書上一致, 有些是我自己的看法。

這一則比較冗, 有許多零碎的小例子:
  • 經典反面例子: 「String s = new String("...");」, 改用「String s = "...";」較好。這讓我相當地不解, 那為什麼需要這種 constructor?
  • immutable 物件較容易避免生成不必要的物件
  • 如同 item 1 所言, 可用 static factory method 避免生成不必要的物件。Integer.valueOf 和 Boolean.valueOf 是典型的例子
  • 若 mutable 物件之後不會再被修改, 也可配合 final 或 static 共用物件 (case by case)
  • 「不再會被修改的 mutable object」的其它例子:
    • 如 adapter pattern 中的 backing object (backing object: 實際提供功能的物件)
    • 對同一實作 Map 的物件呼叫 keySet() 取得的 Set, 雖然是 mutable object, 但它們的內容卻都一致
  • 小心 autoboxing。下面的程式碼生成一萬次不必要的 Long object, 只因為 sum 誤宣告成 "Long"
    Long sum = 0L;
    for (long i=0; i<10000; i++)
        sum += i
    
  • 近代 JVM 的 garbage collection 能力很優異, 除非生成物件成本很貴 (如 database connection), 不然別自己搞 object pool, 提高維護成本而且不見得會變快
  • 這個守則和 item 39 defensive copying 相反, 自行判斷使用時機: 不小心改變物件造成 bug 的成本 vs. 多生成物件增加的時間, 通常是前者比後者慘。這麼說來, 這個守則除提醒一些小細節外, 似乎是寫心酸的啊。

2011年6月27日 星期一

Effective Java 讀書筆記: Item 4 - 避免 class 生成物件的做法

記錄讀書心得, 內容不一定和書上一致, 有些是我自己的看法。

有時會會需要一堆 static methods 或 members, 而不需生成物件, 像是寫一堆數學函式。但 Java 規定所有東西都要放在 class 裡, 只有 method, 沒有 function。所以, 需要寫這類功能時, 為了確保使用 API 或開發 API 的人不會不小心生成物件, 記得要封印 constructor:
  • 明確寫 default constructor, 並設存取級別為 private, 防止 API 使用者生成物件
  • 在 default constructor 裡丟出 exception, 避免開發 API 的人生成物件
第二點附帶的好處是, 讓這個 class 無法被繼承。不過這附帶好處滿弱的, 不如在 class 前加上 final 來得明確。

Effective Java 讀書筆記: Item 3 - singleton 實作技巧

記錄讀書心得, 內容不一定和書上一致, 有些是我自己的看法。

書中先提到使用 singleton 的缺點: 會難以測試程式。畢竟, 使用 singleton 的必要條件是設定 constructor 的存取級別為 private。若要減輕這個問題, 可幫 singleton 加上 interface, 而不是直接用 singleton 的 class 來使用它的 methods。不過我想沒什麼人會想這麼做, 要寫兩套 signature, 挺麻煩的。

查了一下相關資訊, EasyMock 有提到它無法 mock private 或 final method (見 官網文件的 "Class Mocking Limitations" ), 看來 EasyMock 是用繼承的方式 mock class, 所以有此限制吧。vgod 提到 PowerMock 可 mock private, final, static methods, 官網提到它的作法是換掉 class loader, 有機會再來試試。至少知道還是有辦法測試 singleton, 只是可用手段較少, 或許也有一些其它副作用吧。

關於 singleton 更多的弊端, 可參見 Miško Hevery 的文章:
我還需要不少時間配合實例嘗試和思考, 才能明白使用 singleton 或替代方案的 trade-off。

在 java 5.0 開始, 用 enum 實作 singleton 又好寫又好用, 只要這麼寫即可:
public enum MyClass {
    INSTANCE;
    public void someOperation() { .. }
}
enum 的語法可直接做出「singleton」, Making the Most of Java 5.0: Enum Tricks 提供滿不錯的例子介紹使用 enum 的技巧, 像是各別定義各個物件的方法。

至於 java 5.0 前, 實作 singleton 有兩種選擇, 兩者都需要 private constructor, 差別在於取得 singleton 的方式:
  • 用 public static final MyClass INSTANCE = new MyClass()
  • 類似前者, 但改設 INSTANCE 的存取級別為 private, 改用 public static MyClass getInstance() 取得物件
後者的好處是較有彈性, 必要時可放棄 singleton 改為一般用法而不需改所有的 caller, 或是改成「每個 thread 有一個 singleton」。此外, 不用擔心 static method 的成本, 近代 JVM 會 inline static method call。但作者接著說這些好處不太顯眼, 直接用 static member field 較簡單, 語意較明確, 看到 static final 就知道是 singleton。

用 class 實作 singleton 時要另外注意 serialization, 記得寫 readResolve() 避免在 deserialization 時產生第二個 object。所以整體來看, 作者認為使用 enum 並只放一個元素 (INSTANCE) 是比較明智的選擇。

但是, 使用 enum 也會更難 mock。EasyMock 不行, 而 PowerMock 似乎可以。還有, 通常用 enum 時會看作 constant 外加一些輔助函式, 不會有太複雜的 state。但若用 enum 實作 singleton, 很可能會有複雜的初始化, 或需要存取外部資源。這樣測試時就必須 mock enum 了。

2011年6月25日 星期六

Effective Java 讀書筆記: Item 2 - 用 Builder pattern 提供易用的選擇性參數

記錄讀書心得, 內容不一定和書上一致, 有些是我自己的看法。

當生成物件的選擇性參數過多時, 用 Builder pattern 會省事許多, 這篇 《Builder Pattern》 講得很清楚並附有範例碼。關鍵在於:
  • class A 的 builder class B 是 A 裡面的 static class
  • 利用 B 的 constructor 參數指定必要參數
  • 利用 B 的 member method 指定選擇性參數
  • 提供一個 build() 用來生成 A 並傳入之前存下來的參數
  • 若想寫得漂亮點, 可用個
    public interface Builder { public T build(); }
    然後讓 B 實作 Builder
之前找 java argument parser 時, 看到不少 lib 用類似的方式指定 argument 的參數 (像是 description, short name, type 等), 比方說 jopt-simple 最下面的範例。

在一些 mock lib 裡 (如 pymox) 也會看到類似的寫法, 用 method 串接的方式設定過多的選擇性參數。還在揣摩這種寫法的優缺點, 大概等自己實際用上一次後, 才會體悟得較深。

書中有一句關鍵的描述:
The Builder pattern simulates named optional parameters.
讓我想到一個有趣的議題: design patterns 其實是補足語言缺陷的產物。之前有看過一些很有深度的對照文或影片, 忘了記下來。剛才找到的一個例子是, 幾年前讀 Effective C++ 時, 看到一堆管 memory 的準則, 當時不太想學, 覺得有 garbage collection 的話就沒這問題, 自然也不需要發展出這些技巧。如同其它各種技術爭議一般, gc vs. 自己管記憶體? 這議題的標準答案當然是: 看情況。

Effective Java 讀書筆記: Item 1 - static factory method

記錄讀書心得, 內容不一定和書上一致, 有些是我自己的看法。

相對來說, static factory method 對於 constructor 有下列好處:

  • 有名字, 語意較清楚
  • 不一定要生成新物件, 可做到 singleton 或配合 immutable 的特性做 object pool, 或是確保不會生成兩個同樣內容的 immutable 物件, 這樣就能用 == 比較而不用 equals, 效率快很多
  • 有彈性生成 subtype
  • 可避開 constructor 語法限制, 像是可以有多個使用 vararg 的「constructor」

壞處則是:

  • 失去繼承的效果
  • 無法從 java doc 或原始碼裡清楚看出那些 static method 是 factory method

第一點的壞處沒那麼嚴重, 換個角度想, 可以減少濫用繼承的機會 (favor composition over inheritance); 第二點可透過 name convention 降低影響, 像是使用 newInstance (表示生成新物件), getInstance (表示取得物件, 常用於 singleton), valueOf (表示取得和傳入物件「等值」的物件)。

2011年6月24日 星期五

運用 radix sort 的概念加速 sleep sort

偶然從 shakalaca 那看到《排序算法 Sleep Sort》, 剛看完程式碼我的第一印象是: 你在開玩笑嗎? 這在排什麼刁。再仔細看看, 查覺背後神祕的運作原理後, 心中的感覺和文中描述一模一樣: “我擦,真TMD排序了!”。原諒我直接貼上文中的粗話, 當時心中的震撼只能用這樣的字眼才能表達出來。

後來看到留言有人提到這其實是 radix sort 的變型。仔細想想, 確實是這麼一回事!! radix sort 原本是將數字對應到空間的位置, 而 sleep sort 是對到時間上的位置 (或照 sleepnova 的說法, 其實是轉交給 OS 的 task schedule 去排, 不過這樣想就不好玩啦)。所以, 可以套用 radix sort 的概念來加速 sleep sort。

於是憑著愚蠢熱血的餘韻, 用 python + thread 寫了一版程式貼在 github, 有興趣的人可以玩玩看, 排得又「快」又準!! 算時間複雜度不太有意義, 改算秒數比較實在。假設沒有調快執行速度 (即 FASTER_RATE = 1), 且計算時間遠小於 sleep 的時間, 那麼, 若最大允許的正整數是 2**32 - 1, 也就是一個十位數, 我目前的實作方式只需要 90 秒 (比原版快了47721858.83 倍!!)。這樣看來改用二進位會更快, worst case 只要 32 秒 啊!!

2011年6月13日 星期一

socket 超基本心得

最近用 perl、python、java 各寫了 socket 的小程式, 簡記一下心得:
  • 不管是那個語言, 底層都是同樣的實作, 所以用法大同小異, 抓到 socket 的本質, 在換用不同語言時, 自然會知道要怎麼查相關的操作。Python 官網的 socket HOWTO 講得滿清楚的。
  • 為了方便開發, server socket 記得設 SO_REUSEADDR, 以避免 "address already in use" 的錯誤訊息。詳情見: What is the meaning of SO_REUSEADDR (setsockopt option) - Linux?
  • 寫入資料到 socket 時, OS 為了減少 system call, 會有 write buffer。記得查一下自動或手動 flush 的機制, 確保資料有即時送出。這方面 java 最簡單, 不用查也猜得到就是包成 PrintWriter, 用 flush() 即可。雖然 java IO 有點囉唆, 提供一致抽象介面也是有好處啦。
  • 接受端要知道如何收到完整的資料。有各種方式可用: 像是先傳 byte 數, 總是傳固定數量 bytes 過去等 (不夠補 0)。我選擇用 '\n' 做為結束字元, 並將傳輸資料中的 '\n' 先換成別的字元 (如 '\u0001') 再傳過去。好處是可以輸出到 console 或 log 檔, 每次訊息都占一行, 方便除錯。
  • serialization 的選擇需另開文章討論細項。整體來說, 轉成 JSON 再輸出是滿好的選擇。

2011年6月9日 星期四

python 的 scope

python 和其它語言有一個不太一致的地方偶而讓我有點困擾: 只有 module、class、function 才有建立新的 scope。換句話說, if、while、for 沒有建立新的 scope。第一次知道時覺得有點驚呀, 像下列的程式可以正常運作:

if True:
    a = 3
else:
    a = 5
print a   # output: 3

這例子較無傷大雅, 但今天遇到另一個不好的例子:

def hello():
    print 'Hello, %s' % name

if __name__ == '__main__':
    name = 'John'
    hello()  # output: Hello, John

換句話說, 原本語意上將 main block 裡的變數看成是 local, 但它實際上是 global, 會造成隱晦的 bug。像是這份 script 的 hello 可正常執行, 但別的 module import 它後再執行 hello(), 就會造成錯誤, 因為找不到 global 變數 name。只能盡量減少 main block 裡的程式, 降低它的影響了。

virtualbox port forwarding 太慢的原因和解法

這標題其實不太正確, 這是一連串的巧合造成的誤會。我的配置如下:

  • Windows 7 當 host OS
  • Ubuntu 當 guest OS
  • 網路模式用 NAT mode
  • 有設 port forwarding, 像是 host 的 10022 會導向 guest 的 22; 18000 會導向 guest 的 8000。

所以, 我可以在 Windows7 用 putty 連向 localhost 10022, 開始寫程式, 要跑 web dev server 時, 就跑在 port 8000。於是可在 Windows 7 裡打開瀏覽器, 連向 localhost:18000, 連上 Ubuntu 裡的 web dev server

但詭異的是, 連 ssh 和 apache2 都沒問題, 連向 web dev server 時卻會很慢。另外試了 python SimpleHTTPServer 也很慢。

卡了好幾天後, 聽同事 P 的建議, 用 tcpdump 在 guest OS 裡看封包狀況, 發現它會五秒傳一批, 等五秒再傳下一批。讀一次網頁包含 css、js 等, 一次會下載多個檔案, web dev server 則是十秒回傳一個, 相當有規律。

看到這種規律的延遲情況, 讓我想到可能原因是 domain name 反查 time out, 之前在連 ssh連 mysql 時都發生過。

但是這回我有在 guest 的 /etc/hosts 設自己的 IP 反查, 不明白原因在那。最後亂試發現, 在 /etc/hosts 裡設 gateway 的 IP 反查就解決了 (用 route 查 gateway IP; 名稱可以隨便設, 反正都是區網 IP)。再研究一陣子才發覺, 連向 host 透過 port forwarding 傳向 guest 時, 來源 IP 會變成 guest 的 gateway。而上述兩個會延遲的 web server, 都會顯示來源連線的 domain name, 查不到時才會改顯示 IP。因此固定延遲五秒

附帶一提, 這次我又犯之前的錯, 改了 /etc/hosts 後用 host 和 nslookup 測, 結果一直沒反應。看到之前的心得才發覺它們沒有呼叫 gethostbyaddr()。用 ltrace 跑 dev server 有看到 gethostbyaddr 的字, 但是是出現在 memcpy 的參數裡, 不知實際情況怎麼運作的。之後有機會再來連研究上述兩者 web dev server 的原始碼。

2011年6月6日 星期一

用 wireshark 和 tcpview 找出 Windows 的連線情況

看過不少人推過 wireshark, 剛才看到 DK 提到, 就裝來試試。

這篇有圖文並茂的詳細教學, 了解怎麼用 wireshark 過濾出本機連線的封包。練習的時候, 滿容易地找到自己的 BBS 密碼 (oops ...), 還有找到神祕的 UDP 封包群。後來 Tib 建議說可用 netstat 或 tcpview 查看。還挺好用的, 一看就發現, 原來是 ppstream 啊 ...。

不過原本要解的問題仍沒進展, 我發現在使用 port forwarding 時, apache2 和 sshd 速度都很正常, 但跑 python dev server (比方用 SimpleHTTPServer), 卻會異常的慢。而從 VM 內部自己連 dev server 沒有問題。VirtualBox 將網路封包「藏」起來了, 不知道要怎麼查特定程式 port forwarding 緩慢的原因。只好放棄用 dev server, 改用 apache2 直接當 dev server 試看看。

2011年6月3日 星期五

關於 memory 的讀書心得 #1

小記一下前陣子讀 What every programmer should know about memory 的心得。範圍為 1.1 ~ 2.1.4。我這方面相當弱, 有錯還請指正。

  • 用 DRAM 不用 SRAM 主因是造價, SRAM 要較多電晶體。文中的例子是 6 vs. 1 + 電容*1, 有更少電晶體的 SRAM, 但速度會變慢。
  • 但 DRAM 需要充電或放電來維持狀態, 因此需要較長的讀寫時間, 不如 SRAM 可以立即讀寫。
  • 不論 SRAM / DRAM, 記憶體愈大, 需要愈多的 address line, 4G 需要 32 條, 但不會有人用一個 (de)multiplexer 連接全部 cell, 那需要 2^32 輸出的線。
  • 替代方案是用 row address selection (RAS) + columns address selection (CAS) 分別表示上下 16 bit 的位置, 可大幅節省成本。
  • 更進一步, 用一組 16 條的 address line 配合另一個訊號表示這次是 RAS 或 CAS, 可再省一半的線路。
  • SRAM 多用在極需速度的地方, 像是 router, CPU cache, 視實作方式速度快慢不等, 最快可以只慢 CPU 一兩個數量級。

網友補充的內容如下:

  • (by vegafish) DRAM 需要充電的原因是由於電容在讀取data的時候會自然漏電,所以讀取的時候會同時接VDD讓還沒漏光的電容充滿,至於定期充滿的做法就是全部讀取一次。

Ubuntu 移除 apache2 的方法

開啟很久沒用的 VM, 不知為啥 apache2 的 modules 都不見了, 無法正常運作 (能正常運作才有鬼哩), 用 aptitude remove 再重裝也無效, 摸索一陣子才找到解法:

  1. 先用 dpkg -l | grep apache2 找出相關套件
  2. sudo aptitude purge apache2 apache2-mpm-worker apache2-utils apache2.2-common libapache2-mod-php5 libapache2-mod-wsgi # 這裡接上個指令找到相關的套件

javascript 版的 ctags

最近比較常 trace javascript codes, 想要像平時一樣, 在vim 裡按個 ctrl+[ 就跳到變數或函式的定義。但原本的 ctags 效果很差。看到這篇提到要改用 DoctorJS

安裝方式

DoctorJS 是透過 node.js 執行。node.js 的 configure 寫得挺好的, 執行後會說缺什麼, 提示很清楚。在 Ubuntu 10.04 的安裝步驟如下:

安裝 node.js

  1. wget http://nodejs.org/dist/node-v0.4.8.tar.gz
  2. tar zxvf node-v0.4.8.tar.gz
  3. cd node-v0.4.8/
  4. sudo aptitude install g++ # [1]
  5. sudo aptitude install libssl-dev # [2]
  6. sudo aptitude install curl # [3]
  7. sudo ./configure
  8. sudo make test
  9. sudo make install

備註

  • [1] configure 回報沒有 g++
  • [2] configure 回報找不到 openssl header。Ubuntu 9.10 後有內建 OpenSSL, 但沒照 Ubuntu 的預設安裝模式, 不會包含各種開發用檔案, 所以要另裝 dev 的 package。
  • [3] make test 時說少了這個, 滿好用的小工具, 就順手裝了。

安裝 DoctorJS

  1. git clone git:github.com/mozilla/doctorjs.git
  2. sudo make install

用法

就和 ctags 一樣, 只是指令改為 jsctags。試了目前開發的 js, 效果還不錯。

附帶一提, 這篇文章是用 ego-post 寫的, 試用感覺還不壞。試用中發現不少可以改進的小地方。當自己就是開發產品的愛用者時, 點子果然會源源不絕啊!

在 Fedora 下裝 id-utils

Fedora 似乎因為執行檔撞名,而沒有提供 id-utils 的套件 ,但這是使用 gj 的必要套件,只好自己編。從官網抓好 tarball ,解開來編譯 (./configure && make)就是了。 但編譯後會遇到錯誤: ./stdio.h:10...