What have you found for these years?

2008-01-03

object pool reloaded

不知道為什麼,對這個題目有點著迷,之前就曾經對此下過不少功夫,
所以親手打造了一個有點怪模怪樣的 object pool. 也確實用到之前的
專案上了。不過在自鳴得意完畢,想說看看 boost 有沒有提供 object pool 後,
整個情況好像就有點不同了。

是的,想當然爾,在大量使用小型物件,大量產生又大量摧毀的世界下,
這種東西早就有人做了。
Boost Pool Library
http://www.boost.org/libs/pool/doc/index.html

這種時候當然要來 benchmark 一下啦!
如果連得上的話,可以參考我電腦上的一點記錄:
http://phpbb.godfat.org/viewtopic.php?t=722

這一篇寫得非常不完整,因為前後我測試過非常多東西,最後結果又不太理想,
就沒什麼力氣寫記錄了。簡單地說,只有在一種狀況下,當時所寫的 object pool 的
效能才能遠遠超過 boost object pool. 是的,是遠遠超過,因為 boost object pool
在那種狀況下跑得慢到比 new + delete 還要慢,還慢很多。

但其實那根本不重要,因為我那個 test case 在正常情況下根本就不會發生...
所以我最後的結論是,就用 boost object pool 就好了。正常情況下,他的效能很棒。

anyway, 其實還是能聊聊之前的 object pool 是怎麼做的。用上比較重要的工具是:
1. loki/AbstractFactory.h
2. boost/ptr_container/ptr_vector.hpp

等會再來說為什麼有 factory. 先簡單地說概念,就是在 object pool 裡面預先產生出
大量的 object, 用 new T[] 來做。當量不足時,再一次產生更大量的 new T[],
以此降低使用 new 的狀況。這邊,用 std::vector 去 store 這些 pointer, 然後用
ptr_vector 去 view 這些 pointer, 藉由 boost::view_clone_allocator, 一個特殊的
allocator, 拿來單純去 view 其他東西。這樣做的原因是,取得一個扁平的 pointer
array, 往後需要做 search 時會比較好做。

接著就能看到我覺得最大的一個問題點了。就是要利用此 object pool, 必須改變平時
對於 object 的習慣:constructor 建造,destructor 摧毀。
要改用 do_init 建造,do_suicide 摧毀,然後必須去繼承 PooledObject 才行。
理由是我沒使用 placement new! 為什麼不用?抱歉我忘了 XD

總而言之,我在 PooledObject 中插入一個 dead_ flag 去標示這個 object
是活的死的,然後在 init 中將 dead_ = false; 接著呼叫 client 的 do_init,
vice versa, 在 suicide 中將 dead_ = true; 接著呼叫 client 的 do_suicide.

在 object pool 中,則根據這個 flag 去判斷下一次該去復活哪一個 object.
這個作法真的是很爛,不過至少當時玩得很開心(?)
有時候為了完成一個想法,好不好用值不值得能不能用都變其次了 @_@b
那一次,template 也是玩得非常兇,像是這個:
    T* got_it(){
        return &top_++->PooledObject::template init<T>();
    }

接下來就是 factory 一回事了。其實用這個 factory 幾乎可以說是毫無意義,
因為我根本就沒有那麼大的物件結構,根本就沒有必要抽換一整族的物件。
算了,反正就是玩玩,熟悉熟悉,趣味趣味...
畢竟 loki 的東西確實是有很神奇的迷人氣息...

可惜這部份倒是沒什麼好說的 XD
就只是在 factory unit 中插入 object pool, 然後由 object pool 去
DoCreate object 而已,我自己是沒寫什麼神奇的東西。最後 factory 再搭配
singleton holder, that's all.

要說神奇的東西,應該是更早以前寫的 block map 才對...(遠目)
那東西才是 template 玩到走火入魔了,verbose 到了一種恐怖的境界。
數不盡的 typedef, 然後怨恨沒有 template alias, 很多東西變成要 wrapper,
現在回想起來,那種作法好像反而變得有點 java 味了?anyway, that's not the point.

總之,最後的用法大概像這樣:

SF::Instance().Create<Dying>()->init(this);

SF 是 singleton holder of factory. 至於為什麼後面還有 init?
因為原本的 init 沒有參數啊,要傳參數只好拉出來了。其實這還算是著名的:
The Forwarding Problem: Arguments
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2002/n1385.htm

