Brainfuck コードを最適化コンパイルする~C++メタプログラミングで~

この記事は、Brainf*ck Advent Calendar 2019 - Adventarの八日目の記事です。 Brainfuckをインタプリタで実行するとかなり遅いです。 高速に実行する一つの簡単な方法に、「C言語に変換する」という方法があります。 Wikipediaにも書いてありますが、以下の…

容量上限付き可変長配列の空間計算量

boost::container::static_vectorのような動作をする、容量の上限Nがコンパイル時に決められた値であり、実行時に配列の要素数sizeを(上限までの範囲で)変更できるようなデータ構造を考えます。 これを実現するには最低何bitの空間が必要でしょうか? 要素…

ロスってこんな形なのかな

なんか違った気がする

Microsoft(R) Excel(R) が有効数字を減らしてくる現象について

まずA1セルに1を入れ、A2セルには=A1*2と記入します。次に、A2セルのフィルハンドル(セルの右下にカーソルを合わせたときに出現する十字型のカーソル)を下にドラッグし、100セルほどコピーします。 このようにすると、2Nという数列を計算することができま…

g++でコンパイルが非常に遅くなる短い例

次の短いC++プログラムをg++ -g -O1などでコンパイルしてみると、非常に時間がかかります。最適化レベルは、-O0以外のどの最適化でも発生します。 struct Int { int n; Int() : n(0) {} }; struct Array { Int data[8000]; Array() : data{} {} } arr; [Wand…

交差型と主要型付けについてのメモ

主要型(principal type)のある体系とは、以下の性質を満たすような体系です。 型環境と項が与えられた時、につく型(一般に複数ありうる)は、何らかの型を具体化したものになっている。 一方、主要型付け(principal typing)のある体系とは、以下の性質…

rank 2 types の勉強

先週、以下のように書きました。 という項には、という型がつく という項にはという型がつく これらを組み合わせても、の型検査を通すことができない しかし、は、簡約が停止する この矛盾がよくわからなかったのですが、詳しく調べたところ分かったので書い…

calculus of constructions (CoC) の勉強

論理体系のうちの一つとしてのCoCではなくて、ラムダキューブの位置頂点であるλCと言った方が適切かもしれません。 λCは、全称型・型演算子・依存型をすべて含む、非常に表現力の高い型付きラムダ計算の体系です。 表現力が高いにもかかわらず、型検査が通れ…

切り替えて時間を有効に使いたい

explicit_bzeroとω矛盾

void explicit_bzero(void* s, size_t n)という関数があります。これの動作は、void bzero(void* s, size_t n)という関数と同じです。 void bzero(void* s, size_t n)という関数は、memset(s, '\0', n)と同じ動作をします。つまり、memset関数の方が上位互換…

普通の電卓で対数を求める

普通の電卓には対数を求める機能はないと思いますが、何とかして求めてみます。 たとえば、を求めてみます。 2×2=4、4×2=8、8×2=16……のように2nを求めていきます。すると、210=1024が10の累乗数に近いことが分かります。この関係から、であることが分かりま…

高速な完全精度 expf 関数の作り方

結構前に、完全精度(すべての入力に対して最近接丸めを行う) expf 関数の作り方を明らかにしました(完全精度 expf 関数の作り方 - よーる)。 今回は、その高速化を行います。積和演算がそれなりに高速なCPUを前提とします。 高速化の技法 多くの高速化の…

glibcのexp関数を読んでみる

最近のglibcは数学関数の高速化に取り組んでいるため確実なことは言えませんが、多くの環境ではC/C++の数学関数はこのglibcの実装を使うことになっているはずです。 glibcのexp関数の実装は、IBM Accurate Mathematical Libraryを使っているようです。 参考…

分岐予測器最新技術を読み解くメモその2

以下に紹介するのは15年前の技術なので、全然最新じゃないですね。 最近の分岐予測器でも使われる優秀な技術ということでしょう。 folded history グローバル履歴数百ビットを、高々20ビット程度に圧縮するハッシュ関数をどう作るかという問題の解決策です。…

分岐予測器最新技術を読み解くメモその1

高性能なプロセッサを作るためには、予測精度の高い分岐予測器が不可欠です。 ほとんどの分岐予測器は、主に以下の情報を使います。 * 分岐命令のあるアドレス(プログラムカウンタの値、PC) * 直近のいくつかの分岐について、分岐が成立だったか、不成立だ…

IEEE754浮動小数点数の丸めに関するメモ

すごく重箱の隅っぽいことについてです。 計算結果が有限だがINFに丸められる場合 方向丸め(正の無限大への丸め)の場合、真の結果が正規化数で表せる最大数よりも大きい場合、+INFに丸められます。 最近接丸めの場合、真の結果がどんな数でも"無限大"の方…

フィボナッチ数列を再帰関数で計算すると遅い

よく知られた事実ですが、指数的な回数の再帰呼び出しが行われるため、実用的ではありません。 フィボナッチ数列を計算する再帰関数は再帰の仕方がわかりやすいですが、よくわからない再帰の仕方の関数の場合はどうでしょうか? 関数が呼ばれたときにデバッ…

きっともっとやすんだほうがいい

32bit版RISC-VのLinux syscall 62はlseekではない?

Linuxのシステムコール62番は、64bit版の場合、lseekです。 off_t lseek(int fd, off_t offset, int whence); lseekシステムコールは、第一引数にファイルディスクリプタ、第二引数にどれだけ移動させるか、第三引数に動作の種類を受け取り、最終的な位置を…

パック展開とバイトニックソート

結構前の、constexpr関数を高速化する方法 - よーるという記事で、低速なconstexpr文脈の中でもある程度の速さで配列操作を行う方法として、パック展開を利用した配列を一気に構築する手法を紹介しました。 これを利用したバイトニックソートは、たとえば私…

Brainfuckのインタプリタを書いた

Brainfuckのインタプリタの書き方によって、実行速度が変わるのかが気になったため書いてみました。 もちろん、前処理、特にその場でコンパイル (just in time compile) をするなどすれば高速化は容易です。 そうではなく、ごく単純なswitch文を使うような、…

32bit版RISC-V用のspikeを動かす

オープンなISAであるRISC-Vには、32bit版も定義されています。 spikeは、RISC-Vの公式が開発している命令セットシミュレーターです。 以下の手順で必要なソースコードを持ってきます。 $ git clone https://github.com/riscv/riscv-tools.git $ cd riscv-too…

忙しく感じる

なんか最近忙しくないはずなのに、忙しいような気がしています。 たぶん原因は、塊として認識できない、こまごましたやらないといけないことが多いことのような気がします。 あとは、それをやることのできる時間が限られている(持ち時間が少ないという意味…

cat a.out を防ぐ

今日は七夕だったようですが、あいにくの雨でした。 出力ファイルを全部つなごうとcat *.outと打ったところ、a.outも巻き込まれてコンソールが大変なことになりました。 このミスは二回目なので、対策することにしました。 あまりうまい方法が思いつきません…

異世界とか

ちょっと違う世界に行っていました。 そこの住人は親切で、 いや、不親切な対応もあったような気がしますが、トータルでは親切だったなぁという印象でした。 それ以外はあんまり印象に残っていないってことは、そんなに違わなかったってことなのでしょう。

テンプレートメタプログラミングでQuineを書いた

最近テンプレートメタプログラミング (Template meta programming, TMP) から離れているなぁと思ったので、また書いてみました。 Quine(クワイン)とは、自分のソースコードを出力するプログラムのことです。 ソースコードは以下に公開してあります。C++11…

gcc9.1.0をソースコードからコンパイルした

gcc8以前と比較して、gcc9はバイナリ生成部分が更新されているようです。 既存のコンパイラのバイナリ生成に不満を持ったため、gcc9.1.0をビルドすることにしました。 前回gcc8.2.0をソースコードからコンパイルしました。 その時の知見が生かせたので、今回…

干し柿落としゲームのGrundy数を求めてみた

干し柿落しゲームは、takaken氏の作成した対戦ゲームで、石取りゲーム(Nim)を拡張したものです。 遊んだことがなければ、この記事を読む前に遊ぶことをおすすめします。ぜひ、自分で必勝戦略を構築してみてください。 干し柿落としゲームはNimより複雑であり…

AtCoderを退会するための問題(ABC077/ARC084のD問題)を別解法で解いた

AtCoderを退会するための問題、の元ネタは以下のツイートです。 本当に退会しますか?※botではないことの確認のため、以下の問題を解き、ソースコードを提出してください。問題文K の正の倍数の 10 進法での各桁の和としてありうる最小の値を求めてください…

二重かっこの高さを中身に合わせるtexマクロを解読する

のような二重角かっこは、\[\!\[3\]\!\]と入力すれば出すことができます。 nath.styを導入すると、\double[とか\lBrackなどと書けるようです。 しかし、このままでは中身に高さのあるもの(分数など)を入れた場合に見栄えが良くありません。 中身に応じた高…