google ime (mozc)のソースコードが公開されたので読んでみた。
google ime (mozc)のソースコードが公開されました。
http://code.google.com/p/mozc/
http://codezine.jp/article/detail/5174
http://googlejapan.blogspot.com/2010/05/google_10.html
なんで、早速ソースコードを探検してみた。
google のスーパーハカーはどういう楽しいコードを書いているのか興味津々です。
#まだすべてのソースコードに目を通していないです。
1.CallOnce という CASで実装された楽しい関数
base/mutex.cc に、 CallOnce という 大変ユニークな関数があります。
void CallOnce(once_t *once, void (*func)()) { if (once == NULL || func == NULL) { return; } if (once->state != ONCE_INIT) { return; } // change the counter in atomic if (0 == InterlockedCompareExchange(&(once->counter), 1, 0)) { // call func (*func)(); // change the status to be ONCE_DONE in atomic // Maybe we won't use it, but in order to make memory barrier, // we use InterlockedCompareExchange just in case. InterlockedCompareExchange(&(once->state), ONCE_DONE, ONCE_INIT); } else { while (once->state == ONCE_INIT) { #ifdef OS_WINDOWS YieldProcessor(); #endif } // busy loop } }
'
第2引数が 関数へのポインタになっているのがミソです。
これを利用すると、 超高速singleton が実装できるようです。
base/singleton.h
template <typename T> class Singleton { public: static T *get() { CallOnce(&once_, &Singleton<T>::Init); //←注目 return instance_; } private: static void Init() { instance_ = new T; SingletonFinalizer::AddFinalizer(&Singleton<T>::Delete); } static void Delete() { delete instance_; instance_ = NULL; ResetOnce(&once_); } static once_t once_; static T *instance_; };
これだけで、singletonの完成ですね。
CallOnce(&once_, &Singleton
CASで排他しているので、処理速度も格別なはずです。
そもそも、関数のポインタ(この場合 staticメソッド)を渡せるように作られているところが haskell のような関数型言語ぽくてかっこいいですね。
しびれました。
windows IPC の実装
windows IPC の実装を win32_ipc.cc を見てみます。
ipc/win32_ipc.cc
void IPCClient::Init(const string &name, const string &server_path) { last_ipc_error_ = IPC_NO_CONNECTION; IPCPathManager *manager = IPCPathManager::GetIPCPathManager(name); if (manager == NULL) { LOG(ERROR) << "IPCPathManager::GetIPCPathManager failed"; return; } ipc_path_manager_ = manager; // TODO(taku): enable them on Mac/Linux #ifdef _DEBUG const size_t kMaxTrial = 256; #else const size_t kMaxTrial = 2; #endif for (size_t trial = 0; trial < kMaxTrial; ++trial) { string server_address; if (!manager->GetPathName(&server_address)) { continue; } wstring wserver_address; Util::UTF8ToWide(server_address.c_str(), &wserver_address); HANDLE handle = ::CreateFile(wserver_address.c_str(), GENERIC_READ | GENERIC_WRITE, 0, NULL, OPEN_EXISTING, FILE_FLAG_OVERLAPPED | SECURITY_SQOS_PRESENT | SECURITY_IDENTIFICATION | SECURITY_EFFECTIVE_ONLY, NULL); if (INVALID_HANDLE_VALUE != handle) { handle_.reset(handle); if (!manager->IsValidServer(mozc::GetServerProcessId(handle_.get()), server_path)) { LOG(ERROR) << "Connecting to invalid server"; last_ipc_error_ = IPC_INVALID_SERVER; return; } last_ipc_error_ = IPC_NO_ERROR; connected_ = true; return; } else { DLOG(ERROR) << "CreateFile failed: " << ::GetLastError(); } if (ERROR_PIPE_BUSY != ::GetLastError()) { LOG(ERROR) << "Server is not running: " << ::GetLastError(); manager->Clear(); continue; } // wait for 10 second until server is ready // TODO(taku): control the timout via flag. #ifdef _DEBUG const int kNamedPipeTimeout = 100000; // 100 sec #else const int kNamedPipeTimeout = 10000; // 10 sec #endif DLOG(ERROR) << "Server is busy. waiting for " << kNamedPipeTimeout << " msec"; if (!::WaitNamedPipe(wserver_address.c_str(), kNamedPipeTimeout)) { LOG(ERROR) << "WaitNamedPipe failed: " << ::GetLastError(); continue; // go 2nd trial } } }
って感じの実装になっていて、 CreateFile + NamedPipeの実装です。
多分、ここで紹介されているテクニックです。
http://www.codeproject.com/KB/threads/Win32IPC.aspx
私は、このテクニックを使ったことがなくて、今までIPCを実装するときは、 FileMapping と EventObject で実装していました。
このことをtwitter でつぶやくと、@enoguさんから .NET Framework の IPCチャネルの実装も名前つきパイプで実装されているというレスをもらいました。
http://twitter.com/super_rti/status/13858083936
http://twitter.com/enogu/status/13858157887
http://twitter.com/enogu/status/13858460365
http://twitter.com/enogu/status/13858603188
大変勉強になりました。ありがとうございます。
TRIE は tx.cの改良版?
third_party というディレクトリの中に rx.c というファイルがありました。
で、同じ階層の README を見てみると、 ↓のサイトへのリンクがありました。
http://www-tsujii.is.s.u-tokyo.ac.jp/~hillbig/tx-j.htm
TxはコンパクトなTrieを構築するためのライブラリです.従来のTrieの実装(darts等)に比べ1/4〜1/10の作業領域量で辞書を保持することができ、数億〜十億キーワードなど大規模な辞書を扱うことが可能です.Trieは文字列からなるキー集合を処理するデータ構造で、キーが辞書に含まれているかのみではなく、キーのPrefixが含まれているかを高速に求めることができます.内部データ構造には Succinct Data StructureであるLevel-Order Unary Degree Sequence (LOUDS)を利用しています.
と、いうことで、 これらのアルゴリズムは google ime の実装に関するセミナーで聞いた情報とだいたいあっています。
まだ詳しくは読んでいないのですが、 tx を元に 改良したのが google ime で使っている rx で、 TRIE の部分だと思います。
まだ、ぜんぜん追いきれていない。