茂加部珈琲店

主にtech関連のメモ置き場です

線形補間の実装の比較

c++

線形補完をいろんな方法で実装して、生成されるアセンブリを比較してみたいと思います

素直な実装

float lerp(float t, float v0, float v1) {
  return (1-t) * v0 + t * v1;
}

加減算が2, 乗算が2の実装です
t=0の時v0,t=1の時v1が保証されます（多分)

  • g++ 8.2 -O2
lerp(float, float, float):
  movss   xmm3, DWORD PTR .LC1[rip]
  subss   xmm3, xmm0
  mulss   xmm0, xmm2
  mulss   xmm1, xmm3
  addss   xmm0, xmm1
  ret

普通ですね
最初に1.fを読み込んでいます

  • clang++ 6.0 -O2
lerp(float, float, float):
  movss   xmm3, dword ptr [rip + .LCPI5_0] # xmm3 = mem[0],zero,zero,zero
  subss   xmm3, xmm0
  mulss   xmm3, xmm1
  mulss   xmm2, xmm0
  addss   xmm3, xmm2
  movaps  xmm0, xmm3
  ret

ほぼg++と同じ

次はFMA命令を有効化してみます

  • g++ 8.2 -O2 -march=native -ffp-contract=fast
lerp(float, float, float):
  vmovss  xmm3, DWORD PTR .LC0[rip]
  vsubss  xmm3, xmm3, xmm0
  vmulss  xmm0, xmm0, xmm2
  vfmadd231ss     xmm0, xmm3, xmm1
  ret

fmaが最後に入ってますね
精度的に若干有利なはず

  • clang++ 6.0 -O2 -march=native -ffp-contract=fast
lerp(float, float, float):
  vmovss  xmm3, dword ptr [rip + .LCPI5_0] # xmm3 = mem[0],zero,zero,zero
  vsubss  xmm3, xmm3, xmm0
  vmulss  xmm0, xmm0, xmm2
  vfmadd213ss     xmm3, xmm1, xmm0
  vmovaps xmm0, xmm3
  ret

ほぼ同じ

O3とかは危険な式変形やりだすので除外

精度を犠牲にした実装

float lerp(float t, float v0, float v1) {
  return v0 + (v1 - v0) * t;
}

乗算が減るけど、t=1のときにv0 + (v1 - v0)になるので結果がきっちりv1になる保証はありません

  • g++ 8.2 -O2
lerp(float, float, float):
  subss   xmm2, xmm1
  mulss   xmm2, xmm0
  movaps  xmm0, xmm2
  addss   xmm0, xmm1
  ret

普通ですね。clang++もほぼ同じなので省略します

次はFMAあり

  • g++ 8.2 -O2 -march=native -ffp-contract=fast
lerp(float, float, float):
  vsubss  xmm2, xmm2, xmm1
  vfmadd132ss     xmm0, xmm1, xmm2
  ret

除算とFMA命令のみ。はやそうです
ただt=1の時の誤差問題は解決できません
clang++も全く同じコードを吐きます

バランスの良い実装

float lerp(float t, float v0, float v1) {
  return t * v1 - (t * v0 - v0);
}

加減2,乗2と最初の実装と同じですが、順番が違います
t=0,t=1の結果がv0,v1になることが保証されます（多分）

  • g++ 8.2 -O2
lerp(float, float, float):
  mulss   xmm2, xmm0
  mulss   xmm0, xmm1
  subss   xmm0, xmm1
  subss   xmm2, xmm0
  movaps  xmm0, xmm2
  ret

普通ですね
clang++も同じコードを吐きます

FMAを入れてみると

  • g++ 8.2 -O2 -march=native -ffp-contract=fast
lerp(float, float, float):
  vfmsub132ss     xmm1, xmm1, xmm0
  vfmsub132ss     xmm0, xmm1, xmm2
  ret

FMA系命令2つだけになります
clang++でも同様

おまけ MSVCでやってみる

  • msvc 19.14 /O2 /fp:fast /arch:AVX2
lerp, COMDAT PROC
  vmulss   xmm3, xmm0, xmm2
  vmovaps xmm2, xmm1
  vfmsub213ss xmm2, xmm0, xmm1
  vsubss   xmm0, xmm3, xmm2
  ret      0

なんでやねん

まとめ