這個在這次的實作中一併解決這個問題了,後面再提吧。

噢對了,倒是想起來一件事。後來我還有再擴充這個愚蠢的 object pool,
只是沒用上專案裡,所以差點忘記了。簡單地說,我在 object pool 的輸出上
再多 wrap 了一層 smart pointer, 測試了 loki 的 SmartPtr 和 boost 的 shared_ptr,
(或說今天的 tr1::shared_ptr)這是為了證明擴充性所以做的。benchmark 的結果是
效能大概會慢三倍左右(沒記錯的話)。

大概就是讓 deleter 作成呼叫 suicide, 而不是 delete 這樣。事實證明,shared_ptr
在做這件事上比 loki 的 SmartPtr 容易多了。我記得當初曾經碰到怪問題,trace 很久
loki 的 source code 才找到問題。應該這樣說,shared_ptr 對初學者來講真的很親切,
然而 SmartPtr 的組裝與擴充能力還是強大太多了。不過仍要注意的是,也不穩定太多了
(bug...)之前用他導致我程式有不明原因當掉,換 shared_ptr 則完全沒事,讓我對他
失去不少信心。但也難怪 tr1 不考慮這種東西,shared_ptr 可是有長久歷練的。
(那可是 boost 最早的幾樣產物之一呢,從 1998 年就開始發展的(though 1994
有類似的東西,最後沒被加入標準))

程式碼(不含 gc (smart pointer) 部份)可以看這裡:(如果他還活著的話)
http://shooting-cubes.googlecode.com/svn/trunk/include/Factory.hpp

blah, 前言太長了。也罷,算個回顧。
這次的 object pool 精簡得多,但還沒真正用上,到底堪不堪用,其實也難講。
但至少我看來看去是比上次那個滿意得多,希望不會有什麼問題囉。
這次的幾個重要考量如下:

1. 不要用華而不實的東西,如 loki... 就如同 design pattern 一樣,
需求是要等他浮現的,而不是去假設我們「可能」會需要什麼東西。
這次只用上了 singleton holder.

2. shared_ptr 是個好東西,一開始能用上的話就用吧。沒有 gc 不是不行,
但沒有 gc 總是會讓事情變得更複雜。要把事情變複雜容易,反之不亦然。
再者,tr1 應該多加利用,他不是 boost, 更不是 loki.

3. 不要再自己做 object pool 演算法了,比不過人家的... 不過當時要是知道
boost 有做的話,大概也不會做吧。但學個經驗也沒什麼不好倒是真的。

4. 雖然說要直接用 boost 的 object pool, 但是包裝一下仍然是必然的。
至少,要裝上 gc 就需要包裝了。更何況,object pool 恐怕必然值得成為
singleton ?

boost object pool 還有個很大的優點,我測試過,一次把所有的 object
drop 掉的效能是非常棒的。像是這樣:
boost::object_pool<T> pool;
pool.construct(); pool.construct(); pool.construct();
接著等 pool 掛掉,那三個 object 自然會被刪除,也會喚起 destructor.
這樣的效能,遠遠大於一個個呼叫 pool.destroy(t);

那麼 pool 要怎麼成為 singleton 又能被 drop? loki 的 singleton holder
就派上用場了。包裝一下,destroy_all 就把 singleton delete 掉。而我
不用在乎 singleton 是否還活著,呼叫 instance 就對了,不存在的話,
singleton holder 會幫我 new 出來。當然,程式結束也會自動 delete 掉。

不過這邊就碰上一個問題了,我有點困擾。因為如果我呼叫了 destroy_all 的話,
表示之前的 pointer 都會失效了,而我的 shared_ptr 不知道這件事,
如果他再喚起那 custom 的 deleter, 進而呼叫 pool.destroy(p); 這樣就爆炸了!
也就是說,其實這兩個組件似乎不應該搭在一起,或是,我就需要進行一些 hook,
不管是 hook 在 deleter 或是 object pool 上,總之需要。

但是我擔心這樣對效能衝擊太大,所以試著在 deleter 上加上一行判斷:
        void operator()(argument_type p){
            if(ObjectPool<T>::is_from(p))
                ObjectPool<T>::destroy(p);
        }

