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::Init);

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 の部分だと思います。
まだ、ぜんぜん追いきれていない。

その他

base/util.cc が小物系の関数集です。
小物を収集するための static メソッドで構築された関数集ですね。

base/svm.cc これは。。。
名前からすると、機械学習の SVM ですか。
ほー、これはこれは。

もっと詳しく見ていたいけど、出社時間がせまったのでまたこんど!!