本の虫

著者:江添亮
ブログ: http://cpplover.blogspot.jp/
メール: boostcpp@gmail.com
Twitter: https://twitter.com/EzoeRyou
GitHub: https://github.com/EzoeRyou

アマゾンの江添のほしい物リストを著者に送るとブログ記事のネタになる

筆者にブログのネタになる品物を直接送りたい場合、住所をメールで質問してください。

歌舞伎座.tech #8 「C++初心者会」を開催した

歌舞伎座.tech#8「C++初心者会」 - connpass

5月17日に、歌舞伎座.thch #8 「C++初心者会」を開催した。

今回は、勉強会の初心者が発表できる場を設けようという意図から、発表枠には、初心者枠とガチ枠を設けた。これにより初心者が積極的に発表しやすくなるはずだ。さて、問題は参加者と発表者が集まるかどうかだ。いざフタを開けてみると閑古鳥が鳴いているようでは極めて痛い。

さて、connpassで告知と募集を開始すると、参加枠が即座に埋まっていく。どうやら勉強会の需要はあるようでまずは一安心だ。発表枠も埋まり始めたが、その参加者を見ると、どうも、技術的、勉強会的にみて、初心者とは思われない。

さて、公開直後の参加申し込みの波がひけてみると、参加枠と初心者枠は埋まっているものの、ガチ枠が埋まらない。どうやら、みなチョットデキル的な謙遜精神を発揮してしまったようだ。仕方がないので、ガチ枠をクソザコ枠に改名した。するとすぐに発表者で埋まった。しかし、発表者のプロフィールと発表タイトルをみると、どうもザコとも思われない。

さて、当日、

Eigenでオンライン機械学習アルゴリズムを実装したときの話

C++初心者ではあるのかもしれないが、機械学習の初心者ではない人間が発表した。C++に関係のある部分としては、行列計算ライブラリとして、Boost.UBLASは使い勝手が悪く、Eigenの方がパフォーマンスも使い勝手もよいとのことだ。

Seastar 高スループットなサーバアプリケーションの為の新しいフレームワーク

C++初心者ではあるのかもしれないが、カーネル開発の初心者ではない人間が発表した。Seastarとは、カーネルではなくユーザーランドでネットワークスタックを実装して高パフォーマンス化を図るものだ。ネットワークスタックをユーザーランドで実装する利点として、カーネルからユーザーへのメモリコピーが省けるとのことだ。

なるほど、これが必要になるのはどういう状況だろうか。100GbpsのNICが出たら話は変わるのかもしれないが。

Improving Linux networking performance [LWN.net]

Seastarの提供するfutureがthenをサポートしているのも興味深かった。これはC++標準化委員会にconcurrency TSとして提案されている機能だ。そういう意味で、この発表者には是非ともC++標準化委員会に出てきて知見を上げてほしいものだ。

Boost.Asioで可読性を求めるのは間違っているだろうか

果たしてC++初心者はBoost.Asioを使えるのだろうか。Boost.AsioはC++標準化委員会で、ネットワーキングライブラリとしてTSに提案されている。既存のネットワークライブラリで、標準化委員会で合意に達することができるものは、Asioぐらいしかないであろうが、日本の標準化委員会の中では、Asioは使いづらいという意見が出ている。

Boost.Spirit.QiとLLVM APIで遊ぼう

果たして初心者がExpression Templatesの悪用の最たる例であるBoost.Spiritと、LLVM APIを使うだろうか。ただし、便利なライブラリのおかげで、コード自体はとても短く綺麗だった。

任意の文をマングリングすることができないクソザコなのでconstexprラムダをライブラリで作った

lambda式のクロージャーオブジェクトのoperator ()がconstexprではないのは、もし仮にそうであると、lambda式がSFINAEの文脈で使えてしまうので、任意の文のsubstitutionに成功するかどうかを判定する、極めて強力な悪用ができてしまう。その機能を実現するためには、任意の文を型としてマングリングしなければならない。そのような機能は、抜け穴的な技法ではなく、コンセプトのような、その目的のために特別に設計された機能で実現すべきだ。

発表者は、Boost.LambdaのようにExpression Templatesを悪用して、コンパイル時に評価できるlambda式風のDSLをC++上に実装していた。これがザコのすることだろうか。

Haskellを書きたい人生だった

C++でExpression Templatesを悪用して、Haskell風のDSLを実装した話。ソースコードがまるでC++ではない上に、初心者のすることではない。

文字列とC++

これは初心者らしい発表だった。C++を学ぶときに引っかかった落とし穴をいくつか解説している。

