C++ ときどき ごはん、わりとてぃーぶれいく☆

USAGI.NETWORKのなかのひとのブログ。主にC++。

CPP-QUIZ Q5 のこたえ、マクローリン展開による sin/cos の高速化に潜んでいた大きな誤差を生じるバグ

C++ bug fix Advent Calendar 2017

概要

この記事を書くきっかけは先日書いた記事 CPP-QUIZ from Unreal 2017 ( part-1/2; 出題編 ) の Q5. について、こたえとして掲載したコードについて、 Twitter にて @nekketsuuu さんから次のようなご指摘を頂いた事でした。ありがとうございます😃

どう見ても誤差が大きすぎるし（この検証の元となった出題では std::sin との誤差が最大でも 1.0e-6f に収まるようにしたいというものだった）、明らかに癖の強い周期性が見える。

ここ数日、お仕事などでまとまったプライベート時間をなかなか確保できず、数日お待たせしてしまいましたが、この問題の原因を調査し整理できる時間を確保できたので記事として整理する事にしました。

問題を確認する

f:id:USAGI-WRP:20171212032210p:plain

「にゃーん🐾」

とりあえず、現状の問題、誤差の発生状況を把握するため、[0 .. 2π] について視覚的にプロットを把握するに十二分と思われる適当な分解能で、

  1. std::sin を計算し、
  2. SinCosB を計算し、 sin 成分を取り出し、
  3. std::sin と SinCosB の sin 成分の差の絶対値を計算して縦軸へ、入力の角度値を横軸へプロット

した絵です。こうしてみると、

  1. π/2 ごとに周期的に誤差が増減し、
  2. 最大誤差が 1.0e-6f どころか 1.0e-4f を超えてしまっている

ことが明らかです。

問題のコード（＝「こたえ編で紹介した現行の UE4 実装と等価なコード」）

#define PI 3.14159265358979f
std::tuple< float, float > SinCosB( const float angle_in_radians )
{
  float quotient = angle_in_radians * 0.5f / PI;
  if ( angle_in_radians >= 0.0f )
    quotient = (float)( (int)( quotient + 0.5f ) );
  else
    quotient = (float)( (int)( quotient - 0.5f ) );
  float a = angle_in_radians - quotient * 2.0 * PI;
  float s = 0.0f;
  if ( a > 0.5f * PI )
  {
    a = PI - a;
    s = -1.0f;
  }
  else if ( a < -0.5f * PI )
  {
    a = -PI - a;
    s = -1.0f;
  }
  else
    s = +1.0f;
  float p = a * a;
  // [ 1 / 2!, 1 / 3!, 1 / 4!, .., 1 / 11! ]
  constexpr float f2 = 1.0f / 2.0f;
  constexpr float f3 = f2 / 3.0f;
  constexpr float f4 = f3 / 4.0f;
  constexpr float f5 = f4 / 5.0f;
  constexpr float f6 = f5 / 6.0f;
  constexpr float f7 = f6 / 7.0f;
  constexpr float f8 = f7 / 8.0f;
  constexpr float f9 = f8 / 9.0f;
  constexpr float f10 = f9 / 10.0f;
  constexpr float f11 = f10 / 11.0f;
  return std::make_tuple
  ( a * ( +1.0f + p * ( -f3 + p * ( +f5 + p * ( -f7 + p * ( +f9 * p * ( -f11 ) ) ) ) ) )
  , s * ( 1.0f + p * ( -f2 + p * ( +f4 + p * ( -f6 + p * ( +f8 + p * ( -f10  ) ) ) ) ) )
  );
}

誤差が 1.0e-6f 未満となる十分な精度が得られるまでマクローリン展開を計算しています。この実装は std::sin と std::cos を使った同様の計算よりも wandbox 環境では 1.45 倍高速に動作した、めでたしめでたし、というものでした。

ところが、どうやらこの SinCos は一見すると正しくマクローリン展開を計算しているようで、残念なバグが潜んだコードだったのです。

ﾅ　ﾅﾝﾀﾞｯﾃｰ!!
Ω ΩΩ

問題について調査する

一般的に浮動小数点数の取り扱いで生じる幾つかの可能性が思いつきましたが、これと直感で断言できるほどの確信は無く、簡単なものから可能性を排除していく事にしました。

1. 単純に浮動小数点数型の精度を上げてみる

float 固定だった浮動小数点数の型を template 化して同様にプロットを眺めてみます:

template < typename T > constexpr auto pi = (T)3.14159265358979323846264338327950288;

template < typename T >
std::tuple< T, T > SinCosC( const T angle_in_radians )
{
  T quotient = angle_in_radians * (T)0.5 / pi< T >;
  if ( angle_in_radians >= (T)0 )
    quotient = (T)( (int)( quotient + (T)0.5 ) );
  else
    quotient = (T)( (int)( quotient - (T)0.5 ) );
  T a = angle_in_radians - quotient * (T)2.0 * pi< T >;
  T s = (T)0;
  if ( a > (T)0.5 * pi< T > )
  {
    a = pi< T > - a;
    s = (T)-1;
  }
  else if ( a < (T)-0.5 * pi< T > )
  {
    a = -pi< T > - a;
    s = (T)-1;
  }
  else
    s = (T)+1;
  T p = a * a;

  // [ 1 / 2!, 1 / 3!, 1 / 4!, .., 1 / 11! ]
  constexpr T f2 = (T)1 / (T)2;
  constexpr T f3 = f2 / (T)3;
  constexpr T f4 = f3 / (T)4;
  constexpr T f5 = f4 / (T)5;
  constexpr T f6 = f5 / (T)6;
  constexpr T f7 = f6 / (T)7;
  constexpr T f8 = f7 / (T)8;
  constexpr T f9 = f8 / (T)9;
  constexpr T f10 = f9 / (T)10;
  constexpr T f11 = f10 / (T)11;
  
  return std::make_tuple
  ( a * ( (T)1 + p * ( -f3 + p * ( +f5 + p * ( -f7 + p * ( +f9 * p * ( -f11 ) ) ) ) ) )
  , s * ( (T)1 + p * ( -f2 + p * ( +f4 + p * ( -f6 + p * ( +f8 + p * ( -f10 ) ) ) ) ) )
  );
}

f:id:USAGI-WRP:20171212034734p:plain

「(　ﾟ∀ﾟ)o彡ﾟおっぱい！おっぱい！」

SinCosC の template の実引数に float （プロット: 青）, double （プロット: 橙）, long double （プロット: 灰） を与え、それぞれの浮動小数点数型の精度ごとに std::sin との差の絶対値を絵にしてみましたが、この結果からは「どうやら問題は浮動小数点数型の精度に少なくとも直接的には起因した問題ではない」という事が明瞭となりました。

ついでの蛇足調査(1/2); そもそも float vs. long double の値の誤差ってどれくらいでるものなの？

[0 .. 2π] について図示に必要十二分な分解能で float と double それぞれの値の差の絶対値がどれくらい生じるかの図も用意してみました。

f:id:USAGI-WRP:20171212040439p:plain

・・・こんなもんです・ｘ・

ついでの蛇足調査(2/2); SinCos の前半部分が無いとどうなるのか？

SinCos の実装は大きくわけて2段階の工程となります。

  1. [-π .. +π] に射影しつつ 2π * quotient + reminder を経由して、最終的に -π/2 .. +π と cos 用の符号を保存
  2. マクローリン展開に基いて必要十分な精度まで正弦と余弦を計算する

この前半部分をやらずに、直接後半のマクローリン展開へ入力された値を放り込むとどんな事が起こるのか、もののついでにグラフを作っておきました。

f:id:USAGI-WRP:20171212035803p:plain

みょーん・・・と、なってしまい 2π どころか πあたりで既に実用性がかなり怪しい精度になっています。この問題を隠蔽するために最も誤差が小さく他の象限とは対称となるだけの [-π/2 .. π/2] に角度を落としてマクローリン展開部分を計算していたわけです。

そもそもマクローリン展開ってそんな誤差がでるものなの？

でません。少なくとも数学的には。そんなわけで、疑う先はマクローリン展開の実装コードではないかと絞り込めてきました。

そもそも、入力値が π/2 の場合、数学的に正確な正弦は 1 ちょうどです。しかし、どうやら SinCosB やそれを template 化した SinCosC の実装では、入力値が π/2 のときに誤差が最大値となっている事がわかっています。なので、初期値が 0 付近の値の計算や 0 付近の値に対する誤差の計算の信頼性が云々・・・という事でも無さそうです。

ちなみに、入力値が π/2 の場合の場合の SinCosB または SinCosC の出力値は float, double, long double の何れで計算した場合も、出力値は 0.999843 となり、 vs. std::sin の差の絶対値は 0.000157 となります。

f:id:USAGI-WRP:20171212041927p:plain

これは浮動小数点数型の精度、マクローリン展開の精度の何れからも不可解な結果です。

そこで、実装の分かり易く愚直なマクローリン展開の正弦を計算するコードを書いて試してみます。

#include <iostream>
#include <iomanip>

template < typename T > constexpr auto pi = (T)3.14159265358979323846264338327950288;

/// @brief オーバーフローしない限りの任意の階数でマクローリン展開による正弦を計算
/// @tparam N マクローリン展開する階数
/// @tparam T 入力および計算と出力に用いる浮動小数点数型
/// @param a 入力角度 [rad]
/// @return 正弦値 [-]
template < std::uint8_t N, typename T >
auto sin( const T a )
{
  static_assert( N % 2 == 1 );
  static_assert( N <= 19, "factorial be overflow" );
  
  // 展開された級数を加算/減算し結果を得る変数
  T result = a;
  // 符号は項ごとに反転する
  bool is_positive = false;
  // マクローリン展開を項ごと愚直に計算
  for ( decltype( N ) n = 3; n <= N; n += 2, is_positive = ! is_positive )
  {
    // 項の分数の分子の側となる指数を逐次愚直に乗算して結果を得る変数
    T             power     = 1;
    // 項の分数の分母の側となる階乗を逐次愚直に乗算して結果を得る変数
    std::uint64_t factorial = 1;
    // 項の分子と分母それぞれを愚直に乗算を繰り返して計算
    for ( auto m = n; m; --m )
    {
      power     *= a;
      factorial *= m;
    }
    // 項の符号に基いて計算中の結果へ加算/減算し計算精度を高める
    if ( is_positive )
      result += power / (T)factorial;
    else
      result -= power / (T)factorial;
  }
  // マクローリン展開を要求された階数だけ計算した結果を返す
  return result;
}

やや丁寧すぎるくらいにコメントをソースへ入れたので文章での解説は省略します。この sin に float, double, long double の π/2 を入力して出力を眺めてみましょう。

int main()
{
  constexpr auto n = 11;
  std::cout 
    << std::fixed << std::setprecision( 32 ) << sin< n >( pi< float       > / 2 ) << '\n'
    << std::fixed << std::setprecision( 32 ) << sin< n >( pi< double      > / 2 ) << '\n'
    << std::fixed << std::setprecision( 32 ) << sin< n >( pi< long double > / 2 ) << '\n'
    ;
}

n = 11 （問題のある SinCosB などと同じマクローリン展開の階数）の結果:

0.99999988079071044921875000000000
0.99999994374105094507854119001422
0.99999994374105087037701150576297

あっさり、すっきり、精度6桁確保できていますね・ｘ・

ちなみに、 n = 13 にすると、

0.99999994039535522460937500000000
1.00000000066278027510691117640818
1.00000000066278009003360033313257

さらに桁単位で誤差が縮みます。

つまり、 SinCosB のマクローリン展開の実装に問題がある可能性がとても濃厚に疑われます🐰

SinCosB の何が問題だったのか？

次の2つのコードは同じでしょうか、また、違いがあるとすればどちらが正しいマクローリン展開でしょう。

// SinCosB のマクローリン展開の最終的な計算の実装
auto s0 = a * ( 1.0f + p * ( -f3 + p * ( +f5 + p * ( -f7 + p * ( +f9 * p * ( -f11 ) ) ) ) ) );
// クイズ出題にあたり参考とした元の UE4 FMath::SinCos での実装
auto s1 = ( ( ( ( ( ( -f11 ) * p + f9 ) * p - f7 ) * p + f5 ) * p - f3 ) * p + 1.0f ) * a;

s0: 0.99984318017959594726562500000000
s1: 0.99999988079071044921875000000000

CPP-QUIZ from Unreal 2017 では、出題の元ネタとして UE4 の FMath ライブラリーの実装に基きつつ、 UE4 についてはまったく知らない方でもほぼ純粋に C++ における実装問題として楽しめるよう、またコードも私なりに読みやすいよう、 "工夫" したつもりでした。一般に、数式でもマクローリン展開は低い階数から項を並べて書くことが多いので、ややこしい記述となる実装部位について読者にも少しでも読みやすいようにと思い、参考とした UE4 FMath ライブラリーの実装では右側が低い階数となっていた実装を「これは問題ない、同じ動作となる "はず" 」と書き換えていたのです。

よーく、よーく、眺めると、 s1 では +f9 と次の項との計算はもちろん + 演算子となっている ところが、 s0 では * 演算子となっています。 s0 と s1 を比較しやすいよう、 s1 の記述を s0 のように、つまりマクローリン展開についてよく数式で表す際に用いられるように低い階数から並べると、次のようになります。

                                                                     |--- Mistake!
auto s0 = a * ( 1.0f + p * ( -f3 + p * ( +f5 + p * ( -f7 + p * ( +f9 * p * ( -f11 ) ) ) ) ) );
auto s1 = a * ( 1.0f + p * ( -f3 + p * ( +f5 + p * ( -f7 + p * ( +f9 + p * ( -f11 ) ) ) ) ) );
                                                                     |--- CORRECT!

やれやれ・・・なんという結末の「なあんだ、そんなこと！」感。調査に昨晩少々と今朝、記事にしながら併せて90分くらい掛けてしまいました。コードの記述がややこしい実装をやむを得ずする場合には、こうしたごく単純な書き間違えによるバグを埋め込んでしまう可能性が高まります。今回の例はやむを得ず高速化したいという要求から単純ではない実装を試みる必要がありましたが、気持ちが緩み過ぎて、そうしたバグが埋め込まれてしまいやすい実装を行う上で十二分に必要な措置を講じ確実で正確な検証を行うべきところを怠った事が実質的な "バグ" だったと言えます。

修正版 SinCosB の正弦と std::sin の差の絶対値:

f:id:USAGI-WRP:20171212071323p:plain

最大でも 1.0e-6 未満に収まるようになりました😃 より具体的には入力値が 1.51163 [rad] （ ≃ 86.61 [deg] ）などで最大の誤差 1.79e-7 が観測されます。

幸い、今回は実害の無いクイズで、なおかつ異常に気づいた @nekketsuuu さんからの指摘を基に、早々にバグを発見、修正する記事をこのように書けましたが、これが実際の製品に埋め込まれていた可能性や、保守担当者が私ではなかった場合（特に若い子にこれを対処させる必要性が生じた場合など）を考えると、なかなか、危ないところでした。反省しつつ、もっとコードを、そしてメタ的（≃試験やアサーション）に安全に、検証を怠らずに、さらにメタメタ的な素養（≃意識、習慣）を強化したいと思います。

それでは、この後日談ネタも含めて CPP-QUIZ from Unreal 2017 の "楽しさ" として頂ければ幸いです。🎅メリクリ🎄

CPU: Intel が SIMD 命令の拡張にアフィン変換を追加する、という話の中身と影響する分野について

CPU Instruction Set SIMD AES Encryption Intel アフィン変換

Intel が SIMD 命令の拡張にアフィン変換を追加するらしい（参考2） との事で、 "Intel® Architecture Instruction Set Extensions and Future Features Programming Reference" （参考1） を見てきました。アフィン変換は Computer Graphics 界隈の人々が反応しやすいキーワードですが、今回の話はあまり "一般的な狭義の意味での CG 界隈" とは関係無いよ（いまのところ）という話です。

追加される（予定の） アフィン変換系の命令群

  1. GF2P8AFFINEINVQB ; Galois Field Affine Transformation Inverse （＝ガロア域アフィン逆変換）
  2. GF2P8AFFINEQB ; Galois Field Affine Transformation （＝ガロア域アフィン変換）