線形補完の実装は、精度と速度のトレードオフが存在する。
こんなに簡単なコードでも浮動小数点数が絡むと大変になる。浮動小数点数こわい。
最近のコンパイラはstd::fmaとか使わなくても勝手にやってくれる。
標準はstd::fmaだけですが、FMA系命令は他にも色々あります。

static constで宣言してconstexprで初期化する

c++

以下のコードはコンパイルに失敗します

struct Foo {
  // error: 'constexpr const Foo Foo::s' has incomplete type
  static constexpr Foo s = {}; 
};
constexpr Foo Foo::s;

constexprは宣言と初期化を一緒にしないといけないので、以下のようにしてもコンパイルできません。

struct Foo {
  // error: 'constexpr' static data member 's' must have an initializer
  static constexpr Foo s;
};
constexpr Foo Foo::s = {};

そういう時は、宣言をstatic constに変えるとコンパイルできます。

struct Foo {
  static const Foo s;
};
constexpr Foo Foo::s = {};

規格的にはおそらくこれは違法では無いと思いますが、私もいまいちよくわかってません。
static constで宣言された場合は、constexprで初期化されるまではconstexprで使用することはできません。
以下のコードはコンパイルできません

struct Foo {
  static const Foo s;
};
constexpr Foo g = Foo::s;
constexpr Foo Foo::s = {};

しかし、次のコードはコンパイルできます

struct Foo {
  static const Foo s;
};
constexpr Foo Foo::s = {};
constexpr Foo f = Foo::s;

これをヘッダと実装で分けたりするのはあまりおすすめできません

constexprでメンバ変数のオフセットを取得する

c++

constexprでも頑張ればメンバオフセットを取得できるみたいです。constexpr版offsetofですね
コードはこのGithubでの議論あたりを参考にしました。

コンパイルにはc++17が必要です
gcc 7.0 / clang 6.0 あたりでコンパイルできます。
msvcは VS2017 15.8 Preview 3からコンパイルできようになりました。やったね！

  template <typename T1, typename T2>
  struct offset_of_member_impl {
    union U {
      U() : c{} {}
      ~U() {}
      char c[sizeof(T2)];
      T2 o;
    };
    static U u;
    static constexpr size_t get(T1 T2::*member) {
      size_t i = 0;
      for (; i < sizeof(T2); ++i)
        if (((void*)&(u.c[i])) == &(u.o.*member)) break;

      // g++ bug 67371 workaround
      if (i >= sizeof(T2))
        throw std::runtime_error("failed to detect offset");
      else
        return i;
    }
  };

  // suppress warning
  template <class T1, class T2>
  typename offset_of_member_impl<T1, T2>::U offset_of_member_impl<T1, T2>::u{};

  /// get offset of member
  template <class T1, class T2>
  constexpr size_t offset_of_member(T1 T2::*member) {
    return offset_of_member_impl<T1, T2>::get(member);
  }

g++のバグを回避するためにループをばらしています。
こんな感じで使います

struct A {
  int i;
  char c;
  double d;
};

int main() {
  constexpr size_t offi = offset_of_member(&A::i);
  constexpr size_t offc = offset_of_member(&A::c);
  constexpr size_t offd = offset_of_member(&A::d);
  
  std::cout << offi << std::endl; //0
  std::cout << offc << std::endl; //4
  std::cout << offd << std::endl; //8
}

VSCodeでMSYS2+fishを使う

settings.jsonに以下を追加すればよい

    "terminal.integrated.shell.windows": "C:\\Windows\\System32\\cmd.exe",
    "terminal.integrated.shellArgs.windows": [
        "/K","C:\\msys64\\msys2_shell.cmd -mingw64 -defterm -no-start -here -full-path -c fish & exit 0"
    ]

ターミナル起動時にfishを呼んで、fishが終了したときにターミナルも終了させます
なんか時々表示が崩れたり謎の改行が入ったりする

追記:
改行文字(\u23CE)が表示されるのはWindowsのバグなのでしょうかね

github.com

参照: msys2_shell.cmdを使ってVS Codeの総合シェルをMSYS2 bashにする

フレキシブル配列メンバをC++で

c++

こんにちは。c++ネタ。

flexible array member

プログラミングをしていると、大きさのわからない配列を扱いたい時があります。
間接参照を挟まず、構造体に直接配列を埋め込む手法はCなどではよく使われています
こういった配列を扱うため、C99からはフレキシブル配列flexible array memberという機能が追加されました。 使い方は以下のようになります

struct flexArrayStruct {
  int num;
  int data[];
};