ロボティクスとC++

Pythonを褒め称える発表だった。

私が市販のロボットのプログラミング環境に思うことは、バイナリブロブでの配布が多すぎるということだ。そのプログラミング環境は、10年後に維持できない。使い捨てである。そんな使い捨て文化では、一向にソフトウェア資産がたまらない。発表者は個別に差異を吸収するレイヤーライブラリを書いて、自分のコードはその上に書けばよいと主張したが、そういう互換レイヤーは、個人個人で独立して書かれるので、一向にソフトウェア資産がたまらず、ロボット開発の未来は暗い。

不自由ソフトウェアは長期的な利益をもたらさないので根本的に価値がない。

クソ雑魚がC++のウェブフレームワークを食い散らかした話

巷に転がっているC++で書かれたWebフレームワークをいくつか試してみたという発表。

ビルドするのが極めて困難なフレームワークが多いという話だった。ビルド可能性はとても重要で、まともなシステム管理者がドキュメントを読んで数行のコマンドを入力するだけでビルドできるようにしておくべきだ。

大学でC++03を教わった私が、便利そうだと思ったC++11の新機能

これも初心者らしい話。聞説、発表者の大学では、この2015年に大昔の化石規格であるC++03を教えて、それで学位を与えているようだ。日本の教育機関は10年ほど前からC++標準化委員会と関わらなくなっているため、もはや日本の教育機関に最新のC++規格をまともに把握している人間はいない。そのため、C++11を教育できる人間がいないのだろう。

この2015年にC++03しか教育できない教育者しかいない大学というのは何なのだろうか。しかも発表者によると、教育内容には規格上の誤りが多かったという。

Visual C++で始めるOpenCV

OpenCVという画像認識ライブラリの概要を説明する発表のようだった。

組み込み向けC++のやり方を探る

あまり内容を覚えていない。

なぜC++は組み込みに採用されにくいのか

C++はどのようなコードに落とし込まれるか人間が手動で推測しにくいので組み込みには向かないという発表であった。

virtual関数の実装方法として主流なvtableによるクラスオブジェクトのサイズ増加や、関数のオーバーロードをされるとその処理コストがコードを見ただけではわからないという話。

これは疑問で、Cでも実行時に決まる情報を元に分岐処理を行えば、vtable文のメモリ消費量増加はあるので同じだ。

関数のオーバーロードでコストを見積もれないというのも不思議だ。組み込みの分野では、何度も行う処理を関数という単位に分割しないのであろうか。

class Something { } ;
Something plus( Something const &, Something const & ) ;
Something operator + ( Something const &, Something constg & ) ;

のようなライブラリがあったとして、

Something c = plus( a, b ) ;

と書くのと、

Something c = a + b ;

と書くのとで、その処理コストを手動で見積もる難易度に差があるとは思われない。

発表者は、C++標準化委員会は組み込みでも使えるC++のサブセットを定義すべきであると主張したが、それはC++を分断するだけである。C++を分断すると、利用者も分断される。それは適切ではない。C++標準化委員会はC++のサブセットの定義は行わない方針である。

C++でHello worldを書いてみた

これは一見すると実に初心者らしい、微笑ましいタイトルだ。しかし、ホットペプシと名乗るこの発表者のプロフィールを確認すると、競技プログラマーであるという。発表者の最近解いた問題を少し見るだけでも、もはやこの発表者はHello worldやFizzBuzzを書いて正しく動いたことを確認して喜ぶレベルはとっくに過ぎ去っていることが明らかである。

以下がhello worldのC言語のコードである。