命令の概要

何れもガロア域 28 におけるアフィン変換の計算を SIMD レジスターを用いて行うCPU命令。 Inverse の方は 8x8 bit の行列 A 、 8-Bit ベクターの x, b について A * inv( x ) + b を計算、他方は A * x + b を計算するもの。

この計算は AES 暗号の S-box 回りの計算。もし暗号技術に興味があり、それが一体何なのかについてより詳しく理解したい方には書籍「暗号技術のすべて」（参考6）のAES暗号の解説がたいへん詳しくわかりやすいのでおすすめ。

想定される主な用途

  • AES 暗号技術（ AES 暗号の "Rijndeal S-box" まわりの計算が今回話題の GF2P8AFFINE 系命令の適用そのもの; 参考3,4,5 ）
    • Note: AES = Advanced Encryption Standard （参考5）
    • Note: Rijndeal （ラインダール; 参考3）

（一般的な狭義の意味での）CG屋さんへの影響

と、いうわけで、「アフィン変換」と聞いて反応しそうな（2次元、3次元での線形幾何を主戦場とする）CG 屋さんたちには今回は関係無いからひとまず安心して寝ましょう、というお話でした。ちなみに、 AVX のレジスターは 512-Bit なので、ここでいう狭義の CG 界隈で一般的な 32-Bit float の 4x4 行列を扱おうにもオペランドを1つロードしただけでレジスターが埋まってしまいます。 GPU には 16-Bit float の対応もありますが、それはそれで CPU はネイティブに対応していませんし、 IEEE754/binary16 相当では 10 進数で 3 桁程度の精度しかありませんから実世界での用途は限られます。 AVX2048 …みたいなものが来れば CPU で 32-Bit float のここでいう狭義の CG 屋さん向けのアフィン変換命令も乗る事もあるのかもしれませんが、たぶん、少なくとも数年単位の近い未来までの事としては、"それは GPU でやってくれ" と Intel も考えているような気がします（関係者じゃないので知らんけど😋）。

参考

CPP-QUIZ from Unreal 2017 ( part-2/2; 答え編 )

C++ UE4 Advent Calendar 2017 Quiz part-2

（この記事は前の投稿 CPP-QUIZ from Unreal 2017 ( part-2/2; 出題編 ) に対応する答え編です。）

2. こたえ

Q1. float 型の [ 0.0 .. 1.0 ] の値を uint8 型の [ 0 .. 256 ) へ写像したかった

出題のソースコードでは、 "出力が 255 となる元の値の範囲" が 0 から 254 のそれぞれに対応する範囲に対して均等とならない問題が発生する。

例えば、値がグレイスケールカラーの輝度値を表す場合に出題のソースコードを用いると、入力が 1.0 未満の場合に本来よりも僅かに明るくシフトしてしまう結果となる。グレイスケールカラーで人間が目視するだけであれば、大きな問題にはならない事も多いが、変換を繰り返したり、その値での制御を一定時間続ける装置に適用したりすると問題と成り得る事もある。

出題のソースコードと in と out の関係の一部:

in out
[ 0 / 255.f .. 1 / 255.f ) 0
[ 1 / 255.f .. 2 / 255.f ) 1
[ 2 / 255.f .. 3 / 255.f ) 2
[ 254 / 255.f .. 255 / 255.f ) 254
[ 255 / 255.f .. 255 / 255.f ] 255

修正方法:

256 未満で最大の float の数を掛けると [ 0 .. 256 ) に可能な限り均等に写像できる。

int out = in * 255.9999847412109375f;

おまけ: 255.9999847412109375f はどこから来たか？

const int32 x = 0b0'10000110'11111111111111111111111;
const float y = *(float*)&x;
std::cout << std::fixed << std::setprecision( 32 ) << y << '\n';

Q2. 意図しない整数のオーバーフローと問題の遮蔽

出題のコードでは TV で 32-Bit 以上の整数型、例えば int32 を扱うと問題が起こりうる。例えば、次のような意図しない結果が得られる:

auto x = 
  Lerp
  ( std::numeric_limits< int32 >::max()
  , std::numeric_limits< int32 >::min()
  , 1.0f
  );

x には +2,147,483,647 相当の値が期待されるが、実際には -2,147,483,648 が得られる。 b - a は -2,147,483,648 - 2,147,483,647 = -1 となり、 ratio = 1.0f と乗算され -1.0f 、 これが -2,147,483,648 と乗算されると float 型の +2,147,483,648 となるが、 return 直前の (TV) により int32 型へキャストされる。 +2,147,483,648 を int32 へキャストすると -2,147,483,648 になる。