如果已經被刪除過了,is_from 應該會回傳 false 吧?然而 boost 手冊上卻這麼說:
Returns true if p was allocated from u or may be returned as the result of
a future allocation from u. Returns false if p was allocated from some other
pool or may be returned as the result of a future allocation from some other
pool. Otherwise, the return value is meaningless; note that this function
may not be used to reliably test random pointer values.

我就不是很確定這樣做到底對不對了。總之,再看看吧。如果有問題,那就看看是要
把 destroy_all 拿掉,還是乾脆把 shared_ptr 拿掉。反正都很容易。專案上的物件
刪除時機其實也不難掌控!如果效能有瓶頸,這邊應該非常值得注意。

於是,我們的 client code 可以長這樣:

class Test{
public:
typedef tr1::shared_ptr<Test> pointer_type;
static pointer_type create(int i){
return psc::ObjectPool<Test>::create(i);
}
Test(int i){init(i*2);}
Test(){cout << "c'tor" << endl;}
~Test(){cout << "d'tor: " << i_ << endl;}
Test& go(){ cout << "go" << endl; return *this; }

private:
void init(int i){
i_ = i;
cout << "init: " << i_ << endl;
// return shared_from_this();
}
int i_;
};

typedef Test::pointer_type pTest;

定義 pointer_type 表示要用這個 smart pointer, 這個也許可以做自動化,
或是乾脆一點,寫死在 object pool 也無妨。反正說過了,tr1::shared_ptr 是首選。
定義 create 去 wrap object pool 的 create? 這是為了通用介面,就算有些 object
沒有用 object pool, 我們仍然能使用同樣的介面。像是 Map::create 其實就不需要
object pool, Map 並不會大量產生也不會大量摧毀,讓 Map::create 單純 new 即可。

註解掉的 return shared_from_this(); 是個我還不太懂的東西,基本上,大致上
就是要 return pointer_type(this); 的意思。不過這樣做卻會當掉,所以才有
shared_from_this 這東西的存在。但總覺得這個好像很容易產生大量的 copy,
所以暫時還是 comment 掉不用。發現需要用的時候,再把他掛回去也容易得很。

最後一個 pTest 則是懶人用的 Test::pointer_type.

client 的 client 則會這樣寫:
int main(){
pTest t1 = Test::create(1);
cout << 'a' << endl;
{
pTest t2 = Test::create(2);
cout << 'b' << endl;
}
pTest t3 = Test::create(3);
t3->go().go().go();
psc::ObjectPool<Test>::destroy_all();
cout << 'c' << endl;
}

執行結果就會是:
init: 2
a
init: 4
b
d'tor: 4
init: 6
go
go
go
d'tor: 2
d'tor: 6
c

詳細程式碼可以看這裡:(如果他還活著的話)
http://shooting-cubes.googlecode.com/svn/test/pool.cpp

至於 Test(){cout << "c'tor" << endl;} 寫來幹嘛的?為什麼要多個 init?
這就要回到 the forwarding problem 了。基本上,這個問題要描述的是,
在現行標準中,我們難以做到漂亮的 delegator.

在 Ruby 中,it's as simple as ... [insert your word here]
class Delegate
  undef_method *instance_methods.select{|i| not i =~ /^__/ }
  def method_missing msg, *args, &block
    @target.send :msg, *args, &block
  end
end
end

噢,這還是個萬能 delegator, 什麼 method 都能 delegate, 用這個來做 proxy
再容易不過了。第一行先解除所有可以解除的 method, 接著把所有不存在的
method 通通丟給 target 去解決。收工。

可惜 C++ 當然不能這樣幹。the forwarding problem 就是在指這件事的困難。
(http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2002/n1385.htm)
這個困難點在於三個要求難以同時達成:
1. 原本合法的呼叫,必須保持合法
2. 原本不合法的呼叫,也必須保持不合法
3. 完成這件事,不能有非常恐怖的 work 要做

現在的問題在於,C++ 有 const correctness, 這是很嚴格的限制。
假使你的 forwarding function 是 reference 而不是 const reference,
則原本該是 const 的你可以傳 non-const 進去。反之亦然。那提供兩者呢?
有個 reference 版也有 const reference 版?這樣就無法達成第三點要求,
因為當參數一多時,就會有爆炸性的排列組合出現。
e.g.,
1. T1 const&, T2 const&, T3 const&
2. T1 &, T2 const&, T3 const&
3. T1 &, T2 &, T3 const&
4. T1 &, T2 &, T3 &
5. T1 const&, T2 &, T3 const&
....
再考慮 volatile 吧!會多到爆炸。