_[]={
'('-'!'|((','-' ')<<('$'-' '))|(('$'-' '|(('$'-' ')<<('$'-' ')))<<('('-' '))|(('$'-' '|(('#'-'!')<<('$'-' '))|((('/'-' ')<<('$'-' '))<<('('-' ')))<<('='-'-'))
,'('-' '|(('$'-' ')<<('$'-' '))|(('%'-' '|(('&'-' ')<<('$'-' ')))<<('('-' '))|((','-' '|(('&'-' ')<<('$'-' '))|((','-' '|(('&'-' ')<<('$'-' ')))<<('('-' ')))<<('='-'-'))
,'('-'!'|((','-' ')<<('$'-' '))|(('$'-' '|(('$'-' ')<<('$'-' ')))<<('('-' '))|(('$'-' '|(('#'-'!')<<('$'-' '))|(('$'-' '|(('/'-' ')<<('$'-' ')))<<('('-' ')))<<('='-'-'))
,'/'-' '|(('&'-' ')<<('$'-' '))|((','-' '|(('#'-'!')<<('$'-' ')))<<('('-' '))|((('#'-'!')<<('$'-' ')|(('('-'!'|(('('-'!')<<('$'-' ')))<<('('-' ')))<<('='-'-'))
,'('-'!'|((','-' ')<<('$'-' '))|(('$'-' '|(('$'-' ')<<('$'-' ')))<<('('-' '))|(('$'-' '|(('#'-'!')<<('$'-' '))|(('('-' '|(('/'-' ')<<('$'-' ')))<<('('-' ')))<<('='-'-'))
,'/'-' '|(('&'-' ')<<('$'-' '))|(('#'-'!'|(('('-'!')<<('$'-' ')))<<('('-' '))|((','-' '|(('&'-' ')<<('$'-' '))|(('$'-' '|(('&'-' ')<<('$'-' ')))<<('('-' ')))<<('='-'-'))
,'&'-' '|(('&'-' ')<<('$'-' '))|(('('-'!'|((','-' ')<<('$'-' ')))<<('('-' '))|(('$'-' '|(('$'-' ')<<('$'-' '))|(('$'-' '|(('#'-'!')<<('$'-' ')))<<('('-' ')))<<('='-'-'))
,','-' '|(('/'-' ')<<('$'-' '))|((!!""|(('#'-'!')<<('$'-' ')))<<('('-' '))|(('*'-' '|(('*'-' '|(('+'-' ')<<('$'-' ')))<<('('-' ')))<<('='-'-'))
,'.'-' '
,'('-' '|(('$'-' ')<<('$'-' '))|(('+'-' '|(('+'-' ')<<('$'-' ')))<<('('-' '))|((!!"")<<('='-'-'))
,('+'-' '|(('.'-' ')<<('$'-' '))|((')'-' '|((!!"")<<('$'-' ')))<<('('-' ')))<<('='-'-')
,('('-' '|(('$'-' ')<<('$'-' '))|(('-'-' '|(('('-' ')<<('$'-' ')))<<('('-' ')))<<('='-'-')
,'$'-' '|(('('-'!')<<('$'-' '))|(('$'-' '|(('#'-'!')<<('$'-' ')))<<('('-' '))|((('/'-' ')<<('$'-' ')|(('/'-' '|(('+'-' ')<<('$'-' ')))<<('('-' ')))<<('='-'-'))
,!!""
,')'-' '|(('('-' ')<<('$'-' '))|(('('-' '|(('/'-' ')<<('$'-' ')))<<('('-' '))|(('/'-' '|(('%'-' ')<<('('-' ')))<<('='-'-'))
,!!""|(('#'-' ')<<('$'-' '))|(('/'-' '|(('/'-' ')<<('$'-' ')))<<('('-' '))|(('('-' '|(('+'-' ')<<('$'-' '))|((','-' '|(('#'-' ')<<('$'-' ')))<<('('-' ')))<<('='-'-'))
,(('/'-' ')<<('('-' '))<<('='-'-')
,'%'-' '|(('-'-' '|(('('-' ')<<('$'-' ')))<<('('-' '))|((','-' '|(('$'-' ')<<('$'-' '))|(('$'-' '|(('#'-'!')<<('$'-' ')))<<('('-' ')))<<('='-'-'))
,('/'-' ')<<('$'-' ')|(('('-' '|(('+'-' ')<<('$'-' ')))<<('('-' '))|(('$'-' ')<<('='-'-'))
,('-'-' '|((','-' ')<<('$'-' '))|((('('-' ')<<('$'-' '))<<('('-' ')))<<('='-'-')
,!!""|(('#'-' ')<<('$'-' '))|(('+'-' '|(('-'-' ')<<('$'-' ')))<<('('-' '))|(('('-' '|(('+'-' ')<<('$'-' '))|((!!"")<<('('-' ')))<<('='-'-'))
,(('-'-' '|((','-' ')<<('$'-' ')))<<('('-' '))<<('='-'-')
,('('-' ')<<('$'-' ')
};

このコードは、_という名前のint型の配列を定義している。その配列は.textセクションに配置される。配列のビット列は、x86とx86-64において"Hello, world!"と出力するものである。あとはプログラムのエントリーポイントを_startではなく_にしてリンクしてやれば、プログラムを実行するとこのビット列を実行しようとし、結果としてhello worldが出力される

