Singleton のインスタンス取得関数内の条件分岐を減らしたい

## ことの発端

個人的な経験則ですが、グローバルオブジェクトやグローバルステートなるものは使わないに越したことがない。しかし、大人の事情でどうしても必要になるケースが出てきたりします。（単純にインスタンスを引き回すのが面倒なだけという話もありますが[^1]）
そんなグローバルオブジェクトの代表格である `Singleton` クラス。
こやつを C++ で書くと概ねこんな感じになり、かれこれ10年以上のお付き合い。
（ `boost::noncopyable` を使っているところをみると、まだC++11が主流じゃ無い頃に書いたコードっぽいな）

[^1]: まぁ、そうなると、オブジェクトの生存期間というややこしい問題も出てきますので、素直に Rust を使うべきでしょうね。知らんけど。

```cpp:Singleton.h（かれこれ10年以上使っているコード）
#ifndef Singleton_h
#define Singleton_h

#include <boost/noncopyable.hpp>
#include <boost/thread.hpp>

template <class T> class Singleton
: public boost::noncopyable
{
private:
    static T*   s_instance;
    static boost::recursive_mutex s_instance_mtx;
    
protected:
public:
    static void initialize()
    {
        boost::unique_lock<boost::recursive_mutex> lock(s_instance_mtx);
        if(s_instance != nullptr) return;
        s_instance = new T();
    }
    
    static void finalize()
    {
        boost::unique_lock<boost::recursive_mutex> lock(s_instance_mtx);
        if(s_instance == nullptr) return;
        delete s_instance;
        s_instance = nullptr;
    }
    
    static T& instance()
    {
        if(__builtin_expect(s_instance != nullptr, 1)){
            return *s_instance;
        }
        initialize();
        return *s_instance;
    }
};

template <class T> T* Singleton<T>::s_instance = nullptr;
template <class T> boost::recursive_mutex Singleton<T>::s_instance_mtx;

#endif /* Singleton_h */
```

これはこれで良いのですが、 `Singleton` のインスタンス取得関数である `instance()` って登場回数が多くなる場合が多く、どうしても `instance()` 内の条件分岐が速度面に大きく影響するんじゃないかと考えてしまうのです。それもあって `__builtin_expect`　を使って予測分岐で「どっちのケースが多いよ」と指示を出しているんですが、それでも、命令の並べ替え（trueで条件分岐するか、falseで条件分岐するか）はしてくれても、分岐そのものがゼロになる訳じゃありません。（これが速度面にどう影響するかは、命令のプリフェッチや先読みやパイプラインやストールなんかの話をしないといけないので割愛）

## 思いつき　（TypeScript）

そんな感じで暫くは前述の　`Singleton` を使っていたので、　`Singleton` と向かい合う機会も減ったのです。
その後、時代が変わり TypeScript のコードを書く機会も増えてきて、その TypeScript で `Singleton` を実装することになりました。その際に、思いつきで、「インスタンス取得関数を差し替えると分岐が減るんじゃないかしら？」と思ったのです。（脳内では分岐を減らす定石である自己コード改変をイメージして）

https://github.com/terukazu-inoue/RapidSingleton/blob/master/RapidSingleton.ts

```ts:TypeScriptで比較した
class Singleton
{
  private static sInstance?: Singleton = undefined;
  private static sFuncInstance = () => {
    Singleton.sInstance = new Singleton();
    Singleton.sFuncInstance = () => Singleton.sInstance!;
    return Singleton.sInstance;
  };
  public static get Instance() { return Singleton.sFuncInstance(); }
}

class SingletonOld
{
  private static sInstance?: SingletonOld = undefined;
  public static get Instance() { 
    if(SingletonOld.sInstance) return SingletonOld.sInstance;
    SingletonOld.sInstance = new SingletonOld();
    return SingletonOld.sInstance; 
  }
}

const t0 = performance.now();


for(let i = 0; i < 100000000; i++){
  Singleton.Instance;
}

const t1 = performance.now();

for(let i = 0; i < 100000000; i++){
  SingletonOld.Instance;
}

const t2 = performance.now();

console.log(`t0 ~ t1 : ${t1 - t0}ms`);
console.log(`t1 ~ t2 : ${t2 - t1}ms`);

// x 53 faster
// t0 ~ t1 : 50.8900000131689ms
// t1 ~ t2 : 2678.6900000006426ms
```

