2008年5月4日

當 C++ 的不變性遇上懶人法

聊聊我最近碰到的一個問題:想用懶人法(lazy initialization)提升 C++ 程式的效率,郤碰上不變性(constness)的阻礙,和解決的方法。

寫 C++ class 的時候,常常會寫一些 getter 和 setter 來讀寫物件的屬性,比方說 Person 這個物件有年齡(age)屬性,就可以寫個 getAge() 和 setAge() 來讀取和改變它的值。典型的寫法大約是這樣:

class Person {
Person(int persion_id, PersonDatabase & pdb); // 從資料庫裡抓個人資料進來
...
int getAge(void) const { return age_; } // 傳回 age 資料
void setAge(int age) { age_ = age; } // 改變 age 資料
...
};

Person::Person(int person_id, PersonDatabase & pdb)
{
// 把所有屬性從資料庫讀回來填好
}
這是常見的設計:在 constructor 把所有的屬性填好,並提供 getter 和 setter 函式供其他物件讀寫。

在 getAge() 的宣告加上了 const 表示這個 member function 不會改變 Person 物件的屬性。一開始就把不變性說清楚是比較好的設計,這樣子任何程式都可以呼叫 alice.getAge() 來讀出 alice 的年齡,不論 alice 這個 Person 物件是不是 const 的。

想像政府某單位有個程式要把全國納稅人資料載入,然後對年齡、繳稅金額、教育程度的數據做統計分析。依以上 Person class 的設計,那大概是這樣:
vector<Person> people;
PersonDatabase pdb;
while (pdb.next()) {
people.push_back(Person(pdb.getId(), pdb));
}
這樣做程式很簡單,但有兩個問題:
  • 這樣會在記憶體中建立一千多萬個 Person 物件,每個物件如果需要 100 bytes,那就至少需要 1GB 的記憶體。用現代的個人電腦來看不算多,但如果要處理的國家不是台灣而是日本或美國,那就大多了。

  • 另一個問題是把 100 個 bytes 讀進來,依身分證號碼、年齡、姓、名、地址、繳稅金額、教育程度等等屬性分門別類存在每個 Person 物件的肚子裡,也需要時間。既然我們只要用年齡、繳稅金額、教育程度三項數據做統計,花那美國時間去多讀一堆用不到的屬性、還浪費那美國空間去把這些屬性分門別類存好... 好像蠻白痴的。

現代的資料庫很會做最佳化,用一個 SQL query 就可以把所有需要的屬性抓回來,但 C++ 這邊還是要把抓回來的字串拆開、轉型、再儲存,屬性越多,花的時間仍然越多。

所以這個最簡單的設計不 scalable,在物件內含資料較多或有巨量的同種物件要載入記憶體時會浪費記憶體,也變得很慢。

為了空間和時間的效率,一個普遍的技巧是懶人法: lazy initialization,也有人說 on-demand initialization,做法就是在建立 Person 物件時懶惰一下,不去把所有資料讀進來,等 getter 被呼叫的時候,如果沒有資料,再去讀進來存著和回傳,下次同一個 getter 再被呼叫時就可以直接回傳。這個做法需要多一點程式碼,每個 getter 也會要多花一丁點時間檢查有沒有資料,但可能省下不少空間和總時間。(但如果讀資料庫很慢很慢,可能就不適合這樣做。)

程式大概寫成這樣:
Person::Person(int person_id, PersonDatabase & pdb)
{
// 把所有要從資料庫讀的屬性設成「不詳」
age_ = -100;
...
// 記住資料庫在哪裡,以後可以用
pdb_ = pdb;
}

Person::loadInt_(char * name)
{
// 從 pdb_ 載入指定的屬性,轉成 int 後回傳
}

int Person::getAge(void) const
{
if (age_ < 0) age_ = this->loadInt_("age"); // loadInt_() 會去讀 PersonDatabase 回傳 int
return age_;
}
這樣太棒了!一個設計可以省時間又能省空間。一切都很美好...

碰!
person.cc: In member function `int Person::getAge() const':
person.cc:77: error: passing `const Person' as `this' argument of `int
Person::loadInt_()' discards qualifiers
make: *** [person.o] Error 1
Compile 失敗了!為什麼?

因為在 getAge() 裡呼叫 loadInt_() 破壞了不變性。

getAge() 明明昭告天下是不會修改 Person 物件的,但為了用懶人法,又不得不在沒值時叫 loadInt_() 來把年齡抓回來交差,換句話說,getAge() 會修改 Person 的 age_ 屬性。

Compiler 不准你做這種事。怎麼辦?

這時在觀念上要把介面實作分開。宣告是介面,實作要在符合宣告的精神下達成任務。

getAge() 的宣告可以解釋成:
致所有呼叫 getAge() 的程式:我謹以至誠,不會改變 Person 物件的內容,alice 是 19 歲,我就會回傳 19,而且不會改動任何 alice 的屬性。
照這個宣告的精神,雖然 getAge() 要把年齡屬性載進來,把 alice 的年齡從不詳變成 19 才回傳,但這個行為沒有違反上面的宣告,回傳「不詳」才是違反 getAge() 自己的諾言。

所以程式要這樣寫:
int Person::getAge(void) const
{
if (age_ < 0) age_ = const_cast<Person *>(this)->loadInt_("age"); // 把 this 指標轉成 non-const
return age_;
}
先用 const_cast 把 Person 物件 this 從 const Person * 轉成非 const 的 Person *,就可以呼叫 loadInt_() 了。

要違反自己在語法上的宣告,才能符合宣告的精神,這真是 C++ 的黑暗面啊~~~

2008/6/11 後記:謝謝 fr3@k 的指教,在這種情形用 mutable 關鍵字宣告 age_ 就可以在 const 的 member function 中改動 age_ 了。

網路上有不少文章講 mutable vs. const_cast,我看了幾篇,都是一面倒不建議使用 const_cast,其中一個論點和 compiler 最佳化有關。最佳化是個很大的議題,我不太懂,但如果 const_cast 的使用造成 compiler 不知道這個 const member function 會改到 age_ 而把它最佳化成直接回傳某個 register 中的值,問題就大了。(喂!寫程式寫到要顧慮 compiler 的 bug,會不會太辛苦了點?)

不過我實在不喜歡在 header 檔中宣告 mutable int age_,因為 age_ 是不是 mutable 是實作的細節,不是介面,如果換一個實作也許就不需要用 mutable,實在不想在 header 檔裡寫 mutable。看來要用 pImpl pattern 了... 但是用 pImpl 還是躲不掉 mutable... Orz
class Person {
...
struct Impl;
mutable Impl * pImpl_;
};