このコードは、記号のみを使っている。アルファベットや数字は一切使っていない。ではどうやって、任意の数値を表現するのか。記号文字を使えるということは、たとえば'-'とか'$'のような文字リテラルを使うことができる。文字コードを限定すれば、その値はわかる。あとは、ビット演算を用いて任意の値に変えてやればいいだけだ。

_[]={ // 名前_の暗黙のint型の配列の宣言
'('-'!'|((','-' ')<<('$'-' ')) // 0xC7
    |
(('$'-' '|(('$'-' ')<<('$'-' ')))<<('('-' ')) // 0x44
    |
(('$'-' '|(('#'-'!')<<('$'-' ')) // 0x24
    |
((('/'-' ')<<('$'-' '))<<('('-' ')))<<('='-'-')) // 0xF0
,... 

// F0 24 C7 44
// mov dword ptr[esp-16], imm

もちろん、これを手で生成するのはダルいので、これを生成するコード、hello_gen.ccを書く。

#include <iostream>
#include <string>

using namespace std;

template <unsigned int n> struct Symbolizer {
	string s;
	Symbolizer() {
		if (n >= 0x10000) {
			s = "(" + Symbolizer<(n >> 16)>().s + ")<<(" + Symbolizer<16>().s + ")";
			if (n & 0xffff) {
				s = Symbolizer<(n & 0xffff)>().s + "|(" + s + ")";
			}
		} else if (n >= 0x100) {
			s = "(" + Symbolizer<(n >> 8)>().s + ")<<(" + Symbolizer<8>().s + ")";
			if (n & 0xff) {
				s = Symbolizer<(n & 0xff)>().s + "|(" + s + ")";
			}
		} else if (n >= 0x10) {
			s = "(" + Symbolizer<(n >> 4)>().s + ")<<(" + Symbolizer<4>().s + ")";
			if (n & 0xf) {
				s = Symbolizer<(n & 0xf)>().s + "|(" + s + ")";
			}
		} else {
			s = "(" + Symbolizer<(n >> 1)>().s + ")<<(" + Symbolizer<1>().s + ")";
			if (n & 1) {
				s = Symbolizer<1>().s + "|(" + s + ")";
			}
		}
	}
};

template <> Symbolizer<0>::Symbolizer() { s = "!\"\""; }
template <> Symbolizer<1>::Symbolizer() { s = "!!\"\""; }
template <> Symbolizer<2>::Symbolizer() { s = "'#'-'!'"; }
template <> Symbolizer<3>::Symbolizer() { s = "'#'-' '"; }
template <> Symbolizer<4>::Symbolizer() { s = "'$'-' '"; }
template <> Symbolizer<5>::Symbolizer() { s = "'%'-' '"; }
template <> Symbolizer<6>::Symbolizer() { s = "'&'-' '"; }
template <> Symbolizer<7>::Symbolizer() { s = "'('-'!'"; }
template <> Symbolizer<8>::Symbolizer() { s = "'('-' '"; }
template <> Symbolizer<9>::Symbolizer() { s = "')'-' '"; }
template <> Symbolizer<10>::Symbolizer() { s = "'*'-' '"; }
template <> Symbolizer<11>::Symbolizer() { s = "'+'-' '"; }
template <> Symbolizer<12>::Symbolizer() { s = "','-' '"; }
template <> Symbolizer<13>::Symbolizer() { s = "'-'-' '"; }
template <> Symbolizer<14>::Symbolizer() { s = "'.'-' '"; }
template <> Symbolizer<15>::Symbolizer() { s = "'/'-' '"; }
template <> Symbolizer<16>::Symbolizer() { s = "'='-'-'"; }

int main(int argc, char* argv[])
{
	cout << "_[]={" << endl;
#include "numbers.cc"
	cout << "};" << endl;
	return 0;
}

さて、.textセクションに書くバイナリ列はどのように生成するのか。これはhello_gen_gen.ccで、xbyakというライブラリを使って生成している。

#include <string>
#include <iostream>
#include <cstring>
#define XBYAK32
#include "xbyak/xbyak.h"

class PutString: public Xbyak::CodeGenerator {
	void syscall() { db(0x0F); db(0x05); }
	void int80h() { db(0xCD); db(0x80); }
public:
	PutString(const std::string &message) {
		unsigned int *data = (unsigned int *)message.data();
		mov(dword[esp - 16], data[0]);
		mov(dword[esp - 12], data[1]);
		mov(dword[esp - 8], data[2]);
		mov(word[esp - 4], data[3]);
		mov(edx, message.length());
		dec(eax);
		mov(ebx, 1);
		jmp("@f");
		add(byte[eax], al);
		dec(eax);
		lea(esi, ptr[esp - 16]);
		mov(edi, 1);
		mov(eax, edi);
		syscall();
		xor(edi, edi);
		mov(eax, 60);
		syscall();
L("@@");
		lea(ecx, ptr[esp - 16]);
		mov(eax, 4);
		int80h();
		xor(ebx, ebx);
		mov(eax, 1);
		int80h();
	}
};

int main(int argc, char * argv[])
{
	PutString put_string("Hello, world!\n");
	unsigned int *bin = put_string.getCode<unsigned int *>();
	size_t dwords = (put_string.getSize() + 3) / 4;
	std::string delim = "";
	for (size_t i = 0; i < dwords; ++i) {
		std::cout << "cout << " + delim + "Symbolizer<" << std::dec << bin[i] << "U>().s << endl;";
		std::cout << "  // " << std::hex << bin[i];
		std::cout << std::endl;
		delim = "\",\" + ";
	}
}

また、生成するビット列は、面白い工夫をすることで、x86, x86-64どちらでも動くようになっている。

実際にコードを入手して手元で動くことを確認したので、認めるしかない。

https://github.com/firewood/test

https://github.com/herumi/xbyak

ツール系で「BiiCodeとCLion」

あまり覚えていない。パッケージマネージャーはOSが提供すべきだ。

不遇の標準ライブラリ

valarrayの話。

Nicolai Josuttisが参考書に書いていたのだが、valarrayは標準化の途中で作者が途中で抜けたが、そのまま残ってしまったものらしい。標準ライブラリなので、ベクトル型としてコンパイラーが認識すれば最適化できるが、既存のほとんどの実装はvalarrayをベクトル型と認識した最適化をしない。

ベクトル計算は、Expression Templatesによる最適化に研究が向かってしまったので、型情報としてのベクトル型は放置されてしまった。

ただし、コンパイラーの最適化技術は進んだので、今ベクトル型として認識すれば、かなりいいコードが生成できる。現にiccはvalarrayをそれなりに最適化する。

ただし、ベクトル型を定義するのであれば、今新たに設計したほうがいい設計になるだろうから、やはりvalarrayに価値はない。

unique_ptrにポインタ以外のものを持たせる時

std::unique_ptrはカスタムデリーターにネストされた形名pointerを定義すれば、ポインター以外のものも管理できそうだが、既存の実装はnullptrと比較していたりして結局動かなかった。

C++標準化委員会には汎用RAIIラッパーが提案されている。

その後、22時頃まで一部の参加者が残って雑談したあと、解散した。

後片付けをした筆者が職場の自席に戻ると、日曜日なのに同僚のtayamaがいた。こんなに夜遅くに休日出勤なのだろうか。話しかけてみると、そうではなく、単に職場近くを通りかかったので、ついでに寄って、アニメを鑑賞しているだけだという。

勉強会で競技プログラマーがすごいhello worldを書いていたという話に及び、そのついでに、AtCoderで問題開示後3秒でコードを提出して通った猛者がいるという話をした。chokudai氏によれば、「問題の流出は確認されていない」という声明を出すに及んだという。

その場で調べてみると、3秒で提出されたコードは以下のものであった。

Submission #286413 - AtCoder Regular Contest 030 | AtCoder

問題は以下の通り。

A: 閉路グラフ - AtCoder Regular Contest 030 | AtCoder

n個の頂点からなる閉路グラフがあって、その頂点のいくつかを取り除くことでグラフを分断し、最終的にk個の連結成分のみが残るグラフにできるかという問題である。

問題文が意図的に難しく書かれているが、解法は、実際にグラフを生成して操作する必要はなく、単に\(k < \frac{n-1}{2}\)の場合は"YES"を、そうでなければ"NO"を出力すればいいだけだ。

問題開示後3秒でコードを提出したので、もはや人間業ではない。AtCoderにログインしてページをダウンロードしてコードを生成してアップロードするまですべてが自動化されている。どうやら、問題文は無視して、入力と出力のサンプルから、入力に対する正しい出力の計算方法を推定して、コードを生成したようだ。

ちなみに、問題の提出を探す仮定で、24秒で提出して通過したものなどが見つかった。こちらはどうやら手で書かれたようだ。問題は極めて簡単とは言え、人間業とは思えない。

我々はひとしきり感心した後に、職場を後にした。

ドワンゴ広告

この記事はドワンゴ勤務中に書かれた。

ドワンゴは勉強会の会場を提供しています。

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0