std::mapの高速化に対する一考

概要

連想配列、連想コンテナ、辞書、ハッシュ、マップ、実装方法の違いもあるが、キーを指定して値を得るという機能としては、全て同じもの。
c++のライブラリとしては、std::map、もしくは、std::unordered_mapとして提供される。前者がツリー構造で実装されるに対し、後者は高速なハッシュテーブルで実装される。使えるならstd::unordered_mapを使え！というの別な記事。
連想配列のキーは文字列であることが多いため、c++でユニコードをを使わないならstd::stringを使うのが普通だろう。では、std::string_viewや独自の文字列型を使ったならば速くなる？という話。
個人的な見解は、std::stringは最速ではないが、実装を複雑にするくらないならstd::stringを使うのがよい！というタイトルに掲げたわりには無難な判断。begin()とイテレータを使ってmapを走査したり、find()でイテレータを取得するときは、イテレータを参照の構造化束縛で受けること。もちろん、用途、条件によっては判断が異なるかもしれない。

std::mapのイテレータの問題について

begin()やfindの戻り値であるイテレータのoperatr*()は、std::pairのリファレンスを返す。Key=std::stringなら、戻り値を生成するごとに代入するごとにstd::stringのコピーコンストラクタ（メモリ確保を伴うコピー）がコールされるのでオーバヘッドが発生する。イテレータが保持するstd::stringは、普通書き換えることはないのでconst std::string&が取得できれば十分だけど、そのようなインターフェースになっていない。

処理案

1. string_viewを使う
2. メモリ確保の少ない独自のstringクラス
3. イテレータをconst参照で受ける 　
   ※書き換えを考えるなら参照でもよいが、ベンチマークは省略

1.string_viewを使う

実装例

std::map<std::string_view,std::string_view> sv_map;
sv_map["abc"] = "abc" //文字リテラルなので問題ない（文字リテラルはコード領域に定義されている）

問題のある実装

std::map<std::string_view,std::string_view> sv_map;

std::string str = "def";　//実体はヒープに確保
sv_map[def] = def;

strが破棄されると、sv_mapの参照先が不定になってしまう。

改善した実装

std::string　unified_str;
std::map<std::string_view,std::string_view> sv_map;

std::string str = "def";　//実体はヒープに確保