第四個解法我就不說了,反正都是有問題的,而且問題更大。最後面,
則有一些未來可能的解法,都是需要修改語言規則的。最好的解法則是
Rvalue reference + modified argument deduction, 被標為 "perfect".
細節我不多說了,其實我也有點忘了。總之這都算是滿深入 C++ 的語言規則了。
(其實這也顯示了 static typing 語言的大麻煩:許多難以搞定的重複)

另外,C++09 的 variadic templates 也許也該拿出來討論?
不過暫時不管他,因為其實我認為最簡單的解法還是回歸原始:
meta-programming 就結了。問題 3 是希望避免多餘的工作,
避免多餘的工作當然是因為人力是寶貴的。但我們又怎麼能忘記自動化、
批次處理、寫程式又是為何?不正是要解決這些問題?
(btw, template meta-programming 其實並不是要解決 preprocess 的問題,
所以這裡不提 template meta-programming, 包含 lambda, mpl 等東西。)

所以 boost 有個 preprocessor, wave, object pool 自己也用上了 m4,
loki 也有一堆應該要用程式 generate 出來的東西,code generator 也早就是
一直在使用的東西,只是面向可能各自不同罷了。

其實上面提到的東西,我都沒用過 XD 所以也不知道他們用起來感覺如何?
wave 看起來非常精妙,內部似乎是用 spirit 寫的,弄得好複雜,上次想試
卻看不太懂。c/c++ 內建的 preprocessor 我又受夠了,除了難用還是難用。
m4 搞不太懂是什麼。我只知道一件事:工具太多了,還是用自己習慣的好。

所以當然就是選用 ruby 了!藉由 erb, 可以做像 php 一樣的 template,
藉由 rake, 可以把各種 preprocessing 自動化。c++ 確實是有非常多的不足,
template 非常強大,但想深入用下去時,卻會發現很多地方很殘缺。
其實這也不能怪他,畢竟 template 本來就不是設計來搞這些瘋狂的東西,
要用得這麼瘋狂,自然容易碰到很多設計上的問題,這也只能等語言的演化了。
或是 meta-programming... 嘿嘿嘿,把問題拉高一個層次,很多問題就不是問題了。

不過在看 erb 之前,先來看看 pool 裡的 m4.
想當然爾,這東西就用在 pool.construct() 這邊,這邊有個 forwarding,
construct 可以看成 client 的 constructor, 這是跑不掉的。如果只允許
沒有參數的 construct, 而要求 client 要在事後再呼叫 init or its friends,
這樣實在太難看了。硬要把 c'tor 拆成兩半,實在很麻煩。

所以 boost object pool 的作法是這樣:
// Include automatically-generated file for family of template construct()
// functions
#ifndef BOOST_NO_TEMPLATE_CV_REF_OVERLOADS
# include <boost/pool/detail/pool_construct.inc>
#else
# include <boost/pool/detail/pool_construct_simple.inc>
#endif

不要管那 BOOST_NO_TEMPLATE_CV_REF_OVERLOADS 是什麼,
沒有這功能的 compiler 叫他吃屎。simple 版裡面只有 const& 的參數,無聊,
那就只是那篇 paper 中的第二個解罷了。至於 pool_construct.inc 裡面,
則是那爆炸性的排列組合 methods.

開頭有個註解是這樣:
// This file was AUTOMATICALLY GENERATED from "pool_c~1.m4"

現在的問題是,我的 Test::create 需要 forward arguments 給 pool.construct,
所以我想利用他這段程式。不過我不知道這個檔在哪?而且我也不知道 m4 要怎麼用,
也懶得去試。是時候拿出萬能的 ruby 了!

最後我的 c++ 程式長這樣:
<% for_template_parameters_upto(3){ |args_list| %>
    template <%= template_parameters args_list %>
    static element_type create(<%= forward_parameters args_list %>){
        return element_type(SPool::Instance().construct(
            <%= arguments args_list %>), Deleter());
    }
<% } %>

