On the quality of academic software | Daniel Lemire's blog
同僚がSlackに貼り付けたこの記事に同意しすぎて気絶している。
続きを読む今日、後輩と色々試していて面白いことに気付いた。Fortranのキーワードは、予約語ではない。Fortranはdo
とかif
とかといったキーワードを持っているが、これらは予約語ではない。
ググると規格書のセクション番号込で情報が出てくる。
ISO Fortran90 standard § 2.5.2 "Keyword"では、以下のような記述がある。
These keywords are not reserved words; that is, names with the same spellings are allowed.
「これらのキーワードは予約語ではない。つまり、同じ綴りの名前は許される」らしい。
規格書のドラフトはここで見ることができる。
質問している人もいるが、「キーワードを変数名として使うのはバッドプラクティスだ」という(当たり前の)答えが返ってきている。
どういうことかというと、以下のコードが合法だということだ。
program main integer :: do, end=0 do do=1, 10 end = end + do end do write(*,*) end end program main
ついでに、以下のようなコードも合法である。
program main logical::if=.true. if (if) if = then() write(*,*) if contains function then() logical then then = .true. end function then end program main
こんなコードが出てきた日には発狂すること請け合いであるが、Fortranコードのメンテをさせられて発狂寸前の人はこのような爆弾をコードに仕込んでみても面白いのかも知れない。
if
を関数にすることもできて、以下のコードはok
を出力する。
program main if(if(if(if(.true.)))) write(*, *) 'ok' contains function if(x) logical::x logical::if if = x end function if end program main
何一つokなところがない。
これだとif
関数が何もしていないからまだいいが、もっと悪意の強い関数にもできる。
program main if(if(.true.)) then write(*, *) 'ok' else write(*, *) 'not ok' end if contains function if(x) logical::x logical::if if = .not. x end function if end program main
このコードはnot ok
を出力する。確かにnot ok
だ。if
関数が定義されているばかりか、その関数がlogical
な値を受け取ってそれを反転するので。
ちなみにgfortran-5.5.0
で-Wall
と-Wextra
つきでコンパイルしても、上記のコードに警告は出ない(規格上予約語ではないとしても、警告くらいは出していいと思うのだが)。というわけで静かに爆弾を仕込むことができるので、使ってみてはいかがだろうか。
GitHubは自動でシンタックスハイライトがされるが、言語仕様が今も変わっていくような言語(大体の使われている言語はそうだ。Goのように意図的に固定している例外を除いて)ではたまにそれが古いままで、公式ページのハイライトがおかしいことがある。
TOMLがその良い例で、TOML v0.5.0で追加された一部の機能が真っ赤にハイライトされていた。例えば、dotted keys(キーを繋いで階層構造を作る)や整数プレフィックス(0x
、0b
など)、特殊な浮動小数点数(inf
とnan
)などだ。
ところで私は既にv0.5.0対応のTOMLライブラリを一つ書いており(toml11は書き換え中)、それを使ったツールのサンプルが真っ赤になるのは悲しかった。
なので直したいと思い立ち、調べてみることにした。有名エンジニアである犬さんのブログが真っ先に引っかかる。
これによると、GitHubのシンタックスハイライトは以下のレポジトリによって行われている。
このレポジトリはエディタ用の文法定義を再利用するようになっている。TextMateやAtomやSublimeや……といったエディタの設定ファイルをメンテしているレポジトリを覚えておいて、数週間かおきにpullしてきてアップデートしつつ使うというようになっている。それぞれのシンタックス定義は別レポジトリになっているので、linguist自体にPRが山ほど飛んでくるという事態を避けることができる。
このディレクトリにそのモジュールの一覧がある。
linguist/vendor at master · github/linguist · GitHub
ここから直したいレポジトリに飛んで、そこにPRを投げればいいわけだ。今回はTOMLなので、TextMateなるエディタの設定ファイルを編集することになる。
ところで私はTextMateというものを使ったことがない。ちらりとTOML用のレポジトリの中身を見てみたが、正規表現でマッチした部分に名前を付け、名前によってハイライトしていくものであるようだ。XMLで書かれているので読めないこともないが、つらい。
動作確認のこともあり、TextMateが必要だろうと思った。まず、ググるとmacOS用のエディタだということがわかる。私はWindowsマシンは持っていないがmacは持っているので、インストールできた。
TextMate: Text editor for macOS
上のメニューからバンドルを開いて追加すればよいと書かれているのでやってみる。ちなみにやったのが数週間前(後述するがPRが閉じられるまでそれくらいかかった)なのでよく覚えていない。
インストール後、TextMateの Bundles > Edit Bundles > TOML > Language Grammers > TOML と開いていくと、別ウインドウでシンタックスの定義ファイルを編集しながら結果を見ることができるではないか。しかもXMLではなくJSONっぽい(けど少し違う)形式を使っているので、より目にやさしい。Ctrl-Sを押すごとにハイライトが更新されるので、保存のタイミングでこの形式からXMLに変換しているのだろう。実際、Applications/みたいなディレクトリにXML形式のファイルがある。
さて、書き方はわかったが、次は何を編集したらどういう影響が出るのか調べねばならない。以下は試しながらの憶測だったが、まあ多少の編集を経たとはいえマージされたので大外しはしていなかったのだろう。上記のようにして開くと以下のような設定が見える。以下のコードは(TextMateによる変換を経たとはいえ)https://github.com/textmate/toml.tmbundleからの引用になる。
patterns = ( { begin = ‘([A-Za-z0-9_-]+)\s*(=)\s*‘; end = ‘(?<=\S)(?<!=)|$’; captures = { 1 = { name = ‘variable.other.key.toml’; }; 2 = { name = ‘punctuation.separator.key-value.toml’; }; }; patterns = ( { include = ‘#primatives’; } ); })
ここでbegin
とend
に正規表現がある。これらによって囲まれた領域にマッチするものと思われる。基本重要な部分は大抵beginに書いてあったのでそこをいじった。で、そのグループの登場順序によって番号が振られ、capturesの中の番号に対応する名前を書いておくと、その名前としてハイライトされるようである。多分、カラースキームのようなものが別にあって、実際の色はそちらで構文要素の名前から決められるのだろう。この例では、bare-keyに対応する1つめのグループ([A-Za-z0-9_-]+)
にvariable.other.key.toml
という名前が割り振られ、次のグループ=
にpunctuation.separator.key-value.toml
なる名前がついている。
つまり、正規表現を拡張して新機能にマッチするようにして、グループ毎の名前を適切につければよいわけだ。そのような方針で編集して動くことを確認し、内容をPRにまとめて送りつけた。以下がそれだ。
allow dotted keys by ToruNiina · Pull Request #9 · textmate/toml.tmbundle · GitHub
数週間ほど放置されていて少しやきもきしたが、今日晴れてマージされた。いや正確にはマージされたというより、いくらかの編集を経てコミットが追加され、クローズされた。
追加された変更は、例えば数値にマッチする正規表現が長すぎたので分割する(最初は整数と浮動小数点数が同じくくりでマッチされていたので、そういう方針なのかと思って尊重していたのだが、単に短いから構わないという扱いだったのだろうか)とか、ハイライト時の分類を直すとか(ここは純粋にどうするべきかわかっていなかった)、いくつかのエッジケースを直す(ありがたい)などだった。
というわけで、しばらくすればGitHubのハイライトも修正されるだろう。今までもそれなりに使ってもらえるツールは作っていたが、これまでとは比べ物にならない規模の人数が目撃するソフトウェアの端っこに自分の小さな爪痕を残したというのは、結構気分がいいものだ。
これでtoml.tmbundleのレポジトリのコントリビュータは3人になった。プライマリ作者と、TOMLそのものの作者Tom Preston-Werner(@mojombo)と、私である。ヤバい人々でビビるが、それ故に嬉しさもひとしおというところだ。
みなさんもGitHubのハイライトに不満があれば、PRを投げつけてみてはいかがだろうか。
今日、妙な話を聞いた。CかC++かでコードを書いていたところ、変数名を長くすると32文字だかそこらでtruncateされてしまい、前半が同じ名前の変数を使っているとコンパイルエラーになってしまったというのだ。私は(少なくともC++で)変数名に文字数制限があるとは思っていなかったので、かなり驚いた。むしろコンパイラを疑った。
というわけで規格書にあたってみることにした。C規格としてN1256(C99)を、C++規格はN3337(C++11)を参照する。
まず、Cでは§6.4.2.1の Language Lexical elements > Identifiers > General > Implementation limits に、
an implementation may limit the number of significant initial characters in an identifier ... Any identifiers that differ in a significant character are different identifiers. If two identifiers differ only in nonsignificant characters, the behavior is undefined.
との記述がある。要するに、処理系は識別子の最初の何文字か以降は無視してしまって構わないということだ。そしてもし無視されない前半部分が重複していて無視される後半部分のみが違う識別子の組が登場した場合、その挙動は未定義となる。
これは驚きだ。識別子として使える(意味を持つ)文字数は処理系定義なのか。ここしか見ていないのでわからないが、もしかしてこの文字数は1文字でも規格準拠なのだろうか……標準ライブラリのほとんど全てが使えないが。
ちなみにGCCでは文字数に制限はない(以下参照)。まあそりゃそうだ。
Using the GNU Compiler Collection (GCC): Identifiers implementation
ではC++ではどうだろう。§2.11のLexical convensions > Identifiersには、
An identifier is an arbitrarily long sequence of letters and digits.
と書かれている。任意の長さが許されるようだ。話が終わってしまった。まあ、安心するべきことではある。
まとめると、Cを書いている時に長い変数名を使って妙なことが起きた場合(そしてそれが純粋に変数名が長いことによる問題だった場合)、コンパイラが悪いとは言えない。しかしもしC++で識別子の後半が無視された場合は、コンパイラが悪い。プログラマは自信を持ってIssueを報告して構わないということだ。
C++にはコンパイル時の有理数計算ライブラリがある。個人的な理解では、これは<chrono>
のために入ったライブラリで、<chrono>
がduration
を綺麗で速い(使いやすいとは言っていない)やり方で実装するためのものだ。コンパイル時に比率を計算できるので、実行時にかかるオーバーヘッドはせいぜい整数か浮動小数点数の掛け算くらいしか残らないことになる。
ご存知の通り、浮動小数点数は我々の知る実数とは少しだけ異なる。有限のメモリ領域を使ってできる限り広い範囲の数を表現しようとしてはいるが、もちろん完璧ではない。特に、我々は指が10本なので単位系を10の倍数ベースに作っており、そして悲しいことに0.1は2進数では循環少数になる。なので計算途中に丸めが入ることになる。これを避けるためには、整数同士の比で計算するしかない。整数は(実行時に伸びる多倍長整数を使えば)事実上無限の長さを扱えるので、有理数で計算している限り丸め誤差は入る余地がない。まあ、コンパイル時に計算する場合は固定長でなければならないのだが。コンパイル時多倍長演算を実装するという手は置いておいて。
なのでstd::ratio
は2つのstd::intmax_t
を取る。それぞれが分子と分母に相当する。そして演算もサポートされていて、ratio_add
、ratio_subtract
、ratio_multiply
、ratio_divide
が用意されている。これらを使えば、約分まで済んだstd::ratio
が得られる。また、比較も用意されていて、ratio_equal
その他がそれぞれ定義されている。
また、主目的が単位換算なので、SI接頭辞(std::kilo
やstd::milli
など)も定義されている。
さて、単位には非常に大きな数値が登場するものがあったりする。例えば、分子量は6.02e+23の大きさがあり、原子1個あたりの重さは例えば12 / 6.02e+23グラムになったりする。ところで、log10(264)の値は20に届かない。なのでおそらくこの単位はほとんどの環境でオーバーフローを引き起こしてしまい、上記の枠組みに乗らなくなってしまうだろう。
となると、この際丸め誤差には目をつぶって、コンパイル時に浮動小数点演算を行うしかない。幸いなことにC++11以降ではconstexpr
があるので、浮動小数点演算を行うことが可能だ。すると、既存のstd::ratio
と相互運用可能なfratio
とでも言うべきものを作る必要がある。
面倒なことにC++のnon-type template argumentは浮動小数点数を持てないので、static constexpr double value = /**/;
のようにする必要がある。
struct mole { static constexpr double value = 6.02e22; }; template<typename Numer, typename Denom> struct fratio { static constexpr double num = Numer::value; static constexpr double den = Denom::value; static constexpr double value = num / den; };
しかしながらstd::ratio
はstd::ratio::value
を持っていないので、共通で使うには::value
を使ってはいけない。とはいえfratio
の中で::value
を使わざるを得ない以上(再帰的に定義できた方が便利だ)、共通のインターフェースを用意しておく必要がある。
template<typename T> struct value_of { static constexpr double value = T::value; }; // std::ratioへの部分特殊化 template<std::intmax_t N, std::intmax_t D> struct value_of<std::intmax_t<N, D>> { // 有理数をdoubleに変換する static constexpr double value = static_cast<double>(N) / D; };
これを噛ませれば、std::ratio
を共通で使っていくことが可能になる。
正確な数値という利便性を捨ててしまうことになるが、多少の丸め誤差が問題ない場合はこれでことが足りる。もしどうしても正確な数値が必要なら、std::intmax_t
のペアもしくは可変長引数を取ることによって多倍長を実現しても構わないのではあるが、使うのがとても難しくなってしまうので、難しいところだ。
タイトルで察した方は帰って結構です。
git submoduleというのがある。これは、別レポジトリをレポジトリの一部として管理できる機能で、要するに依存しているレポジトリのURLと対応するコミットをコードの一部として管理するものだ(大雑把すぎる)。すると依存レポジトリのバージョンをgitで一括で管理できるようになる。
$ git submodule add <repo URL> # その後 $ git submodule init $ git submodule update # または、上記を一括で $ git submodule update --init # submodule の submodule まで再帰的に $ git submodule update --init --recursive
submoduleも一つの独立したgitディレクトリとして振る舞うので、そこでpullしてから上でaddすることによって「依存関係にあるレポジトリのバージョンを上げる」という変更をgitで記録できる。
さて、このようなことを実践したレポジトリをpushしたところ、Travisが落ちた。Permission denied (publickey)と言われている。gitのsshプロトコルでアクセスした場合、sshの鍵がないとダウンロードできない(sshでログイン出来ないので)。もちろん、自分の秘密鍵を公開レポジトリに置くような馬鹿はいない。よって、submoduleをダウンロードできず、CIは失敗する。
さてどうしたものか。
とりあえずググると、Gistに解決策が転がっていた。まず、Travisが自動で行うgit clone --recursive
をやめさせる(git: submodules: false
)。続いて、sed
でgit@github.com
をhttps://github.com
に変換する。力技だ。
確かにこれはLinuxでなら動くが、OS Xだと動かない。OS XはUnixでありLinuxではないので、コマンドの挙動がほんの少しずつ異なる。以下に同じ問題に苦しめられた人間の怨嗟の声がある。
Sed: 'sed: 1: invalid command code R' on Mac OS X
何が起きているかというと、sed -i
はファイルをその場で(in-place)書き換える。これは怖いので、sedはバックアップファイルを作りたいと思っている。そのバックアップファイルの拡張子を-i
オプションの引数として要求されているのだが、我々はそれを渡さず、代わりにsedスクリプトと変更して欲しいファイルを渡した。するとsedはスクリプトをバックアップファイルの拡張子と思い込み、続くファイル名をsedスクリプトだと思って実行しようとして、「そんなコマンドはない」と返しているというわけだ。
回避するには、適当な拡張子をくれてやればいい。あるいは、空の文字列を渡せばそもそもバックアップファイルは作られない。
# この""が必要 $ sed -i "" 's/hoge/foo/g' foobar.dat
あとはこれで、Travisで環境を見て分岐してから実行して終わりだ。
しばらく放置してしまっていた。中々書くべきことが見つからなかったので。Nintendo Switchを購入してしまい、遊んでいたというのもあるが。
今回は、ちょっと普段気にしないアライメントのことについて話してみようと思う。
以前、C++17でのアライメント指定付き動的メモリ確保の話をした時少し話した気がするが、CPUはメモリのどんな位置にでも好き勝手にアクセスできるわけではない。例えば、一回のメモリアクセスでは16バイト分のデータを16の倍数のアドレスからしか読み込めない、というような感じの制限がある(数字は適当)。なので、以下のようになって困ることがある。
メモリアクセス v v v v | | |d|a|t|a| | |
というわけで、メモリ上でのデータの配置には守るべきルールが存在し、型T
はalignof(T)
(例えば8バイト)の倍数にあたるメモリアドレスから始まる領域にしか置くことができない。
これは、以下のようなコードを書くときに問題になってくる。
他にもあるかもしれない。何にせよ、例えばバイナリファイルを読み書きしている時、以下のようなことをすると一発で地雷を踏みぬいてしまう。
const char* stream; const double d = *reinterpret_cast<const double*>(stream);
ここで、stream
の位置はバイト単位で変わる。例えばデータ型のタグとして1バイト使っていたとすると、その次からdouble
のデータが始まったりするだろう。すると、メモリ上に確かにsizeof(double)
分の領域があり、そこにdouble
のビット列が入っているのだが、メモリアドレスがalignof(double)
の倍数になっていないという状況になりかねない。その場合、上のコードでデリファレンスしているポインタは、アライメント要求を満たさない不適切なポインタになってしまう。
つまりこうだ。
0x0000 v | |d|a|t|a| | | ^ 0x0001 (8の倍数でないため、`double`のポインタにできない)
ではどうするか。C規格では(unsigned|signed) char
とならどんな型でも変換可能ということになっている。C++17ではstd::byte
もここに仲間入りした。これは、char*
からT*
への変換が常に成立するという意味ではなく(これは常には成立しない)、T*
をchar
の配列へのポインタへ再解釈して構わないということである。char
のアライメント要求が最小ということなのだろう。
なので、より安全なコードは以下のようになる。
const char* stream; double d; std::memcpy(reinterpret_cast<void*>(std::addressof(d)), reinterpret_cast<void*>(stream), sizeof(double));
上記コードではdouble
へのポインタを(memcpy
は内部でunsigned char
へのポインタに変換するので)unsigned char
へのポインタに変換し、両方をunsigned char[N]
だと思ってデータをコピーしている。
まったく、面倒この上ない。
他に、データのビット表現を取得するとき、というのは、例えばfloat
の値をuint32_t
へビットをそのままに変換するという意味だ。なぜそんなことをするのかというと、謎のビット演算によっていくつかの高コストな浮動小数点演算が近似できるからだ。このテクニックは以下によくまとまっている。
GitHub - keon/awesome-bits: A curated list of awesome bitwise operations and tricks
この場合、以下のようにしたくなる。
float f = /**/; std::uint32_t i = *reinterpret_cast<std::uint32_t*>(&f);
実際、以前このブログでも書いてしまった気がする。だがこれは通らない(大抵動くのだが、間違ったコードなので動く保証はない)。これは、float
とstd::uint32_t
のアライメント要求が一致している前提で書かれたコードだが、そんな保証はない。保証されているのは前述の通りchar
かstd::byte
への変換のみである。
なので、正しくは以下だ。
float f = /**/ std::uint32_t i; std::memcpy(reinterpret_cast<void*>(std::addressof(f)), reinterpret_cast<void*>(std::addressof(i)), sizeof(float));
よく考えると、float
が4バイトなのは定義されているのだろうか? std::uint32_t
はその点便利で、これは2の補数表現でピッタリ32ビットであることが保証されている。そのような型をサポートしていないアーキテクチャでは、この型が定義されない。なので知らずにコンパイルしてもエラーになってくれる。
ちょっと見てみたが、IEEE754準拠は必須ではない(__STDC_IEC_559__
が1ならIEEE 754に対応しているとわかる)。ということは、float
の中身については何も仮定できない。まあint
がそうなのだから当たり前か。
(ため息)
さて、上記の3つの状況の最後のものは、普通でないアライメントを指定して何かする時だ。
まず、なぜそんなことをする必要があるのかというと、これもいくつか理由がある。
まず、SIMDとはSingle Instruction Multiple Dataの略で、一つの命令を複数のデータに同時に適用することで速度向上を図るものだ。例えば、レジスタに4つの数値をロードしておいて、その全てに加算命令を発行して同時に処理すれば、1命令で4つ分の計算ができ、速度が理論上4倍になる。このとき、ロードするデータが通常より大きなアライメントを満たしていれば、ロード速度が向上する。そうでなければ複数回のメモリアクセスが発生し、少し時間がかかってしまう。
他に、キャッシュの更新を抑える目的でアライメントを調整することがある。根本に立ち戻ると、現代のアーキテクチャではメモリはCPUに比べると遅い。なので、CPUの計算よりもメモリアクセスが律速になってしまうことが多い。それをなんとか隠蔽しようとして、CPUは内部に高速にアクセスできるが容量の少ないメモリを持っておき、メモリ上の使いそうなものをそこに先に持ってきておくようになった。CPUは一回につきある決まった量のデータをキャッシュしておくのだが、これはキャッシュラインと呼ばれている。
賢い戦略ではあるのだが、やはり面倒なことはある。例えば並列化で複数のCPUが同じメモリ領域を見ているとすると、一つのCPUでのキャッシュへの書き込みが他のCPUのキャッシュに同期されなければ、データがおかしくなってしまう。なので書き込みが生じた場合、全CPUとメインメモリでデータを同期する必要がある(キャッシュコヒーレンシ)。さて、もし一つのキャッシュライン上に凄まじく頻繁に更新される値が一つと、全く更新されないとわかっている値が沢山乗っていたらどうだろう。ほとんどの値は変更されないのに、同じキャッシュラインに乗っているたった一つの値のせいでキャッシュライン全体の動機が発生する(false sharing)。これを回避する方法はいくつかある。キャッシュラインサイズに沿ったアライメント指定をして別のラインに乗るようにするものと、構造体にダミーデータでパディングして別のキャッシュラインに入るようにするというものだ。
他に外部デバイスと通信するときに気をつけないといけないという話を聞いたことがあるが、あまり書いたことがないのでよくわかっていない。GPUのテクスチャメモリ(か、別の特殊なメモリだったかもしれない)だと何か要求されていたような気がする。
さて、上記のようなコードを書く場合は同時にアライメントについて調べると思うので、あまり変な事にはならないのではないかと思う。ただ、落とし穴があるのは動的にメモリ確保をする時だ。通常、malloc
やnew
はメモリ領域のサイズしか知らされず、アライメントまでは指定されない。malloc
にアライメント値を渡した記憶のある方はいるだろうか? 受け取らないのだからいるはずがない。ではどうしているのかというと、デフォルトのアライメントが決まっており、それに合わせたメモリ領域が返ってくるのだ。このデフォルト値は大抵、基本型の要求するアライメントのうち最大のものになっている。アライメントは何かの倍数のアドレスに置くことを要求するものなので、最大の値の倍数(最大公倍数と言えばいいのだが、大抵全て2のN乗なので最大の値に等しい)は他のものを満たすという便利な性質がある。ではデフォルト値より大きな値を設定するとどうなるか? どうにもならない。malloc
もnew
もそんなことは知らない。なのでアライメントは単に無視されてしまう。
このために、C11ではaligned_alloc
が、C++17ではアライメント指定されたデータの動的メモリ確保が入った。これらはアライメント要求を受け取り、それに適した領域をアロケートして返す。これ以前だと、大きめにアロケートして先頭ポインタが要求を満たすところまでずらすか、posix_memalign
や_aligned_malloc
などの処理系定義関数を使う必要があった。
面倒この上ない。だが、これらは計算機科学の奥底に眠っている問題ではなく、バイナリファイルを読もうとしたりちょっとした最適化をしようとしたときにすぐに首をもたげる問題なので、意識しておくのもいいかもしれない。