auto pos = unified_str.size(); 
unified_str.resize(pos+str.size());
std::copy_n(&unified_str[pos],str.size(),&str[0]);
std::string_view sv(&unified_str[pos],

sv_map[sv] = sv;

unified_strがsv_mapと同じかそれより長く生存している必要があるが、2つとも同じスコープで定義すれば、生存期間を同じにできる。ただし、mapの要素が削除される場合でも、unified_strのデータを除去することが難しいので、肥大化する一方になってしまう。再構築などの施策は必要かもしれない。

2.独自のstringクラス

概要
mapのキーにするためには、文字リテラルからのコンストラクト、コピーコンストラクタ、比較関数が実装されていればよい。
boost::container::small_vectorの考え方と同じで、文字列サイズが指定値よりも小さいときは、メモリ確保が行われないようにした。
文字列サイズが大きい場合は、メモリ確保するが、参照カウンターを使ってコピーコストがかからないようにした。
キーと値の追加は、文字リテラルでも、std::stringでも問題ない。値を取得する場合は、sv()メンバ関数で、const string_viewオブジェクトとして得る。

実装例

#include <map>
#include <vector>
#include <iostream>
#include <string_view>
#include <string>
#include <sstream>
#include <iostream>
#include <regex>
#include <utility>
#include <algorithm>
#include <charconv>
#include <array>
#include <functional>


#define CONST_BASIC_STRING_MODE 1

template<class T, int _N>
struct  alignas(8) const_basic_string
{
  static constexpr int N = (_N+7)/8*8 < 16 ? 16 : (_N + 7) / 8 * 8;
  const_basic_string()
  {
#if CONST_BASIC_STRING_MODE <=1
    use_arr(true);
#else
    ptr_ = nullptr;
#endif
    size_ = 0;
  }

  ~const_basic_string()
  {
    release();
  }

  void release()
  {
    if(size_ == 0) return;

    if (!use_arr()){
      if (ref_count() <= 1){
        delete ptr_;
      }else{
        (ref_count())--;
      }
    }
#if CONST_BASIC_STRING_MODE <=1
    use_arr(true);
#else
    ptr_ = nullptr;
#endif
    size_ = 0;
  }

  template<int N1>
  const_basic_string& operator=(const const_basic_string<T,N1>& bs)
  {
    release();
    copy(bs);
    return *this;
  }

  
  const_basic_string& operator=(const const_basic_string& bs)
  {
    release();
    copy(bs);
    return *this;
  }

  const_basic_string& operator=(std::basic_string_view<T> sv)
  {
    release();
    assign(sv);
    return *this;
  }

  const_basic_string& operator=(const T* str)
  {
    release();
    std::basic_string_view<T> sv(str);
    assign(sv);
    return *this;
  }

  const_basic_string& operator=(const std::string& str)
  {
    release();
    std::basic_string_view<T> sv(str);
    assign(sv);
    return *this;
  }

  auto begin() const
  {
    return sv().begin();
  }

  auto end() const
  {
    return sv().end();
  }


  template<int N1>
  const_basic_string(const const_basic_string<T,N1>& bs)
  {
    copy(bs);
  }

  const_basic_string(const const_basic_string& bs)
  {
    copy(bs);
  }


  const_basic_string(const T* str) : const_basic_string(std::basic_string_view<T>(str)) {}

  const_basic_string(std::basic_string_view<T> sv)
  {
    assign(sv);
  }

  const_basic_string(const std::string& str)
  {
    assign(str);
  }


#if 0
  const std::basic_string_view<T>& sv() const
  {
    return sv_;
  }
#else
  const std::basic_string_view<T> sv() const
  {
    if (use_arr()) {
      return std::basic_string_view<T>(arr_, static_cast<size_t>(size_));
    }else{
      return std::basic_string_view<T>(ptr(),static_cast<size_t>(size_) );
    }
  }
#endif

  size_t size() const
  {
    return size_;
  }
  private:
#if CONST_BASIC_STRING_MODE==0
  static constexpr size_t SIZE = N;

  union {
    T arr_[N];
    char* ptr_;
  };
  int size_;
  bool use_arr_;

  bool use_arr() const
  {
    return use_arr_;
  }

  void use_arr(bool b)
  {
    use_arr_ = b;
  }

#elif CONST_BASIC_STRING_MODE==1
    static constexpr size_t SIZE = N-1;

    union {
      T arr_[N];
      char* ptr_;
    };
    size_t size_;

    bool use_arr() const
    {
      return arr_[SIZE] != 0;
    }
    
    void use_arr(bool b)
    {
      arr_[SIZE] = b;
    }

#else
    static constexpr size_t SIZE = N;
    //std::array<char, N * sizeof(T)> arr_;
    T arr_[N];
    char* ptr_;
    size_t size_;

    bool use_arr() const
    {
      return ptr_ == nullptr;
    }
#endif

  
  template<int N1>
  void copy(const const_basic_string<T,N1>& bs)
  {
    if (bs.use_arr()){
      std::copy_n(bs.arr_, N, arr_);
      size_ = bs.size_;
#if CONST_BASIC_STRING_MODE == 0
      use_arr(true);//use_arr_=true;
#elif CONST_BASIC_STRING_MODE == 2
      ptr_ = nullptr;
#endif
    } else {
      ptr_    = bs.ptr_;
      size_   = bs.size_;
      (ref_count())++;
#if CONST_BASIC_STRING_MODE <= 1 
      use_arr(false);
#endif
    }
  }

  template<class STR>
  void assign(const STR& sv){
    if (sv.length() <= SIZE) {
      std::copy_n(sv.begin(), sv.size(), arr_);
      size_ = static_cast<int>(sv.length());
#if CONST_BASIC_STRING_MODE <= 1
      use_arr(true);
#elif CONST_BASIC_STRING_MODE == 2
      ptr_ = nullptr;
#endif
    } else {
      ptr_ = new char[sizeof(T) * sv.length() + sizeof(size_t)];
      ref_count() = 1;
      std::copy_n(sv.begin(), sv.length(), ptr());
      size_ = static_cast<int>(sv.length());
#if CONST_BASIC_STRING_MODE <= 1
      use_arr(true);
#endif
    }
  }
  //std::basic_string_view<T> sv_;
  const T* ptr() const
  {
    return reinterpret_cast<const T*>(ptr_ + sizeof(size_t));
  }

 
  T* ptr()
  {
    return reinterpret_cast<T*>(ptr_+ sizeof(size_t));
  }

  int& ref_count()
  {
    return *reinterpret_cast<int*>(ptr_);
  }
  

  //bool use_arr;
};

using const_string = const_basic_string<char, 16>;




template<class T, int N, int N1>
constexpr bool operator==(const const_basic_string<T,N>& a, const const_basic_string<T,N1>& b){
  return a.sv() == b.sv();
}

template<class T, int N, int N1>
constexpr bool operator!=(const const_basic_string<T, N>& a, const const_basic_string<T, N1>& b){
  return a.sv() != b.sv();
}

template<class T, int N, int N1>
constexpr bool operator<(const const_basic_string<T, N>& a, const const_basic_string<T, N1>& b) {
  return a.sv() < b.sv();
}

template<class T, int N, int N1>
constexpr bool operator>(const const_basic_string<T, N>& a, const const_basic_string<T, N1>& b) {
  return a.sv()> b.sv();
}

template<class T, int N, int N1>
constexpr bool operator<=(const const_basic_string<T, N>& a, const const_basic_string<T, N1>& b){
  return a.sv() <= b.sv();
}

template<class T, int N, int N1>
constexpr bool operator>=(const const_basic_string<T, N>& a, const const_basic_string<T, N1>& b) {
  return a.sv() >= b.sv();
}

3.const参照でうける

  std::map<std::string, std::string,std::less<>> normal_map;

　//省略
  for (const auto& [key, val] : normal_map) {ss<<val;}　

auto&&が右辺値参照で、ムーブセマンティクスが働き、無駄なコピーが減る。

ベンチマーク結果

ベンチマーク1

  int count = 200'0000;
  std::vector<std::string> strs(count);
  for (int i = 0; i < count; i++) {
    strs[i] = std::to_string(i);
  }

  std::map<std::string, std::string, std::less<>> normal_map;
  std::map<std::string_view, std::string_view, std::less<>> view_map;
  std::map<const_string, const_string> fast_map;
  
  //以下のfor文の処理時間を計測
  //0.
  for (int i = 0; i < count; i++) {
    normal_map[strs[i]] = strs[i];
  }

  //1.a.
  for (int i = 0; i < count; i++) {
    view_map[trs[i]] = trs[i];
  }

  //1.b.
  unified_str.reserve(count * 16); //予め必要なサイズをリザーブしておく必要がある
  for (int i = 0; i < count; i++) {
    size_t sz = strs[i].size();
    size_t pos = unified_str.size();
    unified_str.resize(pos + sz*2);

    std::copy_n(strs[i].data(), sz,&unified_str[pos]);
    std::copy_n(strs[i].data()+ sz, sz, &unified_str[pos+ sz]);

    std::string_view key(&unified_str[pos], sz);
    std::string_view val(&unified_str[pos+ sz],sz);
    view_map[key] = val;
  }

  //2.
  for (int i = 0; i < count; i++) {
    fast_map[strs[i]] = strs[i];
  }

各for文101回の中央値(Visual Studio 2019 ver 16.9.3でコンパイル)

keyの型	時間(ms)
0.string	6.60
1.a.string_view	4.30
1.b.string_view	6.38
2.const_string	6.12

ベンチマーク2

  std::map<std::string, std::string, std::less<>> normal_map;
  std::map<std::string_view, std::string_view, std::less<>> view_map;
  std::map<const_string, const_string> fast_map;

  //マップ構築は、ベンチマーク１を参照

  stringstream ss;

 //各for文の処理時間を計測
  for (auto [key, val] : normal_map) {ss<<val;}　　//0.a
  for (const auto& [key, val] : normal_map) {ss<<val;}　//0.b
  for (auto it& : normal_map) {const auto& [key,val] = it; ss<<val;}　//0.c
  for (auto [key, val] : view_map) {ss<<val;}     //1
  for (auto [key, val] : fast_map) {ss<<val.sv();}//2.a
  for (const auto& [key, val] : fast_map) {ss<<val.sv();}//2.b

各for文101回の中央値(Visual Studio 2019 ver 16.9.3でコンパイル)

keyの型	時間(ms)
0.a.string	1.28
0.b.string(const参照)	1.20
0.c.string(const参照)	1.18
1.string_view	1.19
2.a.const_string	1.23
2.b.const_string	1.19

ベンチマーク3

  std::map<std::string, std::string,std::less<>> normal_map;
  std::map<std::string_view, std::string_view, std::less<>> view_map;
  std::map<const_string, const_string> fast_map;

　//マップ構築は、ベンチマーク１を参照

  for (auto [key, val] : normal_map) {}//0.a
  for (const auto& [key, val] : normal_map) {}//0.b
  for (auto [key, val] : view_map) {} //1
  for (auto [key, val] : fast_map) {} //2

各for文101回の中央値(Visual Studio 2019 ver 16.9.3でコンパイル)

keyの型	時間(ms)
0.a.string	0.54
0.b.string(const参照)	0.00
1.string_view	0.47
2.const_string	0.48

考察

ベンチマーク1について

1.a.string_viewが最速。テキストパースするケースなど、すでにメモリ上にデータがあるなら、ポインタとデータサイズのコピーで済むため速い。1.bのように共通メモリにコピーすると遅くなる。std::stringは、メモリ確保が発生するためか一番遅いが、2や1.b比較で、差が500～300μsで、6598μsに対しても10%未満。

ベンチマーク2について

1.string_viewが最速でと言えるが、なにか他の処理が入る(例えば、std::string_streamへの出力)と、比率の差はわずかで無視しても良い程度かもしれない（std::string_streamへの出力の例では1%程度かそれ以下。)ベンチマーク3を考慮すると、std::string_streamへの出力にかかる時間は800μs程度だろうか。