いや〜 TypeScript は排他制御を考えなくてよいので楽ちん。
あ、それはそれとして、結果は53倍の高速化に成功しました。
まぁ、 TypeScript だとジェネリクスで Singleton を作るような腕は持ち合わせていないので（[「2022/7/28 追記」](#2022728-追記)でリベンジしました）、こんな感じになるのですが（今、書いていて、アロケータ関数を引数にすれば行けそうな気がしてきた[^2]）、これを C++ でやってみようと思っていながら数年が経過し、ようやく機会があって作ってみました。

[^2]: TypeScriptの gererics は C++ の template と異なって特殊化というプロセスは存在しないので、当然 generics 内の static 関数で型パラメータが扱える訳もなくダメだこりゃという結果でした。まぁ、私と似たような考えの方がいて、私の代わりに[フルボッコ](https://github.com/microsoft/TypeScript/issues/32211)されてました。（苦笑）

## C++ での実装

こんな感じで実装。

```cpp:Singleton.h(新型)
#if !defined(__h_Singleton__)
#define __h_Singleton__

#include "guard.h"
#include <functional>

template <typename T> class Singleton
{
private:
    static guard<T*> s_instance_ptr;

protected:
public:
    static std::function<T&()> instance;
};

template <class T> guard<T*> Singleton<T>::s_instance_ptr;
template <class T> std::function<T&()> Singleton<T>::instance = []() -> T& {
  return *Singleton<T>::s_instance_ptr.template block<T*>([](T** instance){
    if(*instance == nullptr){
      *instance = new T();
      Singleton<T>::instance = []() -> T& {
        return *Singleton<T>::s_instance_ptr.load();
      };
    }
    return *instance;
  });
};

#endif /* !defined(__h_Singleton__) */
```

基本的に TypeScript の `Singleton` と考え方は同じなのですが、初回の `instance()` 呼び出しが複数のスレッドから突入された場合を考慮して、排他制御が入っていて少々ややこしいかもですが、分岐はこの初回だけで、以降は分岐することが無いので、きっと高速化になる筈。（だといいな〜）
ちなみに、　`gurad` なんですが `std::atomic`　だとスコープのロックが出来ない（と思っている）ので、簡単な排他制御クラスを実装して、 `Singleton` で使っています。

```cpp:guard.h
#if !defined(__h_guard__)
#define __h_guard__

#include <mutex>

template <typename T> class guard {
private:
  std::recursive_mutex  m_mtx;
  T                     m_value;

public:
  guard(T value = T()) : m_value(value) {}
  
  T exchange(T newValue) {
    std::unique_lock lock(m_mtx);
    T oldValue = m_value;
    m_value = newValue;
    return oldValue;
  }
  
  T load() {
    std::unique_lock lock(m_mtx);
    T value = m_value;
    return value;
  }
  
  template <typename R> R block(std::function<R(T*)> f) {
    std::unique_lock lock(m_mtx);
    return f(&m_value);
  }
  
  void reset(T value = T()){
    std::unique_lock lock(m_mtx);
    m_value = value;
  }
};

#endif /* !defined(__h_guard__) */
```

## 速度計測

後で評価をしたいと思いま〜す。


### 2021/9/22　計測結果

見事に負けました。。。orz

|方式|結果|
|:-:|-:|
|新方式|209,818ns|
|旧方式|15,649ns|

敗因は guard クラスの `load()` 内での mutex 操作でキャシュのフラッシュが発生して速度が遅延していると気付いたが負けは負け。。。 う〜む。。。
ならばリベンジ！！

<details>
<summary>惨敗時のテストコード</summary>
<div>

```cpp
#include <iostream>
#include <functional>
#include <mutex>
#include <chrono>

template <typename T> class guard {
private:
  std::recursive_mutex  m_mtx;
  T                     m_value;

public:
  guard(T value = T()) : m_value(value) {}
  
  T exchange(T newValue) {
    std::unique_lock lock(m_mtx);
    T oldValue = m_value;
    m_value = newValue;
    return oldValue;
  }
  
  T load() {
    std::unique_lock lock(m_mtx);
    T value = m_value;
    return value;
  }
  
  template <typename R> R block(std::function<R(T*)> f) {
    std::unique_lock lock(m_mtx);
    return f(&m_value);
  }
  
  void reset(T value = T()){
    std::unique_lock lock(m_mtx);
    m_value = value;
  }
};

namespace NEW {
template <typename T> class Singleton
{
private:
    static guard<T*> s_instance_ptr;

protected:
public:
    static std::function<T&()> instance;
};

template <class T> guard<T*> Singleton<T>::s_instance_ptr;
template <class T> std::function<T&()> Singleton<T>::instance = []() -> T& {
  return *Singleton<T>::s_instance_ptr.template block<T*>([](T** instance){
    if(*instance == nullptr){
      *instance = new T();
      Singleton<T>::instance = []() -> T& {
        return *Singleton<T>::s_instance_ptr.load();
      };
    }
    return *instance;
  });
};
}

namespace OLD {
template <class T> class Singleton
{
private:
    static T*   s_instance;
    static std::recursive_mutex s_instance_mtx;

protected:
public:
    static void initialize()
    {
        std::unique_lock<std::recursive_mutex> lock(s_instance_mtx);
        if(s_instance != nullptr) return;
        s_instance = new T();
    }

    static void finalize()
    {
        std::unique_lock<std::recursive_mutex> lock(s_instance_mtx);
        if(s_instance == nullptr) return;
        delete s_instance;
        s_instance = nullptr;
    }

    static T& instance()
    {
        if(__builtin_expect(s_instance != nullptr, 1)){
            return *s_instance;
        }
        initialize();
        return *s_instance;
    }
};
template <class T> T* Singleton<T>::s_instance = nullptr;
template <class T> std::recursive_mutex Singleton<T>::s_instance_mtx;
}

class NewClass : public NEW::Singleton<NewClass> {
private:
    volatile int x;
    
public:
    NewClass() : x(0) {}
    int getAndIncrement() { return x++; }
};

class OldClass : public OLD::Singleton<OldClass> {
private:
    volatile int x;
    
public:
    OldClass() : x(0) {}
    int getAndIncrement() { return x++; }
};


int main(void){
    NewClass::instance();
    OldClass::instance();
    {
        const auto t1 = std::chrono::system_clock::now();
        while(NewClass::instance().getAndIncrement() < 10000) {}
        const auto t2 = std::chrono::system_clock::now();
        std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - t1).count() << std::endl;
    }
    {
        const auto t1 = std::chrono::system_clock::now();
        while(OldClass::instance().getAndIncrement() < 10000) {}
        const auto t2 = std::chrono::system_clock::now();
        std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - t1).count() << std::endl;
    }

}
```

</div>
</details>



### 2021/9/22　計測結果（リベンジ）

前回よりは早くなったものの、なんとも微妙な結果。。。
悔しいけど逆効果という結果になりました。。。

|方式|結果|
|:-:|-:|
|新方式（タイプ２）|15,799ns|
|旧方式|15,154ns|

<details>
<summary>リベンジ時のテストコード</summary>
<div>

```cpp
#include <iostream>
#include <functional>
#include <mutex>
#include <chrono>

namespace NEW {
template <typename T> class Singleton
{
private:
    static std::recursive_mutex s_instance_mtx;

protected:
public:
    static std::function<T&()> instance;
};

template <class T> std::recursive_mutex Singleton<T>::s_instance_mtx;
template <class T> std::function<T&()> Singleton<T>::instance = []() -> T& {
  if(Singleton<T>::s_instance_mtx.try_lock()){
    T* inst = new T();
    Singleton<T>::instance = [inst]() -> T& {
      return *inst;
    };
    Singleton<T>::s_instance_mtx.unlock();
    return *inst;
  }
  std::unique_lock<std::recursive_mutex> lock(Singleton<T>::s_instance_mtx);
  return Singleton<T>::instance();
};
}

namespace OLD {
template <class T> class Singleton
{
private:
    static T*   s_instance;
    static std::recursive_mutex s_instance_mtx;

protected:
public:
    static void initialize()
    {
        std::unique_lock<std::recursive_mutex> lock(s_instance_mtx);
        if(s_instance != nullptr) return;
        s_instance = new T();
    }

    static void finalize()
    {
        std::unique_lock<std::recursive_mutex> lock(s_instance_mtx);
        if(s_instance == nullptr) return;
        delete s_instance;
        s_instance = nullptr;
    }

    static T& instance()
    {
        if(__builtin_expect(s_instance != nullptr, 1)){
            return *s_instance;
        }
        initialize();
        return *s_instance;
    }
};
template <class T> T* Singleton<T>::s_instance = nullptr;
template <class T> std::recursive_mutex Singleton<T>::s_instance_mtx;
}

class NewClass : public NEW::Singleton<NewClass> {
private:
    volatile int x;
    
public:
    NewClass() : x(0) {}
    int getAndIncrement() { return x++; }
};

class OldClass : public OLD::Singleton<OldClass> {
private:
    volatile int x;
    
public:
    OldClass() : x(0) {}
    int getAndIncrement() { return x++; }
};


int main(void){
    NewClass::instance();
    OldClass::instance();
    {
        const auto t1 = std::chrono::system_clock::now();
        while(NewClass::instance().getAndIncrement() < 10000) {}
        const auto t2 = std::chrono::system_clock::now();
        std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - t1).count() << std::endl;
    }
    {
        const auto t1 = std::chrono::system_clock::now();
        while(OldClass::instance().getAndIncrement() < 10000) {}
        const auto t2 = std::chrono::system_clock::now();
        std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - t1).count() << std::endl;
    }

}
```

</div>
</details>


## 結論

`Singleton` でのインスタンス取得関数を差し替える方式は、 TypeScript では効果があるけど、 C++ では殆ど効果なし。（正確には逆効果）
ということで、旧式の `Singleton` とは、これまで通りのお付き合いという感じです。（浮気しちゃってゴメンなさい）

ただ、言語によって効果があるアプローチと逆効果なアプローチがあることを体感できて満足しました。
いや〜やってみないと分からないものだわ。

## 2022/7/28 追記

TypeScript のメタプログラミングを満喫して、ようやくジェネリクスで Singleton を作れるようになりました。（苦笑）
派生とか mix-in じゃないので、若干手数が増えますが、いうても２行程度なので、ここまでやれば使えそうです。（関数呼び出しが１段階増えるので、以前のべた書きよりは速度が劣ります）

```ts:singleton.ts
class Singleton<CREATOR extends () => any>
{
  private m_fnGetInstance: () => ReturnType<CREATOR>;
  public get Instance() { return this.m_fnGetInstance(); }
  public constructor(creator: CREATOR) {
    this.m_fnGetInstance = () => {
      const instance = creator();
      this.m_fnGetInstance = () => instance;
      return instance;
    };
  }
}
```

```ts:元となるクラス
class X {
  public constructor() {}
  public value = "abc";
}
```

```ts:Singleton化
class X {
  private constructor() {} /* privateにする */
  public value = "abc";

  /* 下記を追加 */
  private static ston = new Singleton(() => new X());
  public static get Instance() { return X.ston.Instance; }
}

console.log(X.Instance.value);
```

```ts:匿名クラスを使うとシンプルに書ける
const X = new Singleton(() => new class {
  public constructor() {}
  public value = "abc";
}());

console.log(X.Instance.value);
```

TypeScriptではC++のように型から値（オブジェクト）が生成できないので、値を生成する関数を渡すことで長年悩んでいたSingletonのジェネリクス化をすることができました。
ということで npm に公開しました。

https://www.npmjs.com/package/@codianz/singleton