末尾のdata[]がフレキシブル配列で、要素数の不明な配列を表します。プログラムは実行時に任意の長さのペイロードを含むオブジェクトをメモリ上に確保してアクセスすることができます。

フレキシブル配列の実体は大雑把に言えば大きさ0の配列です。つまり、事前に「次に来る要素」にアクセスする手段を提供する手段ということです。

C++でフレキシブル配列メンバを模倣する その１

本題に入りますが、C++はC99ベースに作られていないので、フレキシブル配列を使用することはできません。
いくつかのコンパイラは独自拡張としてフレキシブル配列をサポートしています

struct flexArrayStruct {
    int num;
    int data[]; // gcc/clangでコンパイル可能
};

しかし、フレキシブル配列を持つクラスは継承することができません。

  struct Derived : flexArrayStruct {}; // error: base class 'flexArrayStruct' has a flexible array member

これは異論がある人もいると思いますが、フレキシブル配列を持つ構造体を継承すれば、ポインタがキャスト可能になり若干嬉しいです。
そこで、フレキシブル配列ではなく、長さゼロの配列を使用します

// gcc/clangでコンパイル可能
struct flexArrayStruct {
    int num;
    int data[0] = {};
};

struct Derived : flexArrayStruct {
    Derived() :flexArrayStruct{8} {}
    int data[8] = {1,2,3,4,5,6,7,8};
};

flexArrayStruct::dataとDerived::dataはメモリ上で同一の場所を表します。
C++の規格上は、長さゼロの配列も、固有のアドレスを持たないオブジェクトも違法です。
そもそも配列の要素数を超えたアクセスはUBですが、耳から天使を召喚して何とかしてください
(ちなみにstd::array<0>は許されていますが、オブジェクトのサイズはゼロではないので注意) また、clang/gccではコンパイルできますが、ゼロ長配列を持つ基底クラスを許さないmsvcではコンパイルできません。

C++でフレキシブル配列メンバを模倣する その2

MSVCでもコンパイルしたい場合は上記の手法は使えませんでした。
こういうときは何も考えずにテンプレートを使ってみるのがC++流

template <int N=1>
struct A : A<N-1> {
    int _data_element= {};
};
template <>
struct A<1> {
    int num;
    int data[1] = {};
};
struct D : A<8> {
  D() :A<8>{8,1,2,3,4,5,6,7,8} {}
};

うーん… 非常に危険な香りがしますね

いずれにせよ、C++でフレキシブル配列を行儀よくやるのは無理そうというのが感想です。 より行儀が良い手法としてはポインタ演算でゴリゴリやるしかなさそうです。 フレキシブル配列メンバが規格に入れば良いんですが、忘れられてしまったんでしょうか

[g++7.1] ジェネリックラムダが不要な場合にもインスタンス化されるバグ

c++

ちょっと調べたのでメモ
以下のコードはg++ 7.1、g++7.2でコンパイルに失敗します。

#include <variant>
template<class... Ts> struct overloaded : Ts... { using Ts::operator()...; };
template<class... Ts> overloaded(Ts...) -> overloaded<Ts...>;

using v = std::variant<double, long, bool>;
 
constexpr const char* get_name(const v& v) {
   return std::visit(
    overloaded{
      [](bool) constexpr { return "bool"; },
      [](double) constexpr { return "double"; },
      [](long) constexpr { return "long"; }, 
      // 網羅していない場合はコンパイルを失敗させる
      [](auto a) constexpr { static_assert(!sizeof(decltype(a)));  }},
    v);
}

これはジェネリックラムダが不要な場合にもインスタンス化されるためです。
以前から報告されており、g++7.3で修正されました。

メンバ関数テンプレートでC2783が出る場合

c++

小ネタなのですが VC++(VS2017 15.5.2)で以下のコードはコンパイルに失敗します。
clangとgccでは通ります。

#include <type_traits>

struct Foo {
  template <class U = int, class = std::enable_if_t<std::is_same_v<U,int>>>
  void f();
};

//template <class U, class> // <- Ok.
template <class, class> // <- C2783: could not deduce template argument for '<unnamed-symbol>'
void Foo::f(){}

int main()
{
  Foo f;
  f.f();
}

エラメッセージでは宣言を確認してくださいなどと書かれていますが、問題はコメントアウトしてあるテンプレートパラメータのようです。
型名までしっかり一致させないといけないので注意。