ベンチマーク3について

0.b.string(const参照) で処理時間が0なのは、最適化が効いて無駄なコードがなくなったためと考えられる。0.b.のように構造化束縛をconst参照で受けると、0.a.のようにautoだけで受ける場合とに比べて、無駄なコピーが省かれることになる（最適化が効きやすくなる）。もし、文字列としてポインタを受け取るインラインでない関数をコールする場合、かならずポインタのコピーが発生するので、ポインタとサイズをコピーするstring_viewに対して同等か少しすくない程度の時間が実質的にかかると考えられる。

まとめ

テキストパースしてstd::mapを作るなど、すでにメモリ上に文字列が存在しているのでstd::string_viewは有効だが、このように特別な条件がない限り、コードを複雑にしないという意味で、std::mapのキーにはstd::stringを使うのが無難。また、イテレータは、以下のようにconst参照で受けるべき。値の書き換えが必要なら参照をつかう。ユニバーサル参照も受け取れるが、通常はconst参照と参照の使い分けで十分。せっかくconst_stringを作ったが、大きな効果はなかった。別なところで活用できるか考えたい。

  std::map<std::string, std::string,std::less<>> normal_map;
　//省略
  for (const auto& [key, val] : normal_map) {}　//const参照
  for (auto& [key, val] : normal_map) {} //参照

おまけ

  std::map<std::string, std::string,std::less<>> map0;
  std::map<std::string, std::string> map1;

　//マップ構築は、ベンチマーク１を参照

  //0.a
  for (int i = 0; i < count; i++) {
    map0[strs[i]] = strs[i];
  }

 //0.b
  for (int i = 0; i < count; i++) {
    map0[strs[i]] = strs[i];
  }


  for (const auto& [key, val] : map0) {ss<<val;}　//1.a
  for (const auto& [key, val] : map1) {ss<<val;}　//1.b

std::less<>	時間(ms)
0.a.あり	0.623
0.b.なし	0.604
1.a.あり	0.120
1.b.なし	0.121

std::less<>をつけたほうが原理的に速いとされるのになぜか逆転？