erb 跑完之後,會產生四百多行的 code 在那邊,長得像這樣:
...
    template <class T0>
    static element_type create(T0 volatile& a){
        return element_type(SPool::Instance().construct(a), Deleter());
    }

    template <class T0>
    static element_type create(T0 const volatile& a){
        return element_type(SPool::Instance().construct(a), Deleter());
    }

    template <class T0, class T1>
    static element_type create(T0 & a, T1 & b){
return element_type(SPool::Instance().construct(a, b), Deleter());
    }

    template <class T0, class T1>
    static element_type create(T0 & a, T1 const& b){
        return element_type(SPool::Instance().construct(a, b), Deleter());
    }
...

其他目前寫好的 preprocessing tool, 還有 attr_builder 和 header guard.
attr_builder 就像這樣:
class MapSetting{<%# @prefix = ' '*4 %>
<%= accessor :int, :frequency, :decay, :delay, :color_amounts,
:chain_amounts, :starting_line, :cube_size %>
<%= accessor :double, :speed, :damage_factor %>
<%= reader :int, :width, :height, :size %>
<%= accessor :bool, :dropping_creatable %>

accessor 會產生 getter, setter, property.
reader 會產生 getter, property.
為什麼 width, height, size 是 reader? 因為 size 取決於 width 和 height,
所以 size 沒有 setter, 而 width 和 height 的 setter 要自己寫:
    MapSetting& width(int const& new_width){
        width_ = new_width;
        return reset_size();
    }
    MapSetting& height(int const& new_height){
        height_ = new_height;
        return reset_size();
    }

產生結果像這樣:
public:
    double speed() const{ return speed_; }
    double damage_factor() const{ return damage_factor_; }
public:
    MapSetting& speed(double const& new_speed){
        speed_ = new_speed; return *this;
    }
    MapSetting& damage_factor(double const& new_damage_factor){
        damage_factor_ = new_damage_factor; return *this;
    }
private:
    double speed_, damage_factor_;

header guard 則是依照檔名和目錄產生相對應的 header guard,
省得老要自己手打,每次習慣又會改一次,不整齊難看,排整齊又麻煩...。
大概就很簡單地長這樣:
#ifndef _SHOOTING_CUBES_DATA_MAPSETTING_
#define _SHOOTING_CUBES_DATA_MAPSETTING_

$ rake preprocess # 這樣可以跑所有的 preprocessing
$ rake build # 這樣會先跑 preprocessing, 然後 cmake ., 接著 make.
$ rake clean # 清掉 *.o 和 preprocessing 後的結果
$ rake clobber # 全清乾淨,包含 cmake 的 cache, 全部還原
$ rake rebuild # 等同於 clobber + build

Rakefile 在這:
http://shooting-cubes.googlecode.com/svn/trunk/Rakefile

attr_builder:
http://shooting-cubes.googlecode.com/svn/trunk/lib/attr_builder.rb

header_guard:
http://shooting-cubes.googlecode.com/svn/trunk/lib/header_guard.rb

template_forward_parameters:
http://shooting-cubes.googlecode.com/svn/trunk/lib/template_forward_parameters.rb

ObjectPool 的 erb template:
http://shooting-cubes.googlecode.com/svn/trunk/include/utils/ObjectPool.hpp.erb

整個專案可以看:
http://shooting-cubes.googlecode.com
License: Apache License 2.0
目前一些 license related 的檔案都還沒放上去,
不過基本上就是借來的程式都用他們原本的 license,
我們寫的則都是 Apache License 2.0.
我是不清楚這樣會不會有什麼問題... 但總之就是尊重所有的 license,
盡量以不改動為原則,其他就請隨意。有什麼錯的話也望請告知,感激不盡。

感謝另一位程式團員,基本上大部份的程式都是出自他手,我只是不知道在寫什麼...

靠,這篇寫四個多小時,天亮了,快趴了...

btw, 以上 ruby 的東西有空會加到 gem ludy 中。不過其中比較複雜的大概只有
template_forward_parameters, 用到 facets 的 combos, 很好用。
ruby 程式寫起來其實蠻 interactive 的,所以趣味特別多。不過程式串太長
會蠻難懂的,感覺有點像是不斷演化,演化到複雜度難以捉摸。但只要把
他當成 functional 的形式寫,把之前的東西全部當黑箱,沒有 side-effect,
step by step 的話,其實也沒有那麼難,就是嚇人了點 :D

0 retries:

Post a Comment

All texts are licensed under CC Attribution 3.0