std::cout
  << std::bitset< 32 >( (int32) +2'147'483'647 ) << ' ' << std::showpos << (int32) +2'147'483'647 << '\n'
  << std::bitset< 32 >( (int32) +2'147'483'648 ) << ' '                 << (int32) +2'147'483'648 << '\n'
  << std::bitset< 32 >( (int32) +2'147'483'649 ) << ' '                 << (int32) +2'147'483'649 << '\n'
  ;

01111111111111111111111111111111 +2147483647
10000000000000000000000000000000 -2147483648
10000000000000000000000000000001 -2147483647

この問題は TV が整数型でも int8, uint8, int16, uint16 の場合には表面化しない。 a, b が int よりも狭いビット幅の整数型の場合に b - a は signed int ないし unsigned int で計算され、結果もその計算に使われた型のままとなる。

int16 a = +32'767;
int16 b = -32'768;
auto c = b - a;
std::cout << typeid( decltype( c ) ).name() << ' ' << std::to_string( c );
s s i -65535

b - a が int16 ではなく int32 で計算され、結果も int32 となるので -65535 を余裕をもって扱えてしまう。結果、 int 未満のビット幅の整数型を Lerp の TV で扱う限りは問題が表面化せず、一見すると任意の整数型に対して意図通りに動作するように見えてしまう。

もし、 Lerp に単体試験を網羅的に行うよう書いていたとしても、計算時間と "整数型" の概念を漠然と考えて、 int8 と uint8、あるいは int16 と uint16 で試験を実装してしまっていたなら、この問題はその単体試験が成功してしまうために何かが起きた際に原因を探すのが少し難しくなる事もあるかもしれない。

この問題が起こらない Lerp の実装例は次の通り:

  return (TV)( a * ( 1 - ratio ) + b * ratio );

数学的には等価な ( a + ratio * ( b - a ) ) と ( a * ( 1 - ratio ) + b * ratio ) も現実の計算機では等価とならない事もある。

Q3. 浮動小数点数型

IsSameAltitude の return では宇宙船Aと宇宙船Bの人工惑星Oからのそれぞれの高度を計算し、最終的に == で float 値を比較している。この処理では float 型の値が完全に一致する必要があるが、ストーリーのニーズからは float 値としての完全な一致ではなく、ゲームのプレイヤーが認識する高度の数値として感覚的に妥当な一致が必要です。

出題の実装ではミニマップにはほとんど何も表示されないか、ほんの一瞬（たいていのゲームではそれは 16 ms や 33 ms くらいの視認できるかどうかわからないくらいに）だけ、極稀に何か表示され…た気がする…、そんなような現実が発生し、ミニマップにまともに同じ高度の宇宙船が映らないというバグチケットが（おそらく）上がる事になるでしょう。

この系は float で十分に表現可能という条件から、宇宙船の高度は10進数にして高々7桁に収まるよう扱われます。 73.1 km のように。

しかし、 float の値としては、 例えソースコード上で 73.1f と書いたとしても、 std::cout << 73.1f; は 73.1 と表示されるとしても、実際の値は 73.099'998'474'121'093'750 相当となります。一般的な x64 アーキテクチャーやそれと互換の処理系での float は IEEE754/binary32 なので。

これはもちろん FVector の x, y, z それぞれについても、また operator- の結果も、 Length の計算の乗算や加算や std::sqrt の結果も全てが計算機にとってはこのバイナリー表現の世界が現実となります。

よって、 例え宇宙船Aと宇宙船Bの高度がプリントエフデバッグやログ出力などで確認すると同じ 73.1 と出力される状況でも、 IsSameAltitude は false を返す意図せず多発、というよりほとんどの状況となる。

float x = 73.1f;
float y = 73.1f + 4.0e-6f;
std::cout
  << x << '\n'
  << y << '\n' 
  << std::fixed << std::setprecision(32)
  << std::bitset< 32 >( *(int32*)&x ) << ' ' << x << '\n'
  << std::bitset< 32 >( *(int32*)&y ) << ' ' << y << '\n'
  ;

1.41421
73.1
73.1
01000010100100100011001100110011 73.09999847412109375000000000000000
01000010100100100011001100110100 73.10000610351562500000000000000000

この点を意識せずにデバッグすると原因の特定に少しだけ手間取るかもしれない。あるいは知識として把握していても、うっかり == で float の比較を書いてしまい予期しないバグを発生させてしまう事は新人や極度に疲弊した状態のプログラマーにはしばしば生じる事があるし、コンパイラーもこの意図は汲んでエラーや警告を出してくれるほど今のところは親切でないし、一般的な処理系の float は IEEE754/binary32 のままです。

この問題の対応としては、 IsNearlyEqual を用意し、また、 IsSameAltitude には許容誤差を明示的に実引数として渡せるようにする事です:

constexpr float default_error_tolerance = 1.0e-3f;

template < typename T >
bool IsNearlyEqual( const T a, const T b, const T error_tolerance = (T)default_error_tolerance )
{
  static_assert( std::is_floating_point< T >::value, "" );
  return std::abs( a - b ) <= error_tolerance;
}

bool IsSameAltitude
( const FVector& a
, const FVector& b
, const FVector& o
, const float error_tolerance = default_error_tolerance
)
{
  auto o_to_a = a - o;
  auto o_to_b = b - o;
  auto altitude_of_a = o_to_a.Length();
  auto altitude_of_b = o_to_b.Length();
  return IsNearlyEqual( altitude_of_a, altitude_of_b, error_tolerance );
}

Q4. 遅すぎた 2 の指数 [ 1, 2, 4, 8, 16, 32, .. ] の判定

template < typename T >
bool IsPowerOfTwo( const T in )
{
  static_assert( std::is_integral< T >::value, "" );
  return in == 0 ? false : ( ( in & ( in - 1 ) ) == 0 );
}

この実装は執筆時の wandbox で出題時と同様に簡易的に計測したところ Optimization=OFF で 5,041,452 #/sec （出題実装比 1.89 倍高速）、 Optimization=ON で 8,007,129 #/sec （出題実装比 1.94 倍高速）で動作した。

Q5. 正弦と余弦も速くしたい

象限を判定し最も精度良く計算可能な低角度域へシフトしつつマクローリン展開を必要な有効数字が十分に得られる程度計算する。

#define PI 3.14159265358979f
std::tuple< float, float > SinCosB( const float angle_in_radians )
{
  float quotient = angle_in_radians * 0.5f / PI;
  if ( angle_in_radians >= 0.0f )
    quotient = (float)( (int)( quotient + 0.5f ) );
  else
    quotient = (float)( (int)( quotient - 0.5f ) );
  float a = angle_in_radians - quotient * 2.0 * PI;
  float s = 0.0f;
  if ( a > 0.5f * PI )
  {
    a = PI - a;
    s = -1.0f;
  }
  else if ( a < -0.5f * PI )
  {
    a = -PI - a;
    s = -1.0f;
  }
  else
    s = +1.0f;
  float p = a * a;
  // [ 1 / 2!, 1 / 3!, 1 / 4!, .., 1 / 11! ]
  constexpr float f2 = 1.0f / 2.0f;
  constexpr float f3 = f2 / 3.0f;
  constexpr float f4 = f3 / 4.0f;
  constexpr float f5 = f4 / 5.0f;
  constexpr float f6 = f5 / 6.0f;
  constexpr float f7 = f6 / 7.0f;
  constexpr float f8 = f7 / 8.0f;
  constexpr float f9 = f8 / 9.0f;
  constexpr float f10 = f9 / 10.0f;
  constexpr float f11 = f10 / 11.0f;
  return std::make_tuple
  ( a * ( +1.0f + p * ( -f3 + p * ( +f5 + p * ( -f7 + p * ( +f9 * p * ( -f11 ) ) ) ) ) )
  , s * ( 1.0f + p * ( -f2 + p * ( +f4 + p * ( -f6 + p * ( +f8 + p * ( -f10  ) ) ) ) ) )
  );
}

この実装は執筆時の wandbox で出題時と同様に簡易的に計測したところ Optimization=OFF で 2,898,145 #/sec （出題実装比 1.06 倍高速）、 Optimization=ON で 5,914,322 #/sec （出題実装比 1.45 倍高速）で動作した。

（追記: 2018-12-12）

↑めでたしめでたし、と思われたが、実は↑の「こたえ」のコードにも新たなバグが埋め込まれてしまっていました。

CPP-QUIZ Q5 のこたえ、マクローリン展開による sin/cos の高速化に潜んでいた大きな誤差を生じるバグ - C++ ときどき ごはん、わりとてぃーぶれいく☆

と、いうわけで、改めまして、正しくは、

#define PI 3.14159265358979f
std::tuple< float, float > SinCosB( const float angle_in_radians )
{
  float quotient = angle_in_radians * 0.5f / PI;
  if ( angle_in_radians >= 0.0f )
    quotient = (float)( (int)( quotient + 0.5f ) );
  else
    quotient = (float)( (int)( quotient - 0.5f ) );
  float a = angle_in_radians - quotient * 2.0 * PI;
  float s = 0.0f;
  if ( a > 0.5f * PI )
  {
    a = PI - a;
    s = -1.0f;
  }
  else if ( a < -0.5f * PI )
  {
    a = -PI - a;
    s = -1.0f;
  }
  else
    s = +1.0f;
  float p = a * a;
  // [ 1 / 2!, 1 / 3!, 1 / 4!, .., 1 / 11! ]
  constexpr float f2 = 1.0f / 2.0f;
  constexpr float f3 = f2 / 3.0f;
  constexpr float f4 = f3 / 4.0f;
  constexpr float f5 = f4 / 5.0f;
  constexpr float f6 = f5 / 6.0f;
  constexpr float f7 = f6 / 7.0f;
  constexpr float f8 = f7 / 8.0f;
  constexpr float f9 = f8 / 9.0f;
  constexpr float f10 = f9 / 10.0f;
  constexpr float f11 = f10 / 11.0f;
  return std::make_tuple
  ( a * ( +1.0f + p * ( -f3 + p * ( +f5 + p * ( -f7 + p * ( +f9 + p * ( -f11 ) ) ) ) ) )
  , s * ( 1.0f + p * ( -f2 + p * ( +f4 + p * ( -f6 + p * ( +f8 + p * ( -f10  ) ) ) ) ) )
  );
}

となります😃 こちらも @nekketsuuu さんからのご指摘が基でバグを発見できました。ありがとうございます😃

Q6. ニアリーイコール、再び

出題の実装には2つの問題が潜んでいる。

  1. a=π/2（ =90° ）, b=2π+π/2 （ =360°+90°=450°） に対して return が false となるが、一般的には何周多く回っても結果的に示す角度は等価なため、本来は true が返ると期待される。
  2. a=0（ =0° ）, b=2π - 1.0e-4f （ =360°-1.0e-4=359.99 ）は標準の許容誤差 e=1.0e-3f 範囲内の角度で周回もしていないが abs(a-b) は abs( 0 - (2π-1.0e-4f) ) となり、 -2π+1.0e-4f < e は false と評価されてしまう。本来は true が返ると期待される。

対応として、 a と b の角度の差を正しく評価する FindDeltaAngleRadians を定義する:

#define PI 3.14159265358979f
/// 弧度法単位の角度の差を計算
/// @param a angle of A in radians
/// @param b angle of B in radians
/// @return a と b の角度の差
float FindDeltaAngleInRadians( const float a, const float b )
{
  auto d = b - a;
  
  if ( ! std::isfinite( d ) )
    return d;
  
  while ( d > PI )
    d -= 2 * PI;
  while ( d < -PI )
    d += 2 * PI;
  
  return d;
}

それから、 IsNearlyEqualAngleInRadians の角度の差の計算に FindDeltaAngleInRadians を用いる:

bool IsNearlyEqualAngleInRadians( const float a, const float b, const float e = 1.0e-3f )
{
  return std::abs( FindDeltaAngleInRadians( a, b ) ) < e;
}

(2017-12-06 追記)

クイズの作成時に題意としては考慮していませんでしたが、後日「こんな答えも含まれるのでは？」と鋭いご指摘を頂き、確かにこのクイズの他の設問で扱っているような出題と答えからするとそれもクイズの答えの1つとして記述した方が自然と私も思い、頂いたご指摘の Tweet を引用する形で追記・紹介いたします😃

ぴんと来ない方も Tweet に添付して頂いた wandbox で状況を確認できるコード を見ると、たいへん分かり易いと思います。ありがとうございます。

Q7. 人間が読みやすい "数値" にしたかった

出題の実装では次の3つの問題が発生する。

  1. int32 型の値は 999,999,999 を超える値も取り得る。例えば 1234567890 をこの関数の実引数として与えると、出力は 1234,567,890 となり期待される桁区切りが足りずに、奇妙で読み難い、意図しない出力が得られる。
  2. int32 型の値は負の値を取り得る。例えば -123456789 を与えると 出力は -123456789 となり桁区切りがまったく行われず、意図しない出力が得られる。
  3. 世界は広い。日本やアメリカ合衆国の文化圏では数値の桁区切りが3桁ごとに , （カンマ）で行われる慣例が一般化しているが、例えばドイツやイタリアでは . （ドット）を桁区切りに使い、 , を小数点に使う。フランスやロシアでは （空白文字）を桁区切りに使い、 , を小数点に使う。スイスでは ' （シングルクォート）を桁区切りに使い、 , を小数点に使う。 int32 は整数型なので小数点の考慮は必要無いが、少なくとも製品が使用される文化圏を限定できない場合には桁区切り文字は , とは限らない事を考慮する必要がある。

(1) int32 型の値は [ -2,147,483,648 .. +2,147,483,647 ] を取り得るので、桁区切りは3つ目まで考慮した実装とする必要がある。

// 出題の実装に倣うなら、3回目の桁区切りを追加すれば
// (1) については意図通りの結果が得られるようになる。
  if ( in > 999'999'999 )
  {
    out = ',' + buffer.substr( buffer.size() - 3, 3 ) + out;
    buffer.resize( buffer.size() - 3 );
  }

(2) は負の値も桁区切りの判定を正常に行えるよう修正する必要がある。

// 出題の実装を最小限の改修で済ませるならば if の条件に負の値の判定も || で盛り込めば 
// (2) については意図通りの結果が得られるようになる。
  if ( in > 999 || in < -999 )

(3) は , を任意の文字へ変更可能に対応する。

std::string FormatIntToHumanReadable( const int32 in, const char splitter = ',' )
{
  // 中略 //
    out = splitter + buffer.substr( buffer.size() - 3, 3 );
  // 後略 //

(1), (2), (3) の修正を加え、ついでに if の3連続を while 1つに整理すると次の実装となる:

std::string FormatIntToHumanReadable( const int32 in, const char splitter = ',' )
{
  auto buffer = std::to_string( in );
  std::string out;

  while ( buffer.size() > 3 && buffer[ buffer.size() - 4 ] != '-' )
  {
    out = splitter + buffer.substr( buffer.size() - 3, 3 ) + out;
    buffer.resize( buffer.size() - 3 );
  }

  out = buffer + out;

  return out;
}

なお、このコードは "文字列処理" としては分かり易い側面もありますが、 C++ の実装としてはやや "暢気" な実装です。また、そもそも std::ostream へロケールを設定して << するだけでよしなに桁区切りしてくれるとか、そういった指摘もあるかと思います。それらは出題の「この実装ではどのような問題が起こり得るだろうか」の題意からは外れますので、興味に応じてエクストラにお楽しみになられたら良いと思います。

Q8. 整数型、再びトラブる

同じ原因に起因するバグが2箇所に潜んでいる。

1 つは、 float intensity = std::abs( in ) の結果は常に正の数とはならない。例えば、 T=int32, in=std::numeric_limits<int32>::min() が関数へ与えられた場合、 intensity は -2147483648.0f となる。 std::abs( in ) は int 型以上のビット幅の符号付きの整数型に対して、その最小値が与えられた場合、プログラマーが数学的に意図する絶対値は返せず、結果的には最小値がそのまま返ってくる。これを float 型へ変換したものが intensity へ保持され、結果、負の値を T 型の最大値である正の値で除算した値が return され、意図しない -1 が得られてしまう事になる。

この関数の仕様は return が [ 0 .. 1 ] なので、 -1 が返る想定をしない何らかの処理がとんでもない動作を引き起こす可能性がある。

もう 1 つは、 intensity / std::numeric_limits< T >::max() の結果が T 型の最大値と最小値の数学的な意味での絶対値が 1 だけ違うために 0 を中心として符号を除去した intensity を T 型の最大値で除算してしまうと、元の値が負の値だった場合に意図した意図した値域の写像とならない。例えば、 T=int8, in=-128 の場合、本来は 1.0f が期待されるが、この出題の実装では 1.007874011993408203125f となる。

この関数の実装上の問題は、以上の2点が起こり得る事。何れも符号付きの整数型の最小値に起因する。

また、この関数の仕様についても1点明確ではない問題が潜んでいる。 T が符号付き整数型の場合に、負の強度の最大値は T 型の 最小値 として T型の値の正、負それぞれの全域を強度とするのか、負の値については 最小値 + 1 までを正常値として正、負の値は符号が異なっても同じ強度とするのかが明確でない。

// 正は正、負は負でそれぞれの数学的な意味での絶対値が最大の値を最大の強度とする場合の修正例
template < typename T >
float GetIntensityToUNormFloat( const T in )
{
  return in >= 0
    ? in / (float)std::numeric_limits< T >::max()
    : in / (float)std::numeric_limits< T >::min()
    ;
}

// 正も負も数学的な意味での絶対値が同じ値は同じ強度とし、
// 符号付き整数型の最小値は不正値とする場合の修正例
template < typename T >
float GetIntensityToUNormFloat( const T in )
{
  check( std::is_unsigned< T >::value || in > std::numeric_limits< T >::min() );
  return std::abs( in / (float)std::numeric_limits< T >::max() );
}

Q9. G.C.D.

5 つの実装例と簡易的な速度評価結果を紹介します。

(1) はじめに Unreal Engine 4.18 の実装を出題に併せて調整した実装:

template < typename T >
T GreatestCommonDivisor( T a, T b )
{
  static_assert( std::is_integral< T >::value, "" );
  check( a >= 0 )
  check( b >= 0 )
  while ( b != 0 )
  {
    T t = b;
    b = a % b;
    a = t;
  }
  return a;
}

(2) while タイプの亜種:

template < typename T >
T GreatestCommonDivisor( T a, T b )
{
  static_assert( std::is_integral< T >::value, "" );
  check( a >= 0 )
  check( b >= 0 )
  if ( b )
    while ( ( a %= b ) && ( b %= a ) );
  return ( a + b );
}

(3) std::function recursive タイプ:

template < typename T >
T GreatestCommonDivisor( T a, T b )
{
  static_assert( std::is_integral< T >::value, "" );
  check( a >= 0 )
  check( b >= 0 )
  std::function< T( T, T ) > f;
  f = [&f]( auto a, auto b ){ return ( b != 0 ) ? f( b, a % b ) : a; };
  return f( a, b );
}

(4) function recursive タイプ:

template < typename T >
T GreatestCommonDivisor_Impl( T a, T b )
{ return ( b != 0 ) ? GreatestCommonDivisor_Impl( b, a % b ) : a; }

template < typename T >
T GreatestCommonDivisor( T a, T b )
{
  static_assert( std::is_integral< T >::value, "" );
  check( a >= 0 )
  check( b >= 0 )
  return GreatestCommonDivisor_Impl( a, b );
}

(5) C++17er:

template < typename T >
T GreatestCommonDivisor( T a, T b )
{
  static_assert( std::is_integral< T >::value, "" );
  check( a >= 0 )
  check( b >= 0 )
  // std::gcd がツールチェインごとにどのようなソースで実装されているかはさておき
  return std::gcd( a, b );
}

それぞれの簡易的な実行速度評価結果:

実装パターン Optimization #/sec
(1) UE4 while OFF 1,137,116
(1) UE4 while ON 1,495,536
(2) while 亜種 OFF 1,121,166
(2) while 亜種 ON 1,503,565
(3) std::function recursive OFF 313,537
(3) std::function recursive ON 1,236,848
(4) function recursive OFF 954,043
(4) function recursive ON 1,534,016
(5) C++17er OFF 960,103
(5) C++17er ON 1,481,497

Q10. L.C.M.

2 つの実装例と簡易的な速度評価結果を紹介します。

(1) はじめに Unreal Engine 4.18 の実装を出題に併せて調整した実装:

template < typename T >
T LeastCommonMultiplier( T a, T b )
{
  static_assert( std::is_integral< T >::value, "" );
  check( a >= 0 )
  check( b >= 0 )
  // Q9 G.C.D. の実装を使う
  T gcd = GreatestCommonDivisor( a, b );
  return gcd == 0 ? 0 : ( a / gcd ) * b;
}

(2) C++17er:

template < typename T >
T LeastCommonMultiplier( T a, T b )
{
  static_assert( std::is_integral< T >::value, "" );
  check( a >= 0 )
  check( b >= 0 )
  // std::gcd がツールチェインごとにどのようなソースで実装されているかはさておき
  return std::lcd( a, b );
}
実装パターン Optimization #/sec
(1) UE4 a / GCD * b OFF 1,126,620
(1) UE4 a / GCD * b ON 1,456,371
(2) C++17er OFF 889,107
(2) C++17er ON 1,418,852

おまけ: G.C.D. & L.C.M. の wandbox での簡易的な実行速度評価に使用したコード

G.C.D., L.C.M. 以外でも概ねは同様のコードで簡易的な実行速度評価を行っています。

#include <iostream>
#include <limits>
#include <type_traits>
#include <chrono>
#include <random>
#include <array>
#include <algorithm>
#include <cassert>
#define check(X) { assert(X); }
using int8 = std::int8_t;
using uint8 = std::uint8_t;
using int16 = std::int16_t;
using uint16 = std::uint16_t;
using int32 = std::int32_t;
using uint32 = std::uint32_t;
using int64 = std::int64_t;
using uint64 = std::uint64_t;

// Q9 のこたえを入れた header file
#include "GCD.h"
// Q10 のこたえを入れた header file
#include "LCM.h"

int main()
{
  std::array< uint64, 1024 > numbers;
  std::mt19937_64 rng( 0 );
  std::generate( numbers.begin(), numbers.end(), rng );
  double x = 0.0f;
  size_t count = 0;
  auto ta = std::chrono::steady_clock::now();
  while ( std::chrono::steady_clock::now() <= ta + std::chrono::seconds( 10 ) )
  {
    auto a = numbers[   count % numbers.size() ];
    auto b = numbers[ ++count % numbers.size() ];
    x += GreatestCommonDivisor( a, b );
    //x += LeastCommonMultiplier( a, b );
  }
  std::cout << ( count / 10 ) << ' ' << x << '\n';
}

CPP-QUIZ from Unreal 2017 ( part-1/2; 出題編 )

C++ UE4 Advent Calendar 2017 Quiz part-1

0. はじめに

この記事は C++ Advent Calendar 2017 の DAY 1 に寄稿したものです。😃

初日は楽しい記事が良いだろうと考え、クイズ形式で C++ コードを楽しむコンセプトで記事を書くことにしました。今年は UE4 の C++ 実装を眺める時間が業務でも多くなりましたので、 Unreal Engine のソースコードを基に C++ の Tips などをクイズ形式で紹介します。

Unreal Engine について

Unreal Engine は Epic Games が現在は OSS として github で公開しながら開発を続けている C++ の実装を基にしたゲームエンジン、フレームワークです。執筆現在の現行版は 4.18 です。この記事は 4.18 のソースコードを基に執筆します。

  1. https://github.com/EpicGames/UnrealEngine/tree/4.18
  2. https://github.com/EpicGames/UnrealEngine/tree/4.18/Engine/Source/Runtime

実行環境について

Wandbox にて gcc-7.2.0 を Warning=ON, Optimization=OFF, Verbose=OFF, Don't Use Boost, Sprout=OFF, MessagePack=OFF, C++14, -pedantic-errors, Compiler options="" 設定を基本の実行環境とします。

  1. https://wandbox.org/

また、この記事の内容は一般的な x64 アーキテクチャーの PC や互換性のある処理系を対象の範囲とします。これは、例えば float は IEEE754/binary32 を前提とする事を意味します。

出題について

Unreal Engine の実装を基に問題を作成していますが、 Unreal Engine には依存しない C++ の問題となるよう調整しています。また、本記事の問題はあくまでも QUIZ として楽しめるよう工夫したもので、問題に登場するバグが実際の Unreal Engine のソースコードでバグとして対処されないまま埋め込まれているという事ではありません。

また、問題は C++ のコードを例示して出題していますが、 C++ の言語仕様に起因するクイズを中心とした C++ Quiz とはことなり、本記事ではもっと緩く C++ 以外でも起こり得る問題を広く扱います。

非常勤講師をしていた頃を思い出して、学生へ講座のはじまりに遊びを兼ねて出題するような気持ちで作りますので、 C++ 初心者、学生さんに楽しんで貰えれば嬉しく思います。

記法について

  1. 文章中で template 仮引数を一般に詳細に明記せずとも意図が通じると思われる範囲内で std::vector<T> のように略記する事があります。
  2. 文章中で値域を [ 0.0 .. 1.0 ] のように表記する場合があります。端の括弧は端の値も含まれる場合には [ または ] を用い、 端の値が含まれない場合には ( または ) を用います。また、値の間に .. があれば明示された値で挟まれた任意の値を取り得る事を意味し、 2つ以上数値が , で区切られて続いていれば , で区切られた間隔で連続する事を意味し、 .. の前後に具体的な数値が無い場合には文脈上の最小値または最大値、もしくは理論上の -∞ または +∞ へ続く意図です。
  3. 文章中では変数の値などの数値に , や + を加えて読みやすく表現する場合があります。
  4. 文章中では C++ コードとしてではなく一般的な数式の表現として a=2π+π/2 のような表現をする場合があります。
  5. uint8, int32 など UE4 で定義される型で、一般にその型名から定義が明白と考えられる型については特に解説なく用います。
  6. ソースコード中に UE4 由来の check() マクロが登場する事があります。これは <cassert> で使用可能となる assert() マクロを #define check(X) { assert(X); } と薄くラップしたものと同様と考えて下さい。簡易的な試験として括弧の中の式が実行時に評価され、 false の場合にはプログラムの動作が停止し問題が検出される一般的なアサーションとして用います。

こたえについて

答えが見えてしまうとクイズとして楽しみ難い方も多いと思います。そこで、クイズに対する著者が想定したこたえはこの記事に続けて投稿する別の記事として掲載し、この記事のおわりからリンクする事にします。

また、「ぐぐ」れば答えがすぐに見つかる問題もありますが、「クイズ」を楽しみたい方は答えがすぐに思い浮かばない問題にも、しばらくは自分の既存の知識と思考、それから wandbox でコード片を試すなどしてできるだけ答えを "現時点での自力" で見出そうとするとすぐにググってしまうよりも楽しく、また分からなかった問題についても知識として身につく事も増えるかもしれません。

もくじ

  1. float 型の [ 0.0 .. 1.0 ] の値を uint8 型の [ 0 .. 256 ) へ写像したかった
  2. 意図しない整数のオーバーフローと問題の遮蔽
  3. 浮動小数点数型
  4. 遅すぎた 2 の指数 [ 1, 2, 4, 8, 16, 32, .. ] の判定
  5. 正弦と余弦も速くしたい
  6. ニアリーイコール、再び
  7. 人間が読みやすい "数値" にしたかった
  8. 整数型、再びトラブる
  9. G.C.D.
  10. L.C.M.

1. CPP-QUIZ from Unreal

Q1. float 型の [ 0.0 .. 1.0 ] の値を uint8 型の [ 0 .. 256 ) へ写像したかった

次の実装にはバグが潜んでいる。どのようなバグか。

/// float 型の [ 0.0 .. 1.0 ] の値を uint8 型の [ 0 .. 256 ) へ写像
/// @in [ 0.0 .. 1.0 ]
/// @out [ 0 .. 256 )
uint8 Quantize8UnsignedByte( float in )
{
  int out = in * 255;
  
  check( out >=   0 );
  check( out <= 255 );
  
  return out;
}

Hint: この方法で写像されて得られる uint8 型の 0 と 255 は巾筒な "幅" に写像されたものだろうか。

Q2. 意図しない整数のオーバーフローと問題の遮蔽

次の実装にはバグが潜んでいる。どのようなバグか。

/// [ 0 .. 1 ] の ratio を [ a .. b ] へ写像
/// @tparam TV a, b, return の型
/// @tparam TR ratio の型
/// @param ratio [ 0 .. 1 ]
/// @param return [ a .. b ]
template < typename TV, typename TR >
TV Lerp( const TV a, const TV b, const TR ratio )
{
  static_assert( std::is_arithmetic_v< TV > , "" )
  static_assert( std::is_arithmetic_v< TR > , "" )
  check( ratio >= 0 );
  check( ratio <= 1 );
  return (TV)( a + ratio * ( b - a ) );
}

Hint: TV が整数型の場合も意図した結果を得られるだろうか？ uint8, int8, uint16, int16, ...

Q3. 浮動小数点数型

宇宙に浮かぶ天体としては小ぶりだがそこそこの重力のある人工の惑星の上を宇宙船が飛ぶゲームを作っているとする。この天体は十分に小さく、考慮すべき宇宙空間は float 型で問題無く扱える範囲内とする。

同じ高度に居る宇宙船同士はミニマップ（画面上に表示される小さな地図）に表示したい。そこで次の実装を行ったとする。

恐らくこれは前提のストーリーを考慮すれば意図通りの動作をせずバグチケットが上がる事になる。どのような問題が発生するだろうか。

/// ある座標を中心とした球面軌道上に浮かぶ2つの物体が同じ高度に居るか判定
/// @param a 位置 o を中心とする系に浮かぶ宇宙船 A の位置
/// @param b 位置 o を中心とする系に浮かぶ宇宙船 B の位置
/// @param o a, b が中心とする人工惑星 O の中心位置
/// @return true: 同じ高度にいる
bool IsSameAltitude( const FVector& a, const FVector& b, const FVector& o )
{
  auto o_to_a = a - o;
  auto o_to_b = b - o;
  auto altitude_of_a = o_to_a.Length();
  auto altitude_of_b = o_to_b.Length();
  return altitude_of_a == altitude_of_b;
}

但し、 FVector 型は次の通り:

// Note: 実際の UE4 の FVector 型はもっと多機能だが
//       さしあたり出題に必要最小限を定義する。
/// 3 次元の直交座標表現用のベクター型
struct FVector
{ float x = 0, y = 0, z = 0;
  float LengthSquared() const
  { return x * x + y * y + z * z; }
  FVector operator-( const FVector& t ) const
  { return FVector{ x - t.x, y - t.y, z - t.z }; }
};

Hint: IEEE754/binary32

Q4. 遅すぎた 2 の指数 [ 1, 2, 4, 8, 16, 32, .. ] の判定

次の実装が遅すぎて悲しみを覚えた。もっと高速に処理するためにはどのような実装を施せば良いだろうか。

/// 与えられた整数型の値が 2 の指数か判定する
/// @tparam T 整数型
/// @param in 判定対象の値
/// @return true: 与えられた整数型の値は 2 の指数である
template < typename T >
bool IsPowerOfTwo( const T in )
{
  static_assert( std::is_integral< T >::value, "" );
  return std::pow( (T)2, (T)std::log2( in ) ) == in;
}

なお、執筆時点の wandbox で簡易的に測定したところ、この実装は、 Optimization=OFF で 2,659,708 #/sec 、 Optimization=ON で 4,122,557 #/sec 程度で動作した。

Note: この記事はクイズであり、バグ探しではないのでこういう出題もある。

Q5. 正弦と余弦も速くしたい

もっと速くしたい。実用上、正弦と余弦として理論的に正しく10進数で6桁程度の精度があれば std::sin, std::cos と厳密に数値が一致しなくて構わない。どうにかならないだろうか。

/// 正弦と余弦を取得
/// @param angle_in_radians 弧度法単位の角度
/// @return ｛正弦、余弦｝
std::tuple< float, float > SinCos( const float angle_in_radians )
{
  return std::make_tuple( std::sin( angle_in_radians ), std::cos( angle_in_radians ) );
}

なお、執筆時点の wandbox で簡易的に測定したところ、この実装は、 Optimization=OFF で 2,726,719 #/sec 、 Optimization=ON で 4,148,229 #/sec 程度で動作した。

Hint: 正弦、余弦の数学的特性

Q6. ニアリーイコール、再び

次の実装にはバグが潜んでいる。どのようなバグか。

/// 弧度法単位の角度の差が許容誤差以下か判定
/// @param a angle of A in radians
/// @param b angle of B in radians
/// @param e error_tolerance; default = 1.0e-3f
/// @return true: a と b の角度の差は許容誤差以下である
bool IsNearlyEqualAngleInRadians( const float a, const float b, const float e = 1.0e-3f )
{
  return std::abs( a - b ) < e;
}

Hint: 問題が簡単過ぎて目が回ってきた。

Q7. 人間が読みやすい "数値" にしたかった

次のパワフルな実装を新人くんがしてくれた、とする。先輩であるあなたにはこのコードのマージを躊躇う理由が思い当たる。この実装ではどのような問題が起こり得るだろうか。

/// int32 型の整数値を人間が読みやすい桁区切りした文字列へ変換
/// @param in 数値
/// @return 数値を桁区切した文字列
std::string FormatIntToHumanReadable( const int32 in )
{
  auto buffer = std::to_string( in );
  std::string out;

  if ( in > 999 )
  {
    out = ',' + buffer.substr( buffer.size() - 3, 3 );
    buffer.resize( buffer.size() - 3 );
  }

  if ( in > 999999 )
  {
    out = ',' + buffer.substr( buffer.size() - 3, 3 ) + out;
    buffer.resize( buffer.size() - 3 );
  }

  out = buffer + out;

  return out;
}

実装してくれた新人くんの PC の画面を見たらこのコードの実装を試験したであろうコード片が見えた:

int main()
{
  std::cout << FormatIntToHumanReadable( 123456789 ) << "\n";
}

123,456,789

Hint: 実装が拙い、遅い、などはさておき、もっと致命的な問題が少なくとも2つ、あるいは3つは発生する可能性がある。

Q8. 整数型、再びトラブる

次の実装にはバグが潜んでいる。どのようなバグか。

/// 整数型の絶対値を強度として float 型の unorm 値へ変換
/// @tparam T 整数型
/// @param in 入力値
/// @return [ 0 .. 1 ] の強度値
template < typename T >
float GetIntensityToUNormFloat( const T in )
{
  float intensity = std::abs( in );
  return intensity / std::numeric_limits< T >::max();
}

Hint: 関数の各行に少なくとも1つ以上の問題が潜んでいる。

Q9. G.C.D.

新人くんが唸っている。助けてあげよう。

/// 最大公約数
/// @param a >= 0 の整数
/// @param b >= 0 の整数
/// @return a, b の最大公約数
template < typename T >
T GreatestCommonDivisor( T a, T b )
{
  static_assert( std::is_integral< T >::value, "" );
  check( a >= 0 )
  check( b >= 0 )
  // 整数型 `T` の2つの値 `a`, `b` の
  // 最大公約数（= "Greatest Common Divisor" ）を計算するアルゴリズムを実装したい
  // 但し、できるだけ高速に動作させたい
}

Q10. L.C.M.

また、新人くんが唸っている。助けてあげよう。

/// 最小公倍数
/// @param a >= 0 の整数
/// @param b >= 0 の整数
/// @return a, b の最小公倍数
/// @notice 結果のオーバーフローは考慮しない
template < typename T >
T LeastCommonMultiplier( T a, T b )
{
  static_assert( std::is_integral< T >::value, "" );
  check( a >= 0 )
  check( b >= 0 )
  // 整数型 `T` の2つの値 `a`, `b` の
  // 最小公倍数（= "Least Common Multiplier" ）を計算するアルゴリズムを実装したい
  // 但し、できるだけ高速に動作させたい
}

答え

Real Unreal Engine C++ 2017-12 (part-5/5)

C++ UE4 Advent Calendar 2017 part-5

（はてなブログの記事あたりの容量制限のため前の部分 §1.10. までは前の記事でどうぞ→Real Unreal Engine C++ 2017-12 (part-4/5) - C++ ときどき ごはん、わりとてぃーぶれいく☆）

1.11. UE4/C++ における入門的な「スレッド」ライブラリーの std 互換性

std UE4
promise TPromise
future TFuture
thread FRunnableThread

PRIMISE-FUTURE-THERAD の std と UE4 の 比較は以前書いた記事がちょうどこのセクションに相当する。

本節ではこれを基にそれぞれを項として整理する。繋げるとどうなるかは上記の記事を参照されたい。

1.11.1. TPromise<T> と std::promise<T>

promise の扱いについては std と主な使い方についてはメンバー関数名も snake か Camel か程度の違いなので std 慣れした C++er が UE4 版の実装を使おうとして混乱する事は無い。

// std
#include <future>
void std_promise()
{
  std::promise< int > p;
  auto f = p.get_future();
  p.set_value( 123 );
}
// UE4
#include "Runtime/Core/Public/Async/Future.h"
void ue4_promise()
{
  TPromise< int > p;
  auto f = p.GetFuture();
  p.SetValue( 123 );
}

1.11.2. TFuture<T> と std::future<T>

// std
#include <future>
void std_future( std::future< int >& f )
{
  // せっかくなので参考記事には無い処理完了をブロッキングせずに待つパターンの
  // 基礎的な実装要素を加えて紹介する。
  if ( f.wait_for( std::chrono::seconds( 0 ) ) == std::future_status::ready )
    auto result = f.get();
}
// UE4
#include "Runtime/Core/Public/Async/Future.h"
void ue4_future( TFuture< int >& f )
{
  if ( f.IsReady() )
    auto result = f.Get();
}

wait_for, wait_until ほど高機能ではないが、一般的に IsReady だけでも事足りる。

1.11.3. FRunnableThread と std::thread

// std
void std_thread( std::promise< int >&& p )
{
  auto t = thread( [ =, p = move(p) ] () mutable { p.set_value( 123 ); } );
  t.join(); // or detach()
}
// UE4
void ue4_thread( TPromise< int >&& p )
{
  struct r_type: public FRunnable
  { TPromise<int> p;
    r_type( TPromise<int>&& p_ ) : p( MoveTemp( p_ ) ) { }
    bool Init() override { return true; }
    uint32 Run() override { p.SetValue( 123 ); return 0; }
    void Stop() override { }
  } r( MoveTemp( p ) );
  constexpr auto bAutoDeleteSelf      = false;
  constexpr auto bAutoDeleteRunnable  = true;
  auto t = FRunnableThread::Create
  ( &r
  , TEXT( "promise-future tester")
  , bAutoDeleteSelf
  , bAutoDeleteRunnable
  , 0
  );
  t.WaitForCompletion();
}

スレッドを生成する事だけを考えると UE4 の生スレッドの生成は少々面倒くさい。しかし、 FRunnableThread は Suspend() や Kill() をメンバー関数として持っているので少しだけ高機能。

以上のようにして "野生のスレッド" を放つ事は UE4 のライブラリー機能としてもサポートされているが、実用上はそのような用途では std 実装を使った方が楽で future の待ち方にも工夫でき面倒も無くて良いだろう。もちろん、 std::promise と FRunnableThread を組み合わせても問題は無い。

UE4 では "野生のスレッド" ではなく、フレームワークが管理するメインスレッドとワーカースレッド群へ FAutoDeleteAsyncTask を用いてフレームワークの制御下で非同期タスクを実行もできる。それについては以下の記事が参考になるだろう。FAsyncTask や FAutoDelegateAsyncTask についてはそちらを参照すると良いだろう。

1.12. UE4/C++ における「アトミック」ライブラリーの std 互換性

所属 型 要素型 Header
std atomic<T> <T> <atomic>
UE4 FThreadSafeBool bool Runtime/Core/Public/HAL/ThreadSafeBool.h
UE4 FThreadSafeCounter int32 Runtime/Core/Public/HAL/ThreadSafeCounter.h
UE4 FThreadSafeCounter64 int64 Runtime/Core/Public/HAL/ThreadSafeCounter64.h

1.12.1. 主なメンバー関数の対応

std UE4 効果
Reset 0 にする
store
operator= 		Set 値を放り込む
load 値を取り出す
exchange 値を取り替える
operator++ Increment 1 増やす
operator-- Decrement 1 減らす
fetch_addo
perator+= 		Add 任意の数を加算する
fetch_sub
operator-= 		Subtract 任意の数を減算する
fetch_and
operator&=
fetch_or
`operator		 =` |
fetch_xor
operator^=

  • std:

  • UE4:

    • FThreadSafeBool は FThreadSafeCounter を継承して定義され、内部的には int32 で 0 と 1 のみを扱うよう制限して実現している。
    • FThreadSafeCounter と FThreadSafeCounter64 は内部的には FPlatformAtomics::InterlockedAdd などに実装を依存している。
      • 実装詳細は HAL/PlatformAtomics.h で定義され、もし気になるならば、 Runtime/Core/Public/Windows/WindowsPlatformAtomics.h などを参照すると善い。
        • 例えば Windows の場合は最終的には <intrin.h> から Win32 API の ::_InterlockedExchangeAdd 等が使われる。(MSDN)
    • int32, int64 に対応しているので、一応実質的にはこれらでも uint16 や void* も扱えないことは無い…

UE4 のアトミックを用いても UPROPERTY() や UFUNCTION() では使用できず特にメリットも無いので、ツールチェインの std 実装が信用できる場合は std のアトミックを使えば良い。

参考:

  1. atomic - cpprefjp C++日本語リファレンス
  2. FThreadSafeBool | Unreal Engine
  3. FThreadSafeCounter | Unreal Engine
  4. FThreadSafeCounter64 | Unreal Engine

1.13. UE4/C++ における「並列処理」ライブラリーと std / OpenMP / Intel-TBB / Microsoft-PPL

所属 関数・プラグマ Header
std for_each <algorithm> <execution>
OpenMP #pragma omp parallel for
Microsoft PPL parallel_for <ppl.h>
IntelTBB parallel_for <tbb/parallel_for.h>
UE4 ParallelFor Runtime/Core/Public/Async/ParallelFor.h

モダンな C++er は既に C++17 で <algorithm> に <execution> による並列処理機能が導入される事は熟知し、開発環境がこれに対応可能となる日を心待ちにしている。

とは言え、現状、現実には多くの C++er は古風でやや癖はあるものの簡単に使用できる OpenMP や、 Microsoft 環境向けだけであれば PPL 、 PC 向けのクロスプラットフォームであれば intel TBB 、 GCC だけであれば Parallel Mode など開発環境に合わせて並列化や並行処理のための機能を使用している。

UE4 でもそれらを使用する事は可能だが、 簡単なループ並列化については UE4 も ParallelFor を用意している。本節では簡単で擬似的なソースコードで C++17 Parallelism, OpenMP, Intel TBB, Microsoft PPL について同等のコードを例示的に整理する。

1.13.1. ParallelFor と for_each ( C++17 Parallelism ) #pragma omp parallel for / parallel_for ( TBB ) / parallel_for ( PPL )

// Note: このコードはほとんど実際に動きそうなコードを書いているが、擬似コードである。
// 実際には例示する example 群は同時に1つのソースコードではそのまま動作しない。
// それぞれの違いを理解しやすいよう1つにまとめたが、実行したい場合は
// それぞれのライブラリーや環境に合わせて1つ1つ試すと良い。

#include <iostream>
#include <cmath>
#include <numeric>
#include <vector>

constexpr size_t n = 256;
using value_type = double;
using values_type = std::vector< value_type >;

void process_value( const value_type v )
{
  std::cout << ( std::to_string( std::sqrt( v ) ) + '\n' );
}

// std::for_each_n ( with C++17 Parallelism )
#include <algorithm>
#include <execution>

void example_std_for_each_cpp17_parallelism( const values_type& values )
{
  std::cout << "\n[ std::for_each with C++17 Parallelism ]\n";
  
  // https://github.com/cplusplus/parallelism-ts
  // http://www.modernescpp.com/index.php/c-17-new-algorithm-of-the-standard-template-library
  // http://www.bfilipek.com/2017/08/cpp17-details-parallel.html
  std::for_each
  ( std::execution::par
  , values.begin()
  , values.end()
  , &process_value
  );
}

void example_openmp( const values_type& values )
{
  std::cout << "\n[ OpenMP ]\n";
  
  // official spec. http://www.openmp.org/specifications/
  // ref 1 https://en.wikipedia.org/wiki/OpenMP
  // ref 2 http://bisqwit.iki.fi/story/howto/openmp/
  // ref 3 (ja) http://tech.ckme.co.jp/openmp.shtml
  #pragma omp parallel for
  for ( auto i = values.cbegin(); i < values.cend(); ++i )
    process_value( *i );
}

#include <ppl.h>

void example_microsoft_ppl( const values_type& values )
{
  std::cout << "\n[ Microsoft PPL ]\n";
  
  // PPL https://msdn.microsoft.com/en-us/library/dd492418.aspx
  // parallel_for https://msdn.microsoft.com/en-us/library/dd728073.aspx
  parallel_for
  ( size_t( 0 )
  , values.size()
  , [&]( auto index )
    {
      process_value( values[ index ] );
    }
  );
}

#include <tbb/parallel_for.h>

void example_intel_tbb( const values_type& values )
{
  std::cout << "\n[ Intel TBB ]\n";
  
  // https://software.intel.com/en-us/node/506153
  parallel_for
  ( size_t( 0 )
  , values.size()
  , [&]( auto index )
    {
      process_value( values[ index ] );
    }
  );
}

#include "Runtime/Core/Public/Async/ParallelFor.h"

void example_ue4_parallel_for( const values_type& values )
{
  std::cout << "\n[ UE4 ParallelFor ]\n";
  
  // https://docs.unrealengine.com/latest/INT/API/Runtime/Core/Async/ParallelFor/
  ParallelFor
  ( values.size()
  , [&]( auto index )
    {
      process_value( values[ index ] );
    }
  );
}

int main()
{
  std::vector< double > values( n );
  std::iota( p, p + n, 0 );
  
  example_std_for_each_cpp17_parallelism( values );
  example_openmp( values );
  example_microsoft_ppl( values );
  example_intel_tbb( values );
  example_ue4_parallel_for( values );
}

UE4 は C++ で一般的に用いられる事の多い多くのライブラリー等に比べてより単純な ParallelFor しか高レベル並列化機能を提供していないが、基本的には [ 0 .. N ) のレンジの並列化そのままで多くの場合には十分かつ必要に応じて少し与えるレンジやファンクターのキャプチャーに工夫をすればたいていの用途には簡単に応用できるため多くの場合には必要十分となる。

それでは必要不十分という場合には UE4 のタスク制御機能を応用したり、必要に応じてライブラリーを導入すると良い。また、恐らくそう遠く無く C++17 Parallelism 対応の開発環境も UE4 での開発環境一般としても、特に PC 向けであれば使用可能となるので、近い未来にはアルゴリズムについてはそちらも必要に応じて使用すると良い。

なお、 ParallelFor には例では省略した最後の bool 型の引数が1つあり、デフォルトの false では並列実行されるが、 true を与えると逐次実行に動作が切り替わる機能もあり、これがデバッグに有用な事もしばしばあり便利である。

但し、 UE4 の ParallelFor については扱われる index が int32 型である点に気をつける必要がある。 C++ 界の一般的な並行処理ライブラリーでは index は size_t 型である。

参考:

  1. C++ 標準の promise / future / thread に対応する UE4 標準の TPromise / TFuture / FRunnableThread の使い方 - C++ ときどき ごはん、わりとてぃーぶれいく☆
  2. future - cpprefjp C++日本語リファレンス
  3. thread - cpprefjp C++日本語リファレンス
  4. Using AsyncTasks - Epic Wiki

1.14. UE4/C++ における「ファンクター」ライブラリーと std 互換性

std::function に相当する機能が UE4 ライブラリーにも実装されている。本節ではこれらについて std 慣れした C++er 向けに整理する。

1.14.1. TFunctionRef<T> と std::function<T>

所属 関数 Header
std function <functional>
UE4 TFunction Runtime/Core/Public/Templates/Function.h
UE4 TFunctionRef Runtime/Core/Public/GenericPlatform/GenericPlatformProcess.h
特徴 std::function TFunction TFunctionRef
has operator= yes yes no
has operator(bool) yes yes no
has ownership of a functor yes yes no
a speed prioritized no no yes

ソースコードでの具体的な比較を以下に示す:

// ふつうの関数 -> ポインターは C++ ファンクターの一種
void something_function() { }

void example()
{
  using signature_type = void();
  // ラムダエクスプレッション -> C++ ファンクターの一種
  auto lambda = []{};
  
  std::function< signature_type > f = lambda;
  if ( f ) // operator(bool) による呼び出し可能の確認に対応
    f();
  f = &something_function; // 代入によりファンクターの挿げ替えが可能
  if ( f )
    f();
  
  // UE4: TFunction
  TFunction< signature_type > g = lambda;
  if ( g ) // operator(bool) による呼び出し可能の確認に対応
    g();
  g = &something_function; // 代入によりファンクターの挿げ替えが可能
  if ( g )
    g();
  
  // UE4: TFunctionRef
  TFunctionRef< signature_type > h = lambda;
  h(); // とりあえず呼び出す事しかできないが、軽量な速度重視の実装になっている
  
  TFunctionRef< signature_type > h = lambda;
}

std::function 互換相当の TFunction については特に UE4 ならこちらを使うべきという程の強い動機はない。 TFunctionRef は UE4 にしかない機能だが、ユーザーにとってはこちらもこれという程の使い所も無いだろう。

2. プロフェッショナル C++er のための UE4/C++ リアル・ベーシック

予め断っておかねばならない事がある。§1を書き終えた時点で11月23日も終わろうとしており、著者には時間的猶予が…無い。そこで§2は内容を大幅に予定よりも削減してしまった。

アドベンカレンダーにかぎらず、著者はこのブログで毎月数本の技術ブログ記事を執筆しているので、ここで書かれる予定だった記事も興味が失われない限りはいつか記事になると思う。さしあたり、気が向いたならブログを購読しておいて頂けると読者数のカウントが私にも見えて嬉しい。

2.1. UE4/C++ におけるガベージコレクターの操作

UE4 のガベージコレクターも UHT の力を借りるとは言えライブラリーとしての実装であり、 C++ コードからある程度は制御が可能になっている。本節ではありがちな要求について UE4/C++ での実現方法について整理する。

2.1.1. 任意の UObject* の参照カウントを確認する

// o の参照カウントを取得
inline static int32 GetReferenceCount( UObject* o )
{
  check( o )
  
  constexpr bool bInRequireDirectOuter     = false;
  constexpr bool bInShouldIgnoreArchetype  = true;
  constexpr bool bInSerializeRecursively   = true;
  constexpr bool bInShouldIgnoreTransient  = false;
  
  TArray< UObject* > refs;
  
  FReferenceFinder finder
  ( refs
  , o
  , bInRequireDirectOuter
  , bInShouldIgnoreArchetype
  , bInSerializeRecursively
  , bInShouldIgnoreTransient
  );
  
  finder.FindReferences( o );
  
  return refs.Num();
}

参考:

  1. FReferenceFinder | Unreal Engine
  2. [https://wiki.unrealengine.com/Garbage_Collection~Count_References_To_Any_Object:title]

2.1.2. 強制的にガベージコレクターを動作させる

GetWorld()->ForceGarbageCollection( true );

UWorld::ForceGarbageCollecion は「強制的にガベージコレクターを動作させる」が、厳密な意味で「直ちに」ではない。 GC の監視タイマーは通常 60 秒ごとにガベージコレクトを行うが、このタイマーの残りを 0 にして、次回の（次フレームの前の） GC のタイマー判定タイミングでガベージコレクトを行わせる効果がある。

なお、当然ながら、この機能では参照カウントが有効なオブジェクトは削除されない。 UObject::ConditionalBeginDestroy を呼びポインターを保持している UPROPERTY() の値を nullptr にしておけば削除される事になる。但し、 AActor については ConditionBeginDestroy の前に Destroy を呼び忘れないよう注意されたい。

また、複数のオブジェクトから参照するが GC の参照カウントに影響する必要が無い場合は TWeakObjectPtr<T>, TAutoWeakObjectPtr<T> を用いておけば面倒が無い。

参考:

  1. TWeakObjectPtr | Unreal Engine
  2. TAutoWeakObjectPtr | Unreal Engine
  3. UWorld::ForceGarbageCollection | Unreal Engine
  4. https://wiki.unrealengine.com/Garbage_Collection_%26_Dynamic_Memory_Allocation#Counting_UPROPERTY.28.29_References_To_Any_Object

2.2. UE4/C++ における「相互排除と同期」ライブラリーと std 互換性

UE4 には 2 種類の相互排除と同期のためのライブラリー実装があるので std の同様の実装と使用例を挙げて整理する。

2.2.1. FCriticalSection クリティカルセクション型と std::mutex

// std
#include <mutex>
{
  std::mutex m;
  // scoped lock; C++17 からは template 型が省略可能になる
  { std::lock_guard< decltype( m ) > lock( m ); }
  // manual operation
  m.lock();
  m.unlock();
}
// UE4
#include "Runtime/Core/Public/Misc/ScopeLock.h"
{
  FCriticalSection m;
  // scoped lock
  { FScopeLock lock( &m ); }
  // manual operation
  m.Lock();
  m.Unlock();
}

std 版では lock_guard, adopt_lock, unique_lock など実装が UE4 よりも充実しているので、特別な事情が無く、 std 版を使用可能な場合は UE4/C++ でも std 版を使えば良い。

2.2.2. FRWLock 読み書きロック型と std::shared_mutex

既に C++17er となる準備のできている一般的な多くの C++er 、あるいは C++14er はプラットフォーム依存の API　に頼らずとも shared_mutex, shared_timed_mutex を用いて Read / Write レベルのロック制御を実装している。

UE4 でもそれらに相当… "いちおう" は相当する FRWLock がライブラリーで提供されている。

// std ( C++17 )
#include <mutex>
{
  std::shared_mutex m;
  { std::shared_lock< decltype( m ) > read_lock( m ); }
  { std::lock_guard< decltype( m ) > write_lock( m ); }
}
// std ( C++14 )
#include <mutex>
{
  std::shared_timed_mutex m;
  { std::shared_lock< decltype( m ) > read_lock( m ); }
  { std::lock_guard< decltype( m ) > write_lock( m ); }
}
// UE4
#include "Runtime/Core/Public/Misc/ScopeRWLock.h"
{
  FRWLock m;
  // scoped lock
  { FRWScopeLock read_lock( m, FRWScopeLockType::SLT_ReadOnly ); }
  { FRWScopeLock write_lock( m, FRWScopeLockType::SLT_Write ); }
  // manual operation
  m.ReadLock();
  m.ReadUnlock();
  m.WriteLock();
  m.WriteUnlock();
}

FRWLock の挙動は次の通り:

  1. ReadLock -> ReadLock: 可能
    • ReadLock した回数だけ ReadUnlock されるとロック状態が解除される
  2. ReadLock -> WriteLock: 解錠待ち（＝ブロッキング、デッドロック注意）
  3. WriteLock -> WriteLock 解錠待ち（＝ブロッキング、デッドロック注意）
  4. WriteLock -> ReadLock 解錠待ち（＝ブロッキング、デッドロック注意）
  5. 過解錠の挙動はプラットフォーム依存（≃落ちる）

参考:

  1. shared_mutex - cpprefjp C++日本語リファレンス
  2. shared_timed_mutex - cpprefjp C++日本語リファレンス
  3. shared_lock - cpprefjp C++日本語リファレンス
  4. lock_guard - cpprefjp C++日本語リファレンス
  5. C++17, C++14, C++11 に併せた std::shared_mutex, std::shared_timed_mutex, std::mutex から mutex_type, read_lock_type, write_lock_type を扱う例 - Qiita
  6. https://github.com/EpicGames/UnrealEngine/blob/4.18/Engine/Source/Runtime/Core/Public/Windows/WindowsCriticalSection.h#L114

2.3. UE4/C++ における基礎的な「HTTP」ライブラリー

UE4 には HTTP Client のライブラリー実装があるので紹介する。

2.3.1. FHttpModule

そのまま紹介してもあまり面白くないので、少し工夫して実用的にラップした例を紹介する:

#pragma once

#include "Runtime/Online/HTTP/Public/Http.h"
#include "Runtime/Core/Public/Async/Future.h"
#include "Async.h"

namespace usagi
{
  template < typename T >
  inline static TFuture< T >
  GetHTTP
  ( const FString& url
  , std::function< T ( FHttpRequestPtr, FHttpResponsePtr, bool ) >
      decoder = [] ( auto, auto, auto ) { return T(); }
  , const FString& method = TEXT( "GET" )
  , const FString& user_agent = TEXT( "X-UE4-Agent" )
  )
  {
    TSharedPtr< TPromise< T > > p( new TPromise< T >() );
    auto f = p->GetFuture();
    
    auto http = &FHttpModule::Get();
    auto request = http->CreateRequest();
    
    request->OnProcessRequestComplete().
      BindLambda
      ( [ = ]
        ( FHttpRequestPtr   request
        , FHttpResponsePtr  response
        , bool              successful
        )
        {
          UE_LOG( LogTemp, Log, TEXT( "result of http-request url: %s => %s" ), *url, successful ? TEXT( "Succeeded" ) : TEXT( "Failed" ) );
          p->SetValue( decoder( request, response, successful ) );
        }
      );
    
    request->SetURL( url );
    request->SetVerb( method );
    request->SetHeader( TEXT( "User-Agent" ), user_agent );
    
    request->ProcessRequest();
    
    return f;
  }
}

ここまで読み進んだ C++er ならこの程度のコードは難しくなく読めると思う。一応簡単に解説する。

  1. UE4 の HTTP Client 機能は 7 段階でリクエスト:
    1. FHttpModule::Get // Note: FHttpModule は singleton
    2. FHttpModule::CreateRequest
    3. IHttpRequest::OnProcessRequestComplete
    4. IHttpRequest::SetURL
    5. IHttpRequest::SetVerb
    6. IHttpRequest::SetHeader
    7. IHttpRequest::ProcessRequest
  2. 実装上の工夫として usagi::GetHTTP では:
    1. url と decoder を実引数で渡す
      • decoder は Get 結果（テキストとは限らない）を望むオブジェクトへ変換するファンクター
    2. 関数自体は Future を返す
      • 呼び出し元は Future::IsReady を確認して Future::Get する

改良の余地はあるが、あまり複雑化しても FHttpModule の紹介から遠ざかる（＆わたしの執筆時間がもうない）こともあり、この程度の実装で紹介した。

C++er は大きなフレームワーク（Qt, POCO など）を使う場合で無ければ libcurl に頼るか boost::asio でソケットから組み立てるなど何れ何かと "めんどう" な HTTP 処理だが、 UE4（大きなフレームワークだが） では Client 処理についてはこのように簡単に扱えるようになっている。

なお、 HTTP Server を簡単に組み込みたい場合は Marketplace で有償販売されている UnrealWebServer など使うと実装の苦労が無く C++ に加えて Blueprint でも簡単に扱えて良い。

もちろん、必要に応じて boost::asio や nghttp2 などから組み込んでもよいだろう。特に blueprint 対応しなくて構わないならばそれほど "めんどう" でもない。

なお、 UE4 の HTTP ライブラリーはモジュール化されているため、 "{your-project-name}.Build.cs" の PublicDependencyModuleNames.AddRange に , "Http" を追加しておく必要がある点には注意されたい。

2.4. UE4/C++ における「JSON」ライブラリー

UE4 には JSON を扱うためのライブラリーが実装されている。少々癖があるが、 UE4 で JSON を扱うならば一度試す価値はある。

2.4.1. FJsonValue 抽象型

UE4 の JSON ライブラリーは、コード例を示す前に少し解説が必要と思われる。

全てはここから始まる。

  1. FJsonValue は抽象型なのでそのオブジェクトは存在しない。
  2. FJsonValue から派生した -Array, -Boolean, -Null, -Number, -Object, -String の 6 つの型が具体的な JSON 値を保持するオブジェクトとして存在可能。
  3. TSharedPtr< FJsonValue > value = MakeSharable( new FJsonValueNull() ); の様に使う。
    • Null 以外は ctor で値を放り込める。
    • 但し、 Array は TArray< TSharedPtr< FJsonValue > > 、 Object は TSharedPtr< FJsonObject > を放り込む必要がある。
      • FJsonObject は public メンバーに TMap< FString, TSharedPtr< FJsonValue > > を持ち、 key-value を JSON の値として便利にキャストする機能を持った特別の型

理屈としては以上で JSON のオブジェクトを UE4/C++ 上のオブジェクトとして表現する。加えて、 FJsonValue と FJsonObject は値をキャストして取得する機能があり、これによって具体的な値の取得も便利に可能となっている。

但し、 { "a": { "b": [ { "c": 123 } ] } }` に対して "a.b[0].c" のようにパスでアクセスする機能などハイカラなものは無いので、地味にこつこつオブジェクトの組み立てと戦いながら扱う必要がある。

また、 UE4 の JSON ライブラリーはモジュール化されているため、 "{your-project-name}.Build.cs" の PublicDependencyModuleNames.AddRange に , "Json", "JsonUtilities" を追加しておく必要がある点にも注意されたい。

2.4.2. UE4/C++ JSON ライブラリーによる読み書き

C++er には旧くは picojson や json11 などの JSON ライブラリーが、また最近では nlohman-json ライブラリーの利用も増えている。実際問題、 C++ のオブジェクトとして JSON を扱いたいだけならばそれらの方が扱いやすくて楽だが、本記事の趣旨の都合、 UE4 の JSON ライブラリーを使った JSON の読み書きを紹介する。

慎重な C++er は使い方を誤る事は無いと思うものの、 TSharedPtr を介した、また値の取得についてはその const* （スマートポインターの const ポインターを扱う設計なのだ…）を扱わなければならないので、少々の覚悟をしてから挑まないと混乱してしまう。

次の JSON を読んでログ出力する例を挙げる:

{ "aaa": 1.23
, "bbb": true
, "ccc": "hoge"
, "ddd": [ 1.23, true, "hoge" ]
, "eee": { "ppp": "qqq" }
}

// read a JSON
/// @param in JSON string
#include "Runtime/Json/Public/Serialization/JsonSerializer.h"
void ue4_json_read( const FString in )
{
  // reader
  TSharedRef< TJsonReader<> > reader = TJsonReaderFactory<>::Create( *in );
  // string --> a value of the root
  TSharedPtr< FJsonValue > root_value;
  if ( ! FJsonSerializer::Deserialize( reader, root_value ) || ! root_value.IsValid() )
    return;
  // root: value --> root object
  const TSharedPtr< FJsonObject >* root_object;
  if ( ! root_value->TryGetObject( root_object ) )
    return;
  // root: object --> a number value of the "aaa" field
  double value_of_aaa = 0;
  if ( ! (*root_object)->TryGetNumberField( TEXT( "aaa" ), value_of_aaa ) )
    return;
  UE_LOG( LogTemp, Log, TEXT( "value_of_aaa=%f" ), value_of_aaa )
  // root: object --> a bool value of the "bbb" field
  bool value_of_bbb = false;
  if ( ! (*root_object)->TryGetBoolField( TEXT( "bbb" ), value_of_bbb ) )
    return;
  UE_LOG( LogTemp, Log, TEXT( "value_of_bbb=%s" ), ( value_of_bbb ? TEXT( "true" ) : TEXT( "false" ) ) )
  // root: object --> a string value of the "ccc" field
  FString value_of_ccc;
  if ( ! (*root_object)->TryGetStringField( TEXT( "ccc" ), value_of_ccc ) )
    return;
  UE_LOG( LogTemp, Log, TEXT( "value_of_ccc=%s" ), *value_of_ccc )
  // root: object --> a array value of the "ddd" field
  const TArray< TSharedPtr< FJsonValue > >* value_of_ddd = 0;
  if ( ! (*root_object)->TryGetArrayField( TEXT( "ddd" ), value_of_ddd ) )
    return;
  // foreach value_of_ddd ( array ) --> value --> { number | bool | string }
  for ( auto&& element_of_ddd : *value_of_ddd )
  {
    double  number_buffer = 0;
    bool    bool_buffer   = false;
    FString string_buffer;
    // value --> number
    if ( element_of_ddd->TryGetNumber( number_buffer ) )
      UE_LOG( LogTemp, Log, TEXT( "number value in ddd=%f" ), number_buffer )
    if ( element_of_ddd->TryGetBool( bool_buffer ) )
      UE_LOG( LogTemp, Log, TEXT( "bool value in ddd=%f" ), bool_buffer )
    if ( element_of_ddd->TryGetString( string_buffer ) )
      UE_LOG( LogTemp, Log, TEXT( "string value in ddd=%f" ), *string_buffer )
  }
  // root: object --> an object value of the "eee" field
  const TSharedPtr< FJsonObject >* value_of_eee;
  if ( ! (*root_object)->TryGetObjectField( TEXT( "eee" ), value_of_eee ) )
    return;
  // Note: これまでの root object のように Field 指定して取得もできるが、
  //       TMap< FString, TSharedPtr< FJsonValue > > を直接操作もできる
  for ( auto&& pair_of_eee: (*value_of_eee)->Values )
  {
    FString string_buffer;
    if ( pair_of_eee.Value->TryGetString( string_buffer ) )
      UE_LOG( LogTemp, Log, TEXT( "string:string value in eee={%s:%s}" ), *pair_of_eee.Key, *string_buffer )
  }
}

扱っている対象が抽象型の Value なのか、あるいは Array または Object なのかを中心に、オブジェクトに対しては対象はポインターか、スマートポインターか、その中の何かか、気を使って組み立てる必要がある。幸い、型のエラーは翻訳時に検出されるが、コードの実装者は少々疲れることになるだろう。

さておき、次は同じ JSON オブジェクトを構築する例を示す:

// create a JSON
/// @param in JSON string
TSharedPtr< FJsonValue > ue4_json_create()
{
  // Note: auto で受けたいが、 MakeShareable の return は
  // SharedPointerInternals::FRawPtrProxy< FJsonObject > で
  // そうなると operator-> も使えないのでだるい。
  TSharedPtr< FJsonObject > root_object = MakeShareable( new FJsonObject );
  root_object->SetNumberField( TEXT( "aaa" ), 1.23 );
  root_object->SetBoolField( TEXT( "bbb" ), true );
  root_object->SetStringField( TEXT( "ccc" ), TEXT( "hoge" ) );
  TArray< TSharedPtr< FJsonValue > > ddd_array;
  ddd_array.Reserve( 3 );
  ddd_array.Emplace( MakeShareable( new FJsonValueNumber( 1.23 ) ) );
  ddd_array.Emplace( MakeShareable( new FJsonValueBoolean( true ) ) );
  ddd_array.Emplace( MakeShareable( new FJsonValueString( TEXT( "hoge" ) ) ) );
  // SetXXXField 系では右辺値参照はサポートされていない
  root_object->SetArrayField( TEXT( "ddd" ), ddd_array );
  TSharedPtr< FJsonObject > eee_object = MakeShareable( new FJsonObject );
  eee_object->SetStringField( TEXT( "ppp" ), TEXT( "qqq" ) );
  root_object->SetObjectField( TEXT( "eee" ), eee_object );
  return MakeShareable( new FJsonValueObject( root_object ) );
}

参考:

  1. Dom | Unreal Engine

2.5. UE4/C++ における「ファイルシステム」ライブラリー

実行時にファイルシステムを覗きたい需要はままあるかと思う。一般に C++er は C++14er である現在まで長きに渡り filesystem について標準ライブラリーで十分には扱えない事に嘆いていた。しかし C++17er がその嘆きを過去のものにする日は既にそう遠くない。

UE4 にもファイルシステムライブラリーが実装されている。もう数日、あるいはもう少し、 UE4 の release ラインが公式に C++17 ビルドに対応するその日まで有用かもしれない簡単な例を掲載する事とした。 ".json" 拡張子を持つファイル群を特定のディレクトリーから実行時に根こそぎ読み出す UE4 のファイルシステムライブラリーでの実装例を紹介する。

2.5.1. UE4 のファイルシステムライブラリーで .json ファイルを根こそぎ読み出す

実装例兼参考リンク:

// UE4
{
  const FString my_json_dir = TEXT( "my_json_dir" );
  
  TArray< FString > directories_to_skip;
  // https://docs.unrealengine.com/latest/INT/API/Runtime/Core/HAL/FPlatformFileManager/
  IPlatformFile& platform_file = FPlatformFileManager::Get().GetPlatformFile();
  // https://docs.unrealengine.com/latest/INT/API/Runtime/Core/Misc/FLocalTimestampDirectoryVisitor/
  FLocalTimestampDirectoryVisitor Visitor( platform_file, directories_to_skip, directories_to_skip, false );
  // https://docs.unrealengine.com/latest/INT/API/Runtime/Core/Misc/FPaths/
  // https://docs.unrealengine.com/latest/INT/API/Runtime/Core/Misc/FPaths/ProjectDir/index.html
  platform_file.IterateDirectory( *( FPaths::ProjectDir() / my_json_dir ), Visitor );
  
  for ( TMap< FString, FDateTime >::TIterator TimestampIt( Visitor.FileTimes ); TimestampIt; ++TimestampIt )
  {
    const FString file_path = TimestampIt.Key();
    const FString file_name = FPaths::GetCleanFilename( file_path );
    
    if ( FPaths::GetExtension( file_name, false ).Equals( TEXT( "json" ), ESearchCase::IgnoreCase) )
    {
      FString json_text;
      
      if ( FFileHelper::LoadFileToString( json_text, *file_path, FFileHelper::EHashOptions::None ) )
        // 前節で紹介した JSON の reader へ投げるなどお好み処理
        ue4_json_read( json_text );
    }
  }
}

2.6. エンジンプラグインのリビルド

時折、 Marketplace で購入したエンジンプラグインのローカル環境での手修正、そして手リビルドをしたい場合があるかもしれない。私は最近もあった。

エンジン本体のローカル環境でのリビルドは公式にわかりやすい解説もあるし、 Linux でも Windows でも困らないが、エンジンプラグインのリビルドは方法を知らないとどうしたもんかと少々悩むかもしれないので最後に紹介する事とした。

2.6.1. エンジンプラグインのリビルド

  1. エンジンプラグインはディレクトリーごと 7z でもしてバックアップしてからソースの改変作業を開始する。
  2. ソースを改変する。
  3. リビルドしてパッケージを適当な dir へ吐き出す。
    • "C:\Program Files\Epic Games\UE_4.18\Engine\Build\BatchFiles\RunUAT.bat" BuildPlugin -plugin="C:\Program Files\Epic Games\UE_4.18\Engine\Plugins\Marketplace\SomethingPlugin\Something.uplugin" -package="C:\Users\usagi\tmp\xxxxx"
  4. エンジンプラグインのディレクトリーの中身をリビルドした中身へ挿げ替える。

おわりに

§2 はお察しのように大幅に削る事になってしまった。しかしこれでも11月の任意に行動可能なプライベート時間は98%をこの執筆に費やした気分でいる。実際のところもっと時間をとれるかとも思ったが、現実に一日は24時間、仕事はきっちりやる（というかザンギョーもする）なかではなかなか他の趣味の時間をゼロにしても完全な内容には程遠い完成度の文書しか残せなかったことが悔やまれる。しかし、12月1日はもうすぐそこまで来ている。それにこの後わたしは C++ アドベンカレンダーの記事も書くことにしている。時間が、足りない。悲しい。

そして、そんなことをしてこの記事を書いていた11月は趣味で好き勝手に作る楽しいゲーム開発の時間はゼロにしていた。これもまたつらい。数時間前に STEAM からのメールを見て「フィリスのアトリエ」も DLC コンプリートで買ってしまい、詰みゲーも増えた。

私はもともと毎月何本か適当にこのブログで技術記事も執筆しているし、他に趣味のお茶の話と食べ物の話のブログもちらほら書いている。

日頃から技術ブログを書いている事もあり、せっかくアドベンカレンダーに参加するならば、といつもより頑張った記事でも書こうとしてしまい、正直これはたいへん疲れた。アドベンカレンダーは日頃情報発信する機会の少ない方にも情報発信する機会として有用という要素もあるし、私の場合は放って置いても技術ブログを書いているので、やっぱりアドベンカレンダーは今回を最後に引退しようかな、なんて思っています😅

ともあれ、今回書ききれなかった§2にあるべきような節に相当する内容なども含め、今後もちまちまこのブログでは記事を書きますので興味があれば、あるいはググった拍子になど適当に、購読やはてなスターやSNSでのいいねなど頂ければ嬉しいです。

では、みなさん良いクリスマスまで残り24日間と数時間、楽しんで参りましょう😃 私はひとあし先に、一仕事終えた気分で続く記事を楽しみに待つ事とします。

Real Unreal Engine C++ 2017-12 (part-4/5)

C++ UE4 Advent Calendar 2017 part-4

（はてなブログの記事あたりの容量制限のため前の部分 §1.9.4 までは前の記事でどうぞ→http://usagi.hatenablog.jp/entry/2017/12/01/ac_ue4_2_p3）

1.9.5 FMath に含まれる型

FMath には3次元の可視空間を扱う上で必要な形状や数値を扱うための型も定義されている。

数が多いので表に概要を整理する:

概要 型
std::numeric_limits<T>のとてもしょぼい版。Min, Max, Lowest くらいしか実装されていないので std::numeric_limits<T> を使っておけばよい。 TNumericLimits
任意精度整数 TBigInt
浮動小数点数のバイナリー表現を一般化する template 型 TFloatPacker
IEEE754/Binary16 相当の浮動小数点数型 FFloat16
ソボル準乱数 FSobal
EUnit で定義される単位間の変換 FNumericUnit
単位変換 FUnitConversion
FUnitConversion が単位の表示名などに使うための補助的な型 FUnitSettings
D3D DirectX::XMVECTOR のエイリアス VectorRegister
SSEレジスター __m128d のエイリアス VectorRegisterDouble
SSEレジスター __m128i のエイリアス VectorRegisterInt
随意型（オプショナル型）
std::optiona<T>(C++17) や boost::optional<T> 相当だが operator bool, operator* の実装都合、 TOptional<T> は地味に扱いが面倒。 UE4 が C++17 標準対応完了すれば要らなくなる子。（ TArray のようにBlueprintでも使用可能になるなどすればまた別だが・・・） 		TOptional
成功値の型と失敗値の型を指定可能な TOptional のごつくなったようなやつ TValueOrError
補間 FInterpCurve
FInterpCurveFloat
FInterpCurveLinearColor
FInterpCurvePoint
FInterpCurveQuat
FInterpCurveTwoVectors
FInterpCurveVector
FInterpCurveVector2D注:FInterpCurve は F 始まりの型だが template
球面座標 TSHVector
RGB色用の球面座標 TSHVectorRGB
3次元ベクター FVector
FIntVector
2次元ベクター FVector2D
FIntPoint
半精度浮動小数点数型の2次元ベクター FVector2DHalf
4次元ベクター FVector4
FIntVector4
FUintVector4
線形色
RGBAを値域 [0..1] に正規化した表現 		FLinearColor
2 点を保持（するだけ） TInterval
FFloatInterval
FInt32Interval
2 点を保持（多機能） TRange
FAnimatedRange
FDateRange
FDoubleRange
FFloatRange
FInt8Range
FInt16Range
FInt32Range
FInt64Range
Rangeの内外の制御を行う型 TRangeBound
FDateRangeBound
FDoubleRangeBound
FFloatRangeBound
FInt8RangeBound
FInt16RangeBound
FInt32RangeBound
FInt64RangeBound
Range 集合用の template 型 Add や Contains など集合に対する操作を行える。 TRangeSet
2つの3次元ベクターの対 FTwoVectors
2つのベクターで表される角（かど） FEdge
立方体 FBox
球 FSphere
同一原点の軸平行直方体（AABB）と球の組み合わせ形状 FBoxSphereBounds
平面 FPlane
カプセル形状 FCapsuleShape
中心と軸方位と軸方位への広がり量を基に任意回転した立方体（の頂点位置）を表現する型 FOrientedBox
矩形 FBox2D
FIntRect
uin32 範囲で行数と列数をそれぞれ任意に template で与えられる行列型 TMatrix
4x4行列 FMatrix
2x2行列 FMatrix2x2
回転変換行列 FRotationMatrix
回転と平行移動の変換行列 FRotationTranslationMatrix
四元数を基にした回転の変換行列 FQuatRotationMatrix
四元数を基にした回転と平行移動の変換行列 FQuatRotationTranslationMatrix
逆回転変換行列 FInverseRotationMatrix
点を中心に回転する変換行列 FRotationAboutPointMatrix
拡大縮小変換行列 FScaleMatrix
拡大縮小と回転と平行移動の変換行列 FScaleRotationTranslationMatrix
変形（拡大縮小、回転、平行移動）変換行列 FTranslationMatrix
視線変換行列 FLookAtMatrix
正射影変換行列 FOrthoMatrix
遠近法変換行列 FPerspectiveMatrix
逆Z軸正射影変換行列 FReversedZOrthoMatrix
逆Z軸遠近法変換行列 FReversedZParspectiveMatrix
鏡像行列
ある平面で鏡像化するための変換行列 		FMirrorMatrix
行列を他の表現に変換するための変換器 TransformConverter
オイラー角に基づく回転型 FRotator
四元数による3次元の回転型 FQuat
四元数風の2次元の回転型 FQuat2D
3次元の拡大縮小を表す型 FScale
2次元の拡大縮小を表す型 FScale2D
3次元変形（拡大縮小、回転、平行移動） FTransform
2次元変形（拡大縮小、回転、平行移動） FTransform2D
2次元の剪断 FShear2D
自称「スレッドセーフで低ビットの品質の悪い擬似乱数生成器」
実装を見るにスレッドセーフではないし、線形合同法ベースだし、 C++er は <random> を使っておけばよいので存在を忘れても構わない何か。 		FRandomStream
暗号鍵用に整数の指数と剰余を保持する template 型 TEncryptionKey

この節の表を作っただけで力尽きて来たので、面白い小話などはまた別の機会に書く事にする。さしあたり、 C++er は FMath に定義される機能で必要十分な限りにおいては FMath の部品を再実装せず少々の癖はあるが上手く付き合えるよう、どのような機能の関数と型があるのか脳内にインデクシングしておくと良い。

なお、 UE4 の線形幾何ライブラリーの実装レベルは速度最適化の面から言っても、それほど優れた実装にはなっていない。例えば、 Eigen のように template が充実していたり、 expression template により評価を遅延していたり、などという工夫はほとんど無く、わりと単純に float ベースで個々に実装されている。そういうわけで、 "必要十分な限りにおいては" と書いた。それについてもまた本記事の趣旨とは少々ずれるので別の機会があれば書く事にする。

1.10. UE4/C++ における入門的な「コンテナー」ライブラリーの std 互換性

一般的な std 慣れした C++er は UE4 コンテナーのメンバー変数の命名と機能とパラメーターに翻弄される。この節では std に慣れた C++er が UE4/C++ にうっかり翻弄され難くなるよう、予防接種的な視点にも注意しながら UE4 のコンテナー類を整理する。

1.10.1. TArray<T> と std::deque<T> / std::vector<T> / std::queue / std::stack

所属 型 Header
std vector <vector>
std deque <deque>
std stack <stack>
std queue <queue>
UE4 TArray Runtime/Core/Public/Containers/Array.h
UE4 TQueue Runtime/Core/Public/Containers/Queue.h

C++er は std::vector / std::stack / std::queue がコンテナーアダプターであり、実装詳細は std::deque コンテナーである事をよく知っている。また、多くのコンテナー類に対して操作を共通化するため <algorithm> が用意され、ほとんどの操作はイテレーターを介したレンジで扱われる事もよく把握している。

UE4 にはそれらをひとまとめにしたような "便利" なコンテナーとして "マッチョ" な TArray が定義されている。

そこで、この項では std::vector / std::stack / std::queue と TArray を対応させ、機能の有無や対応関係がわかりやすいよう整理する。また、 UE4 にはキュー専用に特化した TQueue も定義されているので "ついで" 程度に含める事にする。

なお、「機能を組み合わせれば実現できる」ものは除外し（それは C++er なら脳内でわかること）、直接的にそのように振る舞う機能がある場合にのみ表に関数名を記載する。

効果 std::deque std::vector std::stack std::queue TArray TQueue
[begin..end)の値群に置き換える assign assign
別のコンテナーの値群を追加する Append
operator+=
最前に値を直接生成する emplace_front
最後に値を直接生成する emplace_back emplace_back emplace emplace Emplace
最前に値を入れる push_front
最後に値を入れる push_back push_back push push Add
AddDefaulted
AddUninitialized
AddUnique
AddZeroed
<Push> 		Enqueue
最前の値を削除する pop_front pop Pop Pop
最後の値を削除する pop_back pop_back pop
任意の位置へ値を直接生成する EmplaceAt
任意の位置へ値を内挿する insert insert Insert
InsertDefaulted
InsertUninitialized
InsertZeroed
値を全て削除する clear clear Empty
Reset
保持する値の数を変更する resize resize SetNum
SetNumUninitialized
SetNumZeroed
Init
保持する値の数を予約する reserve Reserve
値を範囲で削除する erase erase
値を値またはインデックスで削除する Remove
RemoveAll
RemoveAllSwap
RemoveAt
RemoveAtSwap
RemoveSingle
RemoveSingleSwap
RemoveSwap
保持可能な値の数を実際の保持数に最適化する shrink_to_fit shrink_to_fit Shrink
最前の値を取得する front front front Peek
Dequeue
最後の値を取得する back back top back Last
Top
任意の位置の値を範囲チェック付きで取得する at at
任意の位置の値を取得する operator[] operator[] operator[]
先頭の値のメモリーアドレスを取得 data GetData
値を保持していない事を判定する empty empty empty empty IsEmpty
値の保持数が正常かアサーション（ checkSlow ）する CheckInvariants
保持する値の数を取得する size size size size Num
保持する値の総容量を取得する CountBytes
内部バッファーの数を取得する capacity
内部バッファーの空き数を取得する GetSlack
内部バッファーのメモリー容量を取得する GetAllocatedSize
値を保持可能な最大数を取得する max_size max_size Max
最前のイテレーターを取得する begin begin CreateIterator
最後のイテレーターを取得する end end
最前のconstイテレーターを取得する cbegin cbegin CreateConstIterator
最後のconstイテレーターを取得する cend cend
最後からの始端のリバースイテレーターを取得する rbegin rbegin
最後からの終端のリバースイテレーターを取得する rend rend
最後からの始端のconstリバースイテレーターを取得する crbegin crbegin
最後からの終端のconstリバースイテレーターを取得する crend crend
別のコンテナーと値群を挿げ替える swap swap swap swap Swap
別のコンテナーと値群のメモリーを挿げ替える SwapMemory
アロケーターを取得する get_allocator get_allocator
有効なインデックスか判定する IsValidIndex
有効なレンジか判定する RangeCheck
アドレスがコンテナーの値か判定する CheckAddress
値のインデックスを取得する IndexOfByKey
IndexOfByPredicate
要素型のメモリー容量を取得する GetTypeSize
値が含まれるか判定する Contains
ContainsByPredicate
最前から値を検索する std::find Find
FindByKey
FindByPredicate
FindItemByClass
最後から値を検索する FindLast
FindLastByPredicate
フィルターしたコンテナーのコピーを取得する std::copy_if FilterByPredicate
非安定ソートする std::sort Sort
安定ソートする std::stable_sort StableSort
シリアライズ結果を取得する BulkSerialize
保持する値群をヒープ構造化する std::make_heap Heapify
保持する値群がヒープ構造化されているか判定する std::is_heap VerifyHeap
ヒープ構造を前提に最前の値を削除する std::pop_heap HeapPop
HeapPopDiscard
ヒープ構造を前提に値を追加する std::push_heap HeapPush
ヒープ構造を前提に任意の位置の値を削除する HeapRemoveAt
ヒープ構造を前提にソートする std::sort_heap HeapSort

この他に大きな相違として、 UE4 では TArray と次節で紹介する TMap 、それと TSet については template であっても例外的に UE4Editor / Blueprint でも直接的な使用がサポートされている点、 UPROPERTY() マクロの指定が可能な点がある。これは一般に C++ コードだけでは完結しない UE4 のプロジェクトの "開発" について、また UObject 派生型を要素型とする必要性において、しばしばコンテナーの実装に求められる重要な要件となる。

std 慣れした C++er が注意を要する TArray を扱う上でのポイントは以下の通り:

  1. deque | vector | stack | queue | SORT | HEAP | FIND ≃ TArray
  2. size ＝ Num
  3. resize ≃ SetNum
  4. reserve ＝ Reserve
  5. empty() ≃ Num() > 0 と clear() ≃ Empty() の混乱回避。
  6. std::remove + erase （ erase-remove idiom ） ≃ Remove
  7. data ＝ GetData
  8. TArray は UPROPERTY() 可能。
  9. std アルゴリズムのレンジは生ポインターでも動作するので TArray にも適用はできる。
  10. std::vector における reserve や capacity で扱う内部バッファーを TArray では "Slack" （スラック）と用語を充てている。

1.10.2. TMap<K,V> と std::unordered_map<K,V>

所属 型 Header
std unordered_map <unordered_map>
UE4 TMap Runtime/Core/Public/Containers/Array.h

std の解説一般でもしばしば同じ節で扱われるように unordered_map にはよく似た unordered_set があり、 UE4 にもそれらと同じ関係の TMap と TSet がある。この記事は網羅的なクラスや API の紹介が趣旨ではないため（＆そろそろアドベンカレンダーの期日も近づきすぎている都合もあり…）、冗長を避ける意味でも unordered_map vs. TMap のみを取り上げる。

効果 std::unordered_map TMap TMap のメンバーの継承元
別のコンテナーの値群を追加する Append
operator+= 		TMap
キーと値の組みを直接生成する emplace Emplace TMapBase
キーと値の組みを挿入位置のヒント付きで直接生成する emplace_hint
キーと値の組みを入れる insert Add TMapBase
キーの値を取得または生成して取得する operator[] FindRef TMapBase
キーの値を取得する at FindChecked
operator[] 		TMapBase
TMap
キーの値を取得または生成してポインターを取得する FindOrAdd TMapBase
キーの値のポインターを取得する Find TMapBase
値のキーのポインターを取得する FindKey TMapBase
キーの組みのイテレーターを取得する find
equal_range
キーの組みを削除しつつ値を取得する FindAndRemoveChecked TMap
キーの組みの有無を確認して存在すれば削除しつつ値を取得する RemoveAndCopyValue TMap
キーの組みを削除する erase Remove TMapBase
組みを全て削除する clear Empty
Reset 		TMapBase
内部バッファーの数を予約する reserve Reserve TMapBase
内部バッファーのバケットの最小数を指定してバケット数を調整する rehash
内部バッファーのバケットの負荷率の最大値を設定または取得する max_load_factor
内部バッファーのバゲットの負荷率を取得 load_factor
内部バッファーの末尾の未使用領域を削除する Shrink TMapBase
内部バッファーの未使用領域を削除する Compact TMapBase
内部バッファーの未使用領域を使用領域の順序を保持して削除する CompactStable TMapBase
組みの順序をキーでソートする KeySort TSortableMapBase
組みの順序を値でソートする ValueSort TSortableMapBase
組みへのconstイテレーターを取得する cbegin CreateConstIterator TMapBase
組みの終端へのconstイテレーターを取得する cend
キーへのconstイテレーターを取得する CreateConstKeyIterator TMapBase
組みへのイテレーターを取得する begin CreateIterator TMapBase
組みの終端へのイテレーターを取得する end
キーへのイテレーターを取得する CreateKeyIterator TMapBase
キーの配列と数を取得する GetKeys TMapBase
組みの数を取得する size Num TMapBase
内部バッファーの数を取得する bucket_count GetAllocatedSize TMapBase
内部バッファーの最大数を取得する max_size
bucket_size
キーが存在するか判定する count Contains TMapBase
保持する組みが空か判定する empty
キー群の配列を取得する GenerateKeyArray TMapBase
値群の配列を取得する GenerateValueArray TMapBase
内部バッファーを出力デバイス（ログ的なやつ）へ書き出す Dump TMapBase
シリアライズに要するメモリー容量を取得する CountBytes TMapBase
アロケーターを取得する get_allocator
要素を挿げ替える swap
ハッシュ関数オブジェクトを取得する hash_function
キー比較用オブジェクトを取得する key_eq

std::unordered_map に比べ TMap ではキー、値それぞれに着目した操作や列挙の実装が充実している。 std 慣れした C++er が留意すべき TMap のポイントは次の通り:

  1. unordered_map の operator[] は存在しない要素は生成してくれるが、 TMap の operator[] は存在しない要素は生成してくれない（実行時エラーとなる）。その用途には FindRef を使う。
  2. TMap は KEY, VALUE によるソートが可能。
  3. メンバーの命名 → TArray と同様の注意が必要。
  4. UPROPERTY() 可能。
  5. インデックスアクセスも可能な連想配列として振る舞う（もちろん表面上は似てはいるが std::unordered_map の一般的な実装と TMap の実装詳細はまったく異なる）

1.10.3. その他の UE4 コンテナーライブラリー

他の std に対応する UE4 コンテナーは以下の通り:

概要 std UE4
ビット列コンテナー std::vector<bool> TBitArray
単方向リスト std::forward_list<T> TList<T>
ソート済み連想コンテナー std::map<K,V> TSortedMap<K,V>
ハッシュ集合 std::unordered_set<T> TSet
優先度付きキュー std::priority_queue<T> FBinaryHeap<K,I>

また、 他にも UE4 には std には無いコンテナー類も存在します。そのうちの一部は boost には同種のコンテナーが存在する。

概要 boost UE4
既存の生配列を参照してサイズ変更を除く TArray<T> と同等の操作を可能にするビュー TArrayView
循環バッファー boost::circular_buffer<T> TCircularBuffer<T>
ロックフリー循環キュー boost::lockfree:queue TCircularQueue<T>
ロックフリーポインターリスト FLockFreePointerListFIFO
FLockFreePointerListLIFORoot
疎配列 Boost.SparseVector SparseArray<T>
バリアント集合 TUnion<A,B,C,D,E,F>

何れも前項までに紹介したコンテナー類よろしく std 慣れした C++er の脳を引っ掻き回すような命名規則や引数はおおよそ共通。また、一部には EPIC GAMES 以外が主体的に開発したソースも含まれさらなる混沌感も少々ある。

何れも使い所次第では単に TArray<T> や TMap<T> あるいは TSet<T>、それに何らかの工夫を加えて使うよりも高効率であったり便利であったりはするものの、 UE4Editor / Blueprint からは使用不能。必要が生じたら使える程度に軽く脳にインデクシングしておけば善いでしょう。

（はてなブログの記事あたりの容量制限のため続き §1.11. 以降は次の記事でどうぞ→http://usagi.hatenablog.jp/entry/2017/12/01/ac_ue4_2_p5）

Real Unreal Engine C++ 2017-12 (part-3/5)

C++ UE4 Advent Calendar 2017 part-3

（はてなブログの記事あたりの容量制限のため前の部分 §1.9.3 までは前の記事でどうぞ→Real Unreal Engine C++ 2017-12 (part-2/5) - C++ ときどき ごはん、わりとてぃーぶれいく☆）

1.9.4. Fmath の真価

前項では FMath について少し残念な結果も見えたが、ともあれ、これまでの下層の実装の上に、 UE4/C++er が実際に多くの場合に数学関数のために触れる FMath が実装される。

API Reference を見ると冒頭の Inheritance Hierarchy でも FPlatformMath から派生している事がわかる。この FPlatformMath は前項のようにプラットフォームごとに実装が特殊化されており、その基底型として FGenericPlatformMath 、また数学関数の最下層としては本節の始めの項のように C++ の CRT 互換層も #include している。

さて、それでは FMath 型には何が定義されているかというと、主に線形幾何、そして範囲操作、補間、角度単位の変換などの関数群、そして区間、ベクター、回転、四元数、行列、任意精度整数、球面座標、IEEE754/binary16 実装など、主に線形幾何と補間、そして GPU 互換性が必要な場合向けの型が含まれる。

FMath の機能詳細の全貌を明らかとする事は本記事の目的から逸脱する事、また FMath の規模が大きい事、 std 慣れした C++er にとって特に互換性のある標準機能は無く、さしあたりこうした機能群が UE4 の FMath に存在するという予備知識が得られれば十分である事などを理由に、本項では関数の概要を紹介するに留める。

効果 UE4
int32値 n を与え [0..n] に一様分布する乱数を得る
注意: C++ CRT 線形合同法擬似乱数生成器ラッパーを内部的に使用。 		RandHelper
FRandRange と同じ。 int32 版と誤用されないようオーバーロードしている。 RandRange
実数区間 [a..b] に一様分布する擬似乱数を取得注意: C++ CRT 線形合同法擬似乱数生成器ラッパーを内部的に使用。 FRandRange
bool 型の擬似乱数を得る
注意: C++ CRT 線形合同法擬似乱数生成器ラッパーを内部的に使用。 		RandBool
長さ 1 の擬似乱数ベクターを得る
注意: C++ CRT 線形合同法擬似乱数生成器ラッパーを内部的に使用。 		VRand
中心方位と水平および垂直の弧度法による角度範囲に基づくコーン形状の方位を向くランダムなベクターを得る
注意: C++ CRT 線形合同法擬似乱数生成器ラッパーを内部的に使用。 		VRandCone
直方体の稜線または内部に一様分布する擬似乱数の点を得る
注意: C++ CRT 線形合同法擬似乱数生成器ラッパーを内部的に使用。 		RandPointInBox
面法線の明らかな面へ入射するベクターの反射ベクターを取得 GetReflectionVector
値 TestValue が 値域 [MinValue .. MaxValue) か判定 IsWithin
値 TestValue が 値域 [MinValue .. MaxValue] か判定 IsWithinInclusive
2つの浮動小数点数型の値について差が誤差許容値以内か判定する
デフォルトの誤差許容値は 1.0e-8f 		IsNearlyEqual
浮動小数点数型の値と 0 との差が誤差許容値以内か判定する
デフォルトの誤差許容値は 1.0e-8f 		IsNearlyZero
整数について2の指数倍か判定
実装詳細の都合、負の値は false、 0, 1 は true を返す。 		IsPowerOfTwo
3つの値から最大値を選択 Max3
3つの値から最小値を選択 Min3
2乗 Square
制限された値域へ切り詰める Clamp
値 Grid の間隔に対し入力値を四捨五入的に吸着した値を取得 GridSnap
繰り上げ除算
(10,1) -> 10, (10,2) -> 5, (10,3) -> 4, (10, 4) -> 3, .. 		DivideAndRoundUp
繰り下げ除算
(10,1) -> 10, (10,2) -> 5, (10,3) -> 3, (10, 4) -> 2, .. 		DivideAndRoundDown
底2の対数
実装詳細で static const float LogToLog2 = 1.f/Loge(2.f) をキャッシュし return Loge(x)*LogToLog2 しているため cl.exe の std::log2 比で 1.37 倍程度高速。 		Log2
正弦と余弦の同時計算
cl.exe では O3 でも個別に計算するより 1.13 倍程度高速。 		SinCos
高速逆正弦（10進数で5桁まで安全な精度、O3条件下で2.2%程度Asinより高速） FastAsin
弧度法単位を度数法単位へ変換 RadiansToDegrees
度数法単位を弧度法単位へ変換 DegreesToRadians
弧度単位の角度を回転を考慮して制限された値域へ切り詰める ClampAngle
2つの与えられた度数法の角度の差を値域(-180..+180)で取得 FindDeltaAngleDgrees
2つの与えられた弧度法の角度の差を値域(-π..+π)で取得 FindDeltaAngleRadians
DEPRECATED -> FindDeltaAngleRadians に同じ。 FindDeltaAngle
弧度法の角度を [-π..+π] の範囲の表現に変換する UnwindRaidnas
度数法の角度を [-180..+180] の範囲の表現に変換する UnwindDegrees
2つの度数法の角度を与え、一方を180°を超える回転を伴わない角度へ反転する
この関数は四元数を使わずに回転を最適化したい場合用に用意されている 		WindRelativeAnglesDegrees
度数法の角度を角度区間 [a..b] にクランプ。
但し負の入力や周回には恐らく意図しない応答となる。 		FixedTurn
カルテシアン座標から極座標を得る CartesianToPolar
極座標からカルテシアン座標を得る PolarToCartesian
任意の軸方向の系で対象への向きから対象への相対的な方位角の余弦値と仰俯角の正弦値を計算
GetAzimuthAndElevation に比べ O3 で 1.34 倍速程度高速 		GetDotDistance
任意の軸方向の系で対象への向きから対象への相対的な方位角(rad;右側が+)と仰俯角(rad;上側が+)を計算 GetAzimuthAndElevation
値を値域 [min .. max] から値域 [0 .. 1] へ写像
"Pct"は"Percentage"の略記と思われるが実際には"Percentage"ではなく単純な比（はみ出し有りの unorm ）である。 		GetRangePct
Lerp の FVector2D 版。 GetRangeValue
値を値域 [in.x .. in.y] から値域 [out.x .. out.y] へクランプ有りで写像 GetMappedRangeValueClamped
値を値域 [in.x .. in.y] から値域 [out.x .. out.y] へクランプ無しで写像 GetMappedRangeValueUnclamped
値域 [a..b] について比 Alpha となる値を取得
但しプラットフォームネイティブの整数型以上のビット幅の整数型の全域は扱えない。その必要があれば LerpStable を使う。 		Lerp
Lerp の整数型全域に対して安全な実装
Lerp は実装詳細で b-a を計算するが、x64でこの計算は 32 bits 未満の a, b に対しては 32 bit 整数に拡張して行われるため、 int8 で a=-128, b=0, Alpha=1.0 を与えると b-a=+128 となり、結果的には (T)(a+Alpha*128) はオーバーフローして 0 となるから写像としては正しい結果が得られる。しかし、 int32 の a, b を同様に与える場合には b-a の時点でオーバーフローし 0 となるため (T)(a+Alpha*0) は Alpha=1.0 でもaとなる。これはint64等でも同様に発生する。LerpStableはこの問題の発生しない実装。なお、LerpとLerpStableの速度差は O0 でも O3 でもほとんど無いので特別な事情が無ければLerpStable` を使っておけば良い。 		LerpStable
二次元の補間結果を得る BiLerp
3次 Hermite 補間した点の値を計算 CubicInterp
3次 Hermite 補間した点の1次微分値を計算 CubicInterpDerivative
3次 Hermite 補間した点の2次微分値を計算 CubicInterpSecondDerivative
底 Alpha 指数 Exp の指数関数で得られる値域 [0..1] を値域 [a..b] へ写像 InterpEaseIn
1 - InterpEaseIn InterpEaseOut
InterpEaseInとInterpEaseOut を1:1で合成 InterpEaseInOut
値域 [0..1] を分解能 Step で分割した離散値へ入力値 Alpha 吸着し値域 [a..b] へ写像 `InterpStep
値域 [0..1] で表される比の入力値 Alpha を-cos(Alpha*π/2)+1 関数で補正し値域 [a..b] へ写像 InterpSinIn
1 - InterpSinInと等価 InterpSinOut
InterpSinInとInterpSinOut を1:1で合成と等価 InterpSinInOut
値域 [0..1] で表される比の入力値 Alpha を-exp2(-10*Alpha)+1 関数で補正し値域 [a..b] へ写像 InterpExpoIn
1 - InterpExpoIn InterpExpoOut
InterpEaseInとInterpEaseOut を1:1で合成 InterpExpoInOut
値域 [0..1] で表される比の入力値を円関数で補正し値域 [a..b] へ写像 `InterpCircularIn
1 - InterpCircularIn InterpCircularOut
InterpCircularInとInterpCircularOut を1:1で合成 InterpCircularInOut
回転 FRotator において Lerp と基本的に同様、但し最短経路ではなく値域に応じて180°以上の経路を取る LerpRange
3次 Catmull-Rom スプライン補間 CubicCRSplineInterp
3次 Catmull-Rom スプライン補間、フェイルセーフ機能付き CubicCRSplineInterpSafe
InterpTo の 3次元ベクター FVector による正規化法線版 VInterpNormalRotationTo
InterpConstantTo の 3次元ベクター FVector 版 VInterpConstantTo
InterpTo の 3次元ベクター FVector 版 VInterpTo
InterpConstantTo の 2次元ベクター FVector2D 版 Vector2DInterpConstantTo
InterpTo の 2次元ベクター FVector2D 版 Vector2DInterpTo
InterpConstantTo の回転 FRotator 版 RInterpConstantTo
InterpTo の回転 FRotator 版 RInterpTo
float 用の区間 [a..b] にクランプされる速度倍率制御付き線形補間 FInterpConstantTo
事実上 FInterpConstantTo と同じ（実装詳細は異なる） FInterpTo
InterpTo の線形色 FLinearColor 版 CInterpTo
周波数 (Hz) と位相シフト [0..1] と時刻 (sec) から振幅範囲 [0..1] の正弦波の振幅値を得る MakePulstingValue
線分と平面の交差判定 LinePlaneIntersection
遠近法変換行列、視野変換行列、視点、有効な球形の範囲からシザー領域の必要性の判定と領域の計算を行う ComputeProjectedSphereScissorRect
平面と軸平行直方体（AABB）の交差判定 PlaneAABBIntersection
球と軸平行直方体（AABB）との交差判定 SphereAABBIntersection
点と直方体の交差判定 PointBoxIntersection
線分と直方体の交差判定 LineBoxIntersection
掃引直方体と直方体の交差判定 LineExtentBoxIntersection
線分と球形状の交差判定 LineSphereIntersection
球とコーン形状の交差判定 SphereConeIntersection
三次元の2点を結ぶ線分上で他の任意の1点に最近接する点を得る
OnSegment2Dと同じ結果となるが、命名から推量するに線分と直線などの違いが設計段階ではあったのかもしれない。 		ClosestPointOnLine
ClosestPointOnSegment
三次元の2点を結ぶ無限遠の直線上で他の任意の1点に最近接する点を得る ClosestPointOnInfiniteLine
3つのFPlane平面が交わるか判定し return を返し、交わる場合には交わる交点 I を与える IntersectPlanes3
2つのFPlane平面が交わるか判定し return を返し、交わる場合には交わる直線上の1点 I と直線の向き D を与える IntersectPlanes2
点と直線の距離 PointDistToLine
二次元の2点を結ぶ線分上で他の任意の1点に最近接する点を得る ClosestPointOnSegment2D
点と線分の距離
2乗次元の値を取得できれば事足りる場合は PointDistToSegmentSquared を使う方が速度的に有利 		PointDistToSegment
点と線分の距離の2乗
PointDistToSegment が sqrt を要する分だけこちらの方が高速 		PointDistToSegmentSquared
2つの線分上で互いに最接近となる2点の座標を得る
但し、線分の何れかまたは両方が長さ 0 の場合は正しい結果を得られない。その可能性がある場合は SegmentDistToSegmentSafe を使う。 		SegmentDistToSegment
SegmentDistToSegment の線分の長さが 0 でも正しく計算可能な実装 SegmentDistToSegmentSafe
2点を通る直線が平面と交差する位置を直線の2点に対する比として取得
交差しない場合は -inf が返る
例: 直線 {(0,0,1),(0,0,-1)} を FPlane(0,0,1,0) へ与えた場合、 0.5 が得られる。 		GetTForSegmentPlaneIntersect
線分と平面が交差するか判定し、交差する場合はその座標も与える SegmentPlaneIntersection
線分と三角面が交差するか判定し、交差する場合はその座標も与える SegmentTriangleIntersection
3次元上の2つの線分がXY平面に投影された場合に交差するか判定し、交差する場合はその座標も与える SegmentIntersection2D
三次元の3点からなる三角形稜線上で他の任意の1点に最近接する点を得る ClosestPointOnTriangleToPoint
三次元の4点からなる四面体表面上で他の任意の1点に最近接する点を得る ClosestPointOnTetrahedronToPoint
球に対し1つの点と正規化された方位からなる半直線との交点を計算 SphereDistToLine
コーン形状に点が含まれるか判定 GetDistanceWithinConeSegment
配列で与える点群が同一の平面から一定の距離内にあるか判定 PointsAreCoplanar
偶数丸め RoundHalfToEven
浮動小数点数型の値を小数部の絶対値が 0.5 以上であれば 0 から遠ざかる方向、それ以外の場合は 0 へ近づく方向の整数へ丸める RoundHalfFromZero
浮動小数点数型の値を小数部の絶対値が 0.5 以下であれば 0 へ近づく方向、それ以外の場合は 0 から遠ざかる方向の整数へ丸める RoundHalfToZero
浮動小数点数型の値を 0 から遠ざかる方向の整数へ丸める RoundFromZero
0 方向への丸め RoundToZero
-∞ 方向への丸め RoundToNegativeInfinity
+∞ 方向への丸め RoundToPositiveInfinity
int32値に桁区切りのカンマを付けた文字列を返す
但しバグがあり正の999,999,999以下の値にしか正常な挙動を期待できない
https://goo.gl/sfv5zo 		FormatIntToHumanReadable
4bytesを単位としてメモリー空間に対して書き込みと読み込みを行い成否を判定する MemoryTest
文字列の数式を評価
対応演算子: + - / % * @
対応数値文字: 0..9 と . で構成される実数文字列
括弧: ( )
L"1+2+3-4-5-6*7*8*9" -> -3027
Note: documentation bug 		Eval
ComputeBaryCentric2D の簡易計算実装版
法線計算, 共線のcheckなどを端折っている
O3で1.59倍速程度に速い 		GetBaryCentric2D
三次元の3点のからなる三角形に対し他の任意の1点の重心座標を得る ComputeBaryCentric2D
三次元の4点からなる四面体に対し他の任意の1点の重心座標を得る ComputeBaryCentric3D
値域 [0..1] で表される比 X を一般的なスムーズステップ関数を適用した値を [a..b] へ写像した値を取得
注意: 入力値について clamp 処理を実装していないため [0..1] を超える X に対する clmap された応答を期待してはならない 		SmoothStep
任意の連続したメモリー領域から特定ビットを抽出 ExtractBoolFromBitfield
任意の連続したメモリー領域の特定ビットへ書き出し SetBoolInBitField
FVector で与えるXYZの拡大縮小と float のMagnitude から単一の拡大縮小倍率を float で得る ApplyScaleToFloat
float 型の入力値の値域 [0..1] を uint8 型の出力 [0..255] へ写像 Quantize8UnsinedByte
float 型の入力値の値域 [0..1] を int8 型の出力 [-128..+127] へ写像 Quantize8SinedByte
最大公約数 GreatestCommonDivisor
最小公倍数 LeastCommonMultiplier

UE4/C++er はこれらの実装が FMath にあり、必要に応じて独自に実装する事なく使用可能な事を把握しておくとよい。

（はてなブログの記事あたりの容量制限のため続き §1.9.5 以降は次の記事でどうぞ→Real Unreal Engine C++ 2017-12 (part-4/5) - C++ ときどき ごはん、わりとてぃーぶれいく☆）