fmt(cppformat)の紹介と、実装を一部読んでみる

これは ドリコム Advent Calendar 2017 の１日目です。

エンジニアの中島です。普段、C++でゲームクライアントを書いています
普段お世話になっているライブラリの、fmt(cppformat)の紹介と、その一部を読んでみました

fmtとは

http://fmtlib.net/latest/index.html

リポジトリ: https://github.com/fmtlib/fmt

fmt is an open-source formatting library for C++. It can be used as a safe alternative to printf or as a fast alternative to IOStreams.

fmt(cppformatと呼ばれることもありますが、以下fmtとします)

はその名の通り、文字列をフォーマットするためのライブラリです

使い方

Docより

std::string s = fmt::format("{0}{1}{0}", "abra", "cad");
// s == "abracadabra"

{}を用いた形式で記載した文字列に、引数で渡した文字列をフォーマットして埋め込みます

メリット

• 使い方を誤ると危険なstdio, 記法が冗長になりがちなostreamを使うことなく、
  シンプルにフォーマッティングができる
• パフォーマンスが良い

例えばfmt::printについてREADMEとベンチマークより

Library	Method	Run Time, s
EGLIBC 2.19	printf	1.30
libstdc++ 4.8.2	std::ostream	1.85
fmt 1.0	fmt::print	1.42
tinyformat 2.0.1	tfm::printf	2.25
Boost Format 1.54	boost::format	9.94

と、さすがにprintfよりは遅いですが、std::ostreamより高速です
他の類似ライブラリと比較してもパフォーマンスが良いです

実プロダクトでの適応例

例えば、

<resources>
<string name="cast_spell">{character_name}は{spell_name}を唱えた！</string>
</resources>

のようなリソースデータを用意しておいて

std::string text
= fmt::format(R::string::get("cast_spell"),
fmt::arg("character_name", caster->get_name()),
fmt::arg("spell_name", casted_spell->get_name()));
text_window->set(text);

のような動的テキスト組み立てに利用したり、

std::string sql
= fmt::format("SELECT * FROM enemies WHERE id IN ({}) ORDER BY id",
fmt::join(master_enemy_ids.begin(), master_enemy_ids.end(), ","));

のようなクエリ組み立てとかに利用することができます

その他、数字の0詰め、アラインメントといった各種フォーマッティング機能など、
欲しいと思うところは一通り揃っています。

公式リファレンスにもAPIは解説されていますが、fmtはGoogleTestでテストが書かれており、そこを読めば一通りの使用方法が把握できます

https://github.com/fmtlib/fmt/tree/master/test

実装の一部を読んでみる

tl;dr

• 基本的には素直愚直、だけど最適化テクニックをしっかり盛り込んでいる
• １文字+後方１文字を順に見ていき、現れるトークンごとにswitchしていくオーソドックスな実装
  • 確定した文字からBuffer<Char>へ溜め込む
• CRTPを用いてポリモーフィズムを実現
  • virtual / override より早いので、パフォーマンスを求める際有用
  • https://eli.thegreenplace.net/2013/12/05/the-cost-of-dynamic-virtual-calls-vs-static-crtp-dispatch-in-c/
• intをasciiへ変換は、特別な計算＋ルックアップテーブルを用いて変換する最適化がある
  • https://www.slideshare.net/andreialexandrescu1/three-optimization-tips-for-c
  • ↑他にも為になる最適化情報がありおすすめ

詳細

<

p class=”p1″>全てを詳細に追っていくとキリがないので、fmt::format関数を例に、
所々ピックアップして紹介いたします

https://github.com/fmtlib/fmt/blob/493586cbca340e631e7d68a3e8ade41016783d34/fmt/format.h#L4012

template <typename Char, typename AF>
void BasicFormatter<Char, AF>::format(BasicCStringRef<Char> format_str) {
const Char *s = format_str.c_str();
const Char *start = s;
while (*s) {
Char c = *s++;
if (c != '{' && c != '}') continue;
if (*s == c) {
write(writer_, start, s);
start = ++s;
continue;
}
if (c == '}')
FMT_THROW(FormatError("unmatched '}' in format string"));
write(writer_, start, s - 1);
internal::Arg arg = internal::is_name_start(*s) ?
parse_arg_name(s) : parse_arg_index(s);
start = s = format(s, arg);
}
write(writer_, start, s);
}

fmt::formatの第一引数について実行される、フォーマット対象のブラケットパース処理の入り口です。
文字列に対して１文字と、その１つ先のCharを順次見て、特定のトークンパターンで分岐していくという
オーソドックスな構文処理となっています

if (*s == c) {

部で、

if (c != '{' && c != '}') continue;

の前提と合わせ、{トークンのネストについての処理を記載しているのは成る程と思いました

さらに読み進めて、

start = s = format(s, arg);

のformat関数について見てみます

https://github.com/fmtlib/fmt/blob/493586cbca340e631e7d68a3e8ade41016783d34/fmt/format.h#L3839

template <typename Char, typename ArgFormatter>
const Char *BasicFormatter<Char, ArgFormatter>::format(
const Char *&format_str, const internal::Arg &arg) {
// 長いので以下割愛

コロンをもちいたalignmentやprecisionなど、spec指定記法のパース処理を行っています
ここもオーソドックスに１文字づつ見ていって、トークンごとに処理をswitchする作りとなっています
トークンによって

typename ArgFormatter::SpecType spec;

にspec情報をメンバ変数、フラグなどとして記憶しています

最終的にこれまでパースされてきた情報は

ArgFormatter(*this, spec, s - 1).visit(arg);

で処理されます

ArgFormatterについて、1つの実装を見てみると
https://github.com/fmtlib/fmt/blob/493586cbca340e631e7d68a3e8ade41016783d34/fmt/format.h#L2240

/**
\rst
An argument formatter based on the `curiously recurring template pattern
<http://en.wikipedia.org/wiki/Curiously_recurring_template_pattern>`_.
// -略
*/
template <typename Impl, typename Char, typename Spec = fmt::FormatSpec>
class BasicArgFormatter : public internal::ArgFormatterBase<Impl, Char, Spec> {

C++の実装イディオムの一つ、CRTPが用いられています
自身の型を基底クラスのテンプレート引数として渡して、
その基底クラスからstatic_castを通して静的に仮想関数的な実装をするテクニックです

fmtは高速なことも売りとしているため、パフォーマンスをキープしつつ、
interface的ポリモーフィズム実装を実現するためでしょう
CRTPの詳細と、virtual/overrideで実装した時とのパフォーマンス差は以下がよくまとまっていてお勧めです

https://eli.thegreenplace.net/2013/12/05/the-cost-of-dynamic-virtual-calls-vs-static-crtp-dispatch-in-c/

本題に戻り、ここからさらにargの型によって処理が分岐されていくので、個別ケースを例にとってもう少し追ってみます

intの場合、ArgVisitor::visit_any_int()のインターフェースをコールし、その、ArgFormatterBase実装はさらに

https://github.com/fmtlib/fmt/blob/493586cbca340e631e7d68a3e8ade41016783d34/fmt/format.h#L3004

void BasicWriter<Char>::write_int(T value, Spec spec) {

を呼び出します。
ここでもトークンによって進数記法を見分け、パース処理を実行しているのが確認できます
ここもすべて追っていると分量がえらいことになるので、１０進数の場合の処理について追ってみます

最終的にコードを追っていくと、intをCharバッファへため込むのは以下の関数となります
https://github.com/fmtlib/fmt/blob/493586cbca340e631e7d68a3e8ade41016783d34/fmt/format.h#L1080

template <typename UInt, typename Char, typename ThousandsSep>
inline void format_decimal(Char *buffer, UInt value, unsigned num_digits,
ThousandsSep thousands_sep) {
buffer += num_digits;
while (value >= 100) {
// Integer division is slow so do it for a group of two digits instead
// of for every digit. The idea comes from the talk by Alexandrescu
// "Three Optimization Tips for C++". See speed-test for a comparison.
unsigned index = static_cast<unsigned>((value % 100) * 2);
value /= 100;
*--buffer = Data::DIGITS[index + 1];
thousands_sep(buffer);
*--buffer = Data::DIGITS[index];
thousands_sep(buffer);
}
if (value < 10) {
*--buffer = static_cast<char>('0' + value);
return;
}
unsigned index = static_cast<unsigned>(value * 2);
*--buffer = Data::DIGITS[index + 1];
thousands_sep(buffer);
*--buffer = Data::DIGITS[index];
}

DIGITSの実態は

https://github.com/fmtlib/fmt/blob/493586cbca340e631e7d68a3e8ade41016783d34/fmt/format.cc#L262

template <typename T>;
const char internal::BasicData<T>::DIGITS[] =
"0001020304050607080910111213141516171819"
"2021222324252627282930313233343536373839"
"4041424344454647484950515253545556575859"
"6061626364656667686970717273747576777879"
"8081828384858687888990919293949596979899";

イミガワカラナイ

ので取っ掛かりとしてコメントに記載してある、
Three Optimization Tips for C++を調べてみると、以下のスライドでした
https://www.slideshare.net/andreialexandrescu1/three-optimization-tips-for-c

スライド35ページ目に同等の実装が記載されています。

ここに書かれている計算を行い、このテーブルを用いるとintからasciiへの変換が少ない命令数で可能になるようです。すごい。

また、このスライドはエンジニアリングでよく言われる、計測せよ　という金言や、
数値計算の際の型の使い分け(21ページ~)など、為になる情報が沢山記載されていて勉強になります

まとめ

ざっくり部分的＆駆け足ですが、fmt(cppformat)の使い方と、どのような実装がされているかのほんの一部を紹介させていただきました。

APIが直感的で使いやすく、ゲームのような大量のstring処理を行う必要があるプロジェクトに速度面からもお勧めできる＆実績もあるライブラリです。

また、ごく一部、intの一つの進数表記パース処理を読むだけでも、実際に用いられている最適化テクニックを学ぶことができ、非常にためになります。

普段使われているライブラリの実装を読むことは、実務につながるところもあり、コーディングの参考にもなり、大変ですがとても面白いです。