算譜記録帳
プログラミングに関して調べたり思いついたりしたことを適当にメモっておくだけのブログ.
2023年3月31日金曜日
証明作法を読んで
2023年2月15日水曜日
プログラマーのためのCPU入門を読んで
プログラマーのためのCPU入門を読みました.
この書籍は,ゲームの土台となるシステムを作っているプログラマーには是非とも読んでもらいたい内容となっています.書いてある内容は10年以上ゲーム業界にいると聞いたことがあったりする内容が多いです.つまり,この本を読むことで何年もかけて学んだような知識を得ることが出来るわけです.
昨今は,ゲーム業界でも専門化が進み,新卒で入社してくる社員には物理学だったり数学だったりの専門家ではあるけれど,情報の教育は受けていない,というような人もいたりします.そういった方たちに高速に動くコードを書いてもらうための助けにもなることでしょう.
第1章では,CPUが命令を順次処理していくことに触れられています.この辺は基本的な知識として是非知っておいてもらいたいレベルですね.
そして,第2章ではパイプラインやスーパースカラなどによって並列実行をすることで高速に実行できるようにすることを解説しています.まずここが分かっていないと,例えばif文は遅いといった話をしても通じないことでしょう.
実際,最近パイプラインという言葉さえも通じないことがあったのでこの書籍を紹介しました.
第3章はデータ依存関係で,例えばある計算の結果を次の計算で使う,というような依存関係がある場合にパイプラインが上手く詰まらず効率が下がるということが解説されています.そのため,実行順序を変更したりして解消することを解説しています.
また,学生時代だと計算量などの話をする場合にはどの処理も一律で扱っていることもあったでしょうが,処理によっては必要な時間が違う,といった話も出ています.これをレイテンシといって,計測するためのサンプルも用意されています.
第4章では,if文のような分岐命令について触れています.分岐は遅い,という話を聞いたことがあるかもしれませんが,これもパイプラインに関係していて,この章を読めば何故遅いのかが理解できることでしょう.
第5章では,キャッシュについて触れています.正直なところ,キャッシュまで考慮して高速化するようなことは,よっぽど中心部分を実装しているような人でないと必要が無いかもしれません.昨今のようにゲームエンジンを利用する場合であればなおさらです.でも,プロファイラなどを見る場合にキャッシュミスが多いというのはどういう意味なのか,といったことを理解するためにも,こういった知識は必要でしょう.
レンダリングプログラマはキャッシュがどうのとしょっちゅう言っている気がします.
第6章では,仮想記憶,特にアドレス変換周りについて触れています.内容としては若干キャッシュの話と近い部分もありつつ,そもそも仮想記憶が当たり前すぎて仮想記憶とは何か分かってない,という方も増えてきているので読んで損はないでしょう.
第7章では,I/O (input / output)について触れます.例えばマウスとかキーボードとかですね.ゲームだとコントローラなんかも含まれます.I/Oは遅いというのはよく聞くんですが,省電力とかコストの関係で意図的に遅くしている,という話は面白かったです.
昔のゲーム専用機のコントローラは今より速かったらしく,ゲームを移植したら反応が遅いってなって,原因を調べると,そもそもコントローラが遅くなっていた,なんてこともありました.
第8章は,システムコールなどOSの機能に関係する部分です.この辺まで考慮するのは本当に根本の部分を担当する人たちだと思いますが,例えばファイルオープンは結構時間がかかるので,複数のデータをまとめてファイルオープンを減らすとか,システムコールが必要な同期の仕組みを減らして速度を上げるといったことは実際に行われているので,何故こんなことをしているのだろう,と思ったときのヒントになることでしょう.
第9章はマルチプロセッサについてです.ここまでくると,ソフトウェアのそもそもの設計なんかが複数のプロセッサを生かせるようになっていないと難しい,というような話になってきます.ゲームなんかは,元々複数の要素を並列で動かして高速化するといったことをしてきているので,この辺は既にフレームワークとして設計に組み込まれているかもしれません.
第10章は,キャッシュコヒーレンス制御です.これは,複数のプロセッサが別々に持っているキャッシュの内容が一致しているようにする,という話です.確実に一致する状態を保とうとすると処理速度が落ちます.実際,その設定をしていたせいで遊べたものではない状態になったことがあります.そう,設定を一か所変えるだけで劇的に改善されたんです.
かといって,場合によってはプロセッサによっては違う値を取ってくるというのは,それはそれでよく分からない問題を引き起こしたりします.
実際にそういったことが起きないように対処するのはシステムの根本を作ってくれている人たちが対応してくれると思いますが,そういったことが起こるってことくらいは知っていて損は無いと思います.
第11章は,メモリオーダーとかメモリ順序付けと言われるものを解説しています.これはこれでやっかいな話で,コード上は順番に書いているのに,実際には違う順序で実行されたりアクセスされた結果,条件が成立したのに成立していないとか謎な状態になったりします.今時のゲームは並列処理が基本でこういった問題もちょくちょく発生しているので,是非とも押さえておいた方が良いでしょう.
第12章は,アトミックとか不可分操作と言われるものを解説しています.CASとかロックフリーとか聞いたことがあるかもしれません.例えば,キューを並列でアクセスすると簡単にクラッシュします.そういったことを防ぐためにも必要な知識なので,是非押さえておきたいところです.
第13章はまとめとして高速なソフトウェアを書く際に注目する点を解説しています.そのあとには,様々な参考文献もまとまっています.
多くの章には簡単な実験で速度の低下や効率化が確認できるコードが付いています.ただし,Linuxを前提としているので,そういった環境を用意できない方はご注意ください.
最後まで書いて,新人への課題図書にしても良いんじゃないかなと思いました.
2023年1月4日水曜日
継続的デリバリーのソフトウェア工学の感想
継続的デリバリーの,となっていますが,読んだ限りでは元のタイトルのModern Software Engineeringを実現する方法として継続的デリバリーも推している,という感じなのかな,という気がします.
序文では,この書籍は次のようなものだと述べています.
ソフトウェア工学に工学を取り戻す試み
つまり,現在のソフトウェア工学は工学になっていない,ということです.正確には,皆が誤解しているというところなのだと思います.実際,この書籍で紹介される多くの概念は過去に提唱されてきたものがほとんどです.
そのための流れとして,まず科学と工学の違い,そしてソフトウェア工学とはどうあるべきなのかが定義されます.そして,工学であるために必要となる学習と複雑さの管理 について説明し,最後にそれらのためのツールというかアイデアを紹介しています.
この書籍が良いところは,既に様々な書籍で紹介されているアイデアを整理し,それらがどう関係しあって良い結果をもたらすのか,ということが具体例も交えつつ解説されている点です.
例えば,テスト駆動開発(Test Driven Development, TDD)を用いると,疎結合な設計になりやすいであるとか,関心事の分離により変更が容易になるとかです.
TDDや継続的インテグレーション(Continuous Integration, CI),継続的デリバリー(Coninuous Delivery, CD)などは,良い設計をする方向への圧力となるのだと.
また,プログラマはどうしても個々人のレベルアップによる開発を夢見がちですが,それでは大規模化が困難であることにも触れています.ある程度の規模のソフトウェア開発に関わっている人ほど,その点については何となくでも気付いていると思います.
TDDとなると,どうしてもテストを書くのが面倒だと言う人は多いのではないでしょうか? しかし,この書籍を読めば,何故TDDが必要なのか,単純に単体テストではダメなのか,という質問をされた場合に返答できるようになると思います.
雑に要約すると,TDDでのテストは仕様を記述しているのであって,バグを検出することが第一の目的ではない,ということです.
他にも色々とありますが,この書籍ではTDDやCI,CD,他にはマイクロサービスやDevOpsなどによってもたらされる利点が語られていますが,そのものについては既知のものとして詳しく触れてはいません.
1つか2つソフトウェアの開発経験を積んだ後,まずはこの書籍を読み,知らない概念についてはそれぞれの参考文献を読む,という読み方をするのが良いと思います.
2020年7月20日月曜日
DirectX12の魔導書を読んで
書評を書くにあたって,軽く自分の経歴を書いておくと,とあるゲームでリードプログラマを務めたり,ゲームエンジンに携わったりしています.
誤解しないで欲しいので最初に言っておきますが,私はこの本は良い本だと思っています.
誰のための書籍か
この本の利点
この本の欠点
手を動かす場合の注意点
自力でエラーを修正するか,プロジェクトのプロパティから,C/C++を選び,言語から準拠モードをいいえに切り替えましょう.
書籍の説明はところどころに抜けがあったりして,以前に設定したパラメータを切り替えておかないと上手く動かない部分があったりします.WinMergeなどのテキスト比較ツールを利用して,サンプルコードの前の章のコードと比較して差分を確認するなどしながら進めましょう.
また,9章ではリファクタリングと言いつつ,大幅な書き換えもあるので,その辺で一度復習しておくのも手です.なお,その関係で9章と8章の差分を取るのは困難というか不可能に近いです.
正誤表やIssue,Twitterなどを活用しよう
文章の間違いを見つけた場合,翔泳社の書籍紹介ページから正誤表に飛ぶことが出来るので,正誤表を確認してみましょう.載っていなければ,気軽に間違いを送ってみましょう.本当に間違いであれば,ちゃんと正誤表に載せてもらえます.また,DirectX12のようにハードウェアに近い処理を扱う場合,利用しているハードウェアやドライバの影響で動かないことなどもあるでしょう.
そういうときは,サンプルコードがGitHubに上がっているので,気軽にIssueとして投げてみましょう.
著者の川野先生は忙しくて対応できないようですが,それを見た他の人が何かしらアクションしてくれるかもしれません.
また,Twitterなどで#DirectX12の魔導書 のタグを付けてつぶやくなどしていると,バグなどがあった場合に,著者であったり経験者の方がサポートしてくれたりします.
最後に
2020年6月25日木曜日
STLのtype_traitsを実装する その2
conjunctionを上手く実装できないか試行錯誤していて,たぶんこれでOKというのが出来たので書いておきます.
conditionalおよびconditional_tの実装
conditionalは,型のif文だと思えば良いでしょう.boolと型Tと型Fを渡すと,boolがtrueのときはtypeとしてTを,falseのときはtypeとしてFが手に入るわけです.template <bool, class T, class F>
struct conditional
{
using type = F;
};
template <class T, class F>
struct conditional<true, T, F>
{
using type = T;
};
template <bool B, class T, class F>
using conditional_t = typename conditional<B, T, F>;
boolの値がtrueの場合を特殊化していますが,デフォルトはtypeがTになって,falseの場合はFになる,と逆にしても問題はありません.
conjunctionおよびconjunction_vの実装
conjunctionは,is_XXX系の型が特定の性質を持っているかを判定するtype traitsに対する論理積になります.通常の論理積と同じく,短絡評価が可能です.
つまり,is_integral_v<float> && is_floating_point_v<float>と書くと,最初のfloatが整数かどうかの判定でfalseになるので,全体としてfalseが決定するので,is_floating_point_v<float>は参照しない,というようなものです.
ただし,ここで問題なのが,&&でtype traitsの結果の論理積を取ってしまうと,参照はしないけれど,テンプレートの実体化は行われている,ということです.
例えば,has_valueというtype traitsがあって,与えられた型TがT::valueというような名前を持つかチェックする場合,has_value<int>が実体化されるとコンパイルエラーになるわけです.しかし,conjunctionを使うと,そういった問題は発生しません.
conjunction<is_floating_point<int>, int>;
最初の時点でfalseになるので,それ以降はテンプレートの実体化が行われず,2つ目のintはint::valueをチェックする,という処理が行われないわけです.
あとは,少しややこしいのが,親となるクラスを決定する方法です.
- conjunction<>と実引数が0の場合,true_typeを継承.
- conjunction<T0, T1, ..., Tn>の場合,Ti::valueがfalseなら,Tiを継承
- conjunction<T0, T1, ..., Tn>の場合,全てのTi::valueがtrueなら,Tn(つまり最後の型)を継承
となるわけです.
というわけで,おそらく次のようになります.
// 実引数が0の場合は,ここで終わる
template <class... B>
struct conjunction : true_type {};
// 実引数が1の場合は,ここで終わる
template <class H>
struct conjunction<H> : conditional_t<static_cast<bool>(H::value), H, H>
{};
// それ以外
template <class H, class... T>
struct conjunction<H, T...> : conditional_t<static_cast<bool>(H::value), conjunction<T...>, H>
{};
template <class... B>
inline constexpr bool conjunction_v = conjunction<B...>::value;
最初の定義は,実引数が0の場合に適用されます.1つの場合,2つ目の定義で::valueを持っているかチェックした上でその型を利用します.
trueでもfalseでも,最後の1つならその型を使うことに変わりはないので,これで問題ないはずです.
3つ目の定義は,2つ以上ある場合で,trueなら残りをチェックし,falseならその型を継承するようにしています.
名前空間myに定義していたとして,次のようなテストをしています.
my::conjunction<my::is_integral<int>> c0;
my::is_integral<int> * pc0 = &c0;
my::conjunction<is_integral<int>, my::is_floating_point<int>> c1;
my::is_floating_point<int> * pc1 = &c1;
my::conjunction<is_integral<int>, my::is_floating_point<int>, int> c2;
my::is_floating_point<int> * pc2 = &c2;
// my::conjunction_v<int>; // コンパイルエラー(int::valueができないため)
static_assert(my::conjunction_v<>);
static_assert(my::conjunction_v<std::is_integral<int>>);
static_assert(my::conjunction_v<std::is_integral<int>, std::is_floating_point<float>>);
static_assert(!my::conjunction_v<std::is_integral<int>, std::is_floating_point<int>>);
// 短絡評価されるので,intを指定していても問題無し
static_assert(!my::conjunction_v<std::is_integral<float>, int>);
clangの実装でもMSVCの実装でも,condtionalを使っていなかったので,もしかしたら何か抜けがあるのかもしれませんが,今のところ上手く動作していそうです.
こういうパターンが網羅できないよ,というのがあれば指摘いただけると助かります.
2020年6月23日火曜日
STLのtype_traitsを実装する その1
これを独自に実装するというのは車輪の再発明になりますが,例えばテンプレートで配列の場合のみ特殊化したい場合,どう書けば良いのか,などテンプレートの書き方について色々と勉強になります.
なお,ここではC++17以降を想定しています.
integral_constantの実装
まず,integral_constantを実装します.これは,type_traitsにある色々な判定系のテンプレートの土台になっています.また,boolの場合に限定したbool_constantエイリアステンプレートや,その値がtrueの場合のtrue_type,false_typeは,型が特定の条件を満たすか判定する際の土台として使います.template <class T, T v>
struct integral_constant {
static constexpr T value = v;
using value_type = T;
using type = integral_constant<T, v>
constexpr operator value_type() const noexcept { return value; }
constexpr value_type operator()() const noexcept { return value; }
};
template <bool B>
using bool_constant = integral_constant<bool, B>;
using true_type = bool_constant<true>;
using false_type = bool_constant<false>;
is_sameおよびis_same_vの実装
次に,2つのテンプレートパラメータの型が同じ場合にtrue,違う場合にfalseとなるvalueを持ったis_sameという型を実装します.また,通常はis_same<X, Y>::valueと書いて値を読み取るところを,C++14以降では,直接読み取れるようにした
is_same_vも追加されているので,そちらも実装します.
template <class T, class U>
struct is_same : false_type {};
template <class T>
struct is_same : true_type {};
template <class T, class U>
inline constexpr bool is_same_v = is_same<T, >::value;
このように,通常はfalse_typeを継承していて,型が同じ場合を特殊化してtrue_typeを継承するようにすることで,valueの値は型が同じときだけtrueになります.
これを実装しておくと,次に実装する,型を変形するtype traitsのテストがしやすくなります.is_sameも,次のようにstatic_assertを利用してテストしておきましょう.
static_assert(is_same_v<int, int>);
static_assert(!is_same_v<int, const int>);
本当は,もっと色々なパターンをテストしておいた方が良いでしょうが,その辺は実装する際に色々考えてみると良いでしょう.
remove/add系の実装
次に,型を変形するtype traitsを実装します.何故かというと,その型が何なのかを判定するis_XXX系のtype_traitsではconstなどは無視するケースも多々あり,そこでこれから実装するremove_constなどを利用するからです.
これらの型を変形するtype traitsには,typeという名前で変形後の型にアクセスできます.
まずは,constを取り除くremove_constを実装しましょう.また,typeに直接アクセスできるremove_const_tも実装します.
template <class T>
struct remove_const
{
using type = T;
};
template <class T>
struct remove_const
{
using type = T;
};
template <class T>
using remove_const_t = typename remove_const<T>::type;
エイリアステンプレートでtypeと取り出す際には,typenameが必要です.
逆に,constを付けるadd_constの実装はシンプルです.
template <class T>
struct add_const
{
using type = const T;
};
template <class T>
using add_const_t = typename add_const<T>::type;
constで無い型にはconstが付き,既にconstな型なら追加のconstは無視されるんですね.
では,テストを書いておきましょう.
static_assert(is_same_v<remove_const<int>, int>);
static_assert(is_same_v<remove_const<const int>, int>);
static_assert(is_same_v<remove_const<const int *>, const int *>);
static_assert(is_same_v<remove_const<const int * const>, const int *>);
本当は,もう少し色々書くべきですが,省略します.ここで注目すべきは,ポインタの場合,constはポインタに対して付いているものが取り除かれる,ということです.
const int *がint *になると思った方もいるかもしれませんが,そうはなりません.
こんな感じで,独自のtype_traitsを実装していきます.
remove_constとadd_constのconstをvolatileに置き換えるだけで,remove_volatileとadd_volatileが作れます.
この2つを組み合わせれば,remove_cvやadd_cvが作れます.
その2は……気が向いたら書きます.
2020年5月20日水曜日
C++ Templates - The Complete Guide, 2nd 読書メモ 2章 クラステンプレート
スタックの実装を例にクラステンプレートについて解説している.
クラステンプレートの宣言
関数テンプレートと同様に,templateの後にテンプレート仮引数を並べ,クラス宣言を書く.
template <typename T>
class Stack {
...
};
クラステンプレート内では,Tを型として利用できる.
コピーコンストラクタなどを書く場合,次の2通りの書き方があるが,敢えて書くと意味があるように思わせるので,前者の方が良い.
Stack(const Stack &);
Stack(const Stack<T> &);
メンバ関数の実装
クラステンプレートのメンバ関数を実装する方法として,クラスの外側で定義する方法とクラス内で定義する方法が紹介されている.
ついでに,例外安全についても触れていて,Exceptional C++が紹介されている.
クラステンプレートの利用
基本的には,クラステンプレートを利用する場合は型を明示する必要があるが,C++17では型を省略する方法が追加され,後ほど解説する,とある.
また,呼び出されたテンプレート(メンバ)関数のみがインスタンス化される,とある.
friend
フレンド関数を定義するには,クラス内で宣言してしまう方法と,後から別途宣言する方法が2つ紹介されている.
template <typename U>
friend std::ostream & operator<<(std::ostream &, const Stack<U> &); // 別途非メンバ関数として定義する
template <typename T>
class Stack; // 前方宣言
template <typename T>
std::ostream & operator<<(std::ostream &, const Stack<T> &);
template <typename T>
class Stack {
friend std::ostream & operator<< <T>(std::ostream &, const Stack<T> &);
};
テンプレートの特殊化
template <>として,クラス名の後に具体的な型を指定して定義することで,特定の型の場合について専用の実装を用意することができる.
例としては,std::vector<bool>など.
例えば,typename Tに対して,T *,とポインタ型にするような部分的な特殊化も可能.
デフォルト実引数
関数テンプレートと同様に,テンプレート仮引数にデフォルト実引数を指定することが可能.
タイプエイリアス
typedefのように型の別名を定義する方法として,usingによるエイリアス宣言が紹介されている.
typedefよりも = でつなぐ分,読みやすい,とも.
また,エイリアスはテンプレートにもできる.
template <typename T>
using DequeStack = Stack<T, std::deque<T>>;
C++14以降では,標準ライブラリでは 型とレイトである型から他の型を取り出す場合,今まではA::typeとしていたのを,A_tというようなエイリアスが用意された.
クラステンプレート実引数推論
C++17から,初期化時の実引数からクラステンプレートの型を推論できるようになった.使い方次第では便利なのだろうけれど,使いこなせない気がする.
文字列を利用して推論する場合の注意点についても触れている.コンストラクタが参照を受け取るようになっていると,文字列から推論しようとするとconst char [x]のような型になってしまうが,値渡しにしていると,const char *になる.
推論ガイド(deduction guide)についてもサラッと触れている.
テンプレート化された集成体
ユーザー定義または継承したコンストラクタを持たず,privateやprotectedな非staticメンバを持たず,仮想関数,仮想またはprivateまたはprotectedなベースクラスを持たないクラスまたは構造体をテンプレートにすることもできる.