kmizuの日記

プログラミングや形式言語に関係のあることを書いたり書かなかったり。

scala-nativeでは相互末尾再帰呼び出しも最適化される

Scala Nativeなのかscala-nativeなのか迷ったのですが、今後はリポジトリ名のscala-nativeに統一しようかと思います。さて、タイトルについてですが、そのまんまです。

サンプルコードは以下:

gist.github.com

通常のJVM上でのScalaでは、末尾呼び出しが自分自身で(自己末尾再帰)、かつ、その関数(メソッド)がオーバーライドされない場合に限り、末尾呼び出しを除去することができましたが、scala-nativeはそれに限らず、一般の末尾呼び出しも除去(ジャンプに置き換えることができる)という話です。

上記サンプルコードでは、単純にやるとおよそ100000000個分スタックを積む必要がありますが、そのまま関数呼び出しとして実装するとスタックオーバーフローします。事実、最適化オプションを付けないclang(3.7)では同等のコードを実行しようとするとsegmentation faultを起こしました(-O1以上の最適化オプションを付けるとちゃんと実行できました)。

JVM上でのScalaでは末尾呼び出しの除去をやろうと思うと、非常に高いコストを払って自前でトランポリン形式にするくらいしか選択肢がなかったですが、scala-nativeではJVMという制約がないので、その辺の最適化もできるようになった、ということです。

追記: LLVMでは言語非依存の最適化として末尾呼び出しの除去が行えるらしいのでscala-nativeはその機能をそのまま使っているのかもしれませんね。

scala-nativeのサンプルプログラムをLinuxで動作させる場合の注意点

kmizu.hatenablog.com

についての補足的なエントリです。scala-nativeのサンプルプログラムsmallpt.scala__stderrpを使っていますが、Linux系には存在しないので、リンク時にこけてしまいます。

これを修正するには、smallpt.scalastdlib.scala__stderrp__stdoutpをそれぞれ、stderrstdoutに書き換えてやる必要があります。現状、条件コンパイルのような仕組みはサポートされていないのでこれをクロスプラットフォームで動作させる方法がたぶんないのがちと困ったものです(作者本人が作ったIssueには入っているので、そのうち解決されるだろうとは思いますが)。実は手元でunameを使ってOSによって分岐するコードを書いてみようとしたのですが、構造体のメモリレイアウトが微妙に違うのか、unameは呼び出せるものの、返り値に謎の値が入っているという事態になりました(なにか勘違いしているかも)。