###############
# Lua速度計測 #
###############

P/ECEで、Luaスクリプトの演算速度を計測してみました。

前回、倍精度浮動小数点演算ライブラリを高速化したのですけれど、そのきっかけは、P/ECEでLuaスクリプトを高速に使いたいと思ったことでした。
Luaは、人気のある組み込み用スクリプト言語です。
Luaの特徴のひとつは、P/ECEのような非力な実行環境でも(かろうじて)使えるぐらい、メモリ消費量が少ないことです。
別の特徴として、実行速度が速いことも挙げられるのですが、P/ECEで使用する場合は、少々問題があります。
Luaスクリプトの数値変数には、倍精度浮動小数点型しか無く、整数演算で充分なところも、全て、倍精度浮動小数演算を行ってしまうという点です。
P/ECEのように、浮動小数点演算をソフトウェアで処理する実行環境では、かなり速度低下してしまいます。
厳密には、Luaの数値変数を、整数型や単精度浮動小数型にすることも可能ではあるのですが、一般的でないし、できることも制限されてしまうため、良い方法ではありません。
そこで、正攻法で、倍精度浮動小数点演算ライブラリを高速化して、P/ECE上でのLuaの演算速度を改善することにしました。───というのが経緯です。

『2〜1000の範囲にある素数の数』を数える、スクリプトの実行時間を計測することにしました。
(「<a href='http://www.hakkaku.net/articles/20081023-283'>八角研究所 : 高速スクリプト言語「Lua」を始めよう！（1） - 高速スクリプト言語「Lua」を始めよう！（1）</a>」を参考させて頂きました。)

	-- nが素数ならばtrue、素数でなければfalseを返します。
	function is_prime(n)
		local i
		for i = 2, (n - 1) do
			if (n % i) == 0 then
				return false
			end
		end
		return true
	end
	-- 2〜1000の範囲にある素数の数を、変数cに格納します。
	c = 0
	for i = 2, 1000 do
		if is_prime(i) then
			c = c + 1
		end
	end

一見、整数演算しか使っていなさそうな処理なのですけれど、前述のとおり、Luaでは全て、倍精度浮動小数演算になってしまいます。
ループ変数iや、カウンタcの処理も、漏れなく倍精度浮動小数演算になってしまいます。

まずは、EPSON版浮動小数点演算ライブラリを使って、計測しました。
EPSON版浮動小数点演算ライブラリをSRAMに配置して、P/ECEを48MHzで駆動しました。(今回は全て、48MHzで計測しました。)
結果は、以下のようになりました。

	       結果[個] 時間[ms]
	C(int)      168      195
	C(flt)      168     3767
	C(dbl)      168    19235
	Lua         168    22904

下の行から逆順に見て行ってください。
「Lua」の行が、Luaスクリプトの実行時間です。
「C(dbl)」の行は、同じアルゴリズムをC言語で、倍精度浮動小数点演算で実行した場合の実行時間です。
「C(flt)」の行は、同じアルゴリズムをC言語で、単精度浮動小数点演算で実行した場合の実行時間です。
「C(int)」の行は、同じアルゴリズムをC言語で、整数演算で実行した場合の実行時間です。

C(int)が約0.2秒に対して、Luaは約22秒。これは遅すぎます・・・
ただし、C(dbl)も20秒近くかかっているので、遅さの主原因はLuaそのものではなく、倍精度浮動小数点演算であることがわかります。

次に、高速版浮動小数点ライブラリを使って、計測しました。
高速版浮動小数点ライブラリをSRAMに配置して、P/ECEを48MHzで駆動しました。
結果は、以下のようになりました。

	       結果[個] 時間[ms]
	C(int)      168      195
	C(flt)      168     1801
	C(dbl)      168     9223
	Lua         168    12700

C(flt)とC(dbl)が、高速版浮動小数点ライブラリの効果で、二倍ぐらい早くなっています。
C(dbl)が早くなったのと同じ分だけ、Luaも早くなっています。

最後に、高速版浮動小数点ライブラリを高速RAMに配置、P/ECEを48MHzで駆動して、計測しました。
結果は、以下のようになりました。

	       結果[個] 時間[ms]
	C(int)      168      195
	C(flt)      168      991
	C(dbl)      168     3976
	Lua         168     6851

C(flt)とC(dbl)が、高速RAMの効果で、さらに二倍ぐらい早くなっています。
C(dbl)が早くなったのと同じ分だけ、Luaも早くなっています。

LuaとC(dbl)を比べると、Luaの方が４０〜５０％ぐらい遅い、という結果です。
LuaとC(dbl)の実行時間の差は、三つの計測結果で同じなのですけれど、倍精度浮動小数点演算の時間が短くなった分だけ、LuaとCの差が顕著になります。
でも、スクリプト言語とC言語を比べて、この程度の差ならば、充分許容範囲だと思いました。

ところで、本題とは外れるのですけれど、今回の計測結果で、少し気になる点があります。
C(flt)とC(dbl)の差が、四倍もあることです。
前回のWhetstoneベンチマーク(倍精度版)の計測結果から考えると、倍精度と単精度の性能差は、二倍弱ぐらいに収まるはずでした。
なぜ、四倍もの差がついてしまったのでしょうか？
たぶん、除算(厳密には剰余「%」)を多用しているからだと思います。
P/ECEのCPUでは、除算は、筆算のアルゴリズムで実装します。
単精度の除算と倍精度の除算を較べると、まず単純に、ビット数が二倍になった分、二倍のステップ数が必要になります。
その上、32ビットと64ビットの違いが、1ステップあたりの処理にも影響します。
単精度ならば、32ビットの筆算で済むので、P/ECEのCPUに備わっているステップ除算命令を利用して、1ステップ当り1クロックで実行できます。
倍精度では、64ビットの筆算が必要で、ステップ除算命令は利用できず、命令を組み合わせて処理し、1ステップ当り8〜10クロックかかります。
ビット数の違いと、1ステップ当りの速度の違いが掛け合わさって、16〜20倍ぐらいの差が生じます。
(実際には、除算処理の中の筆算以外の部分では、こんなに大きな速度差は無いので、除算処理全体で平均すると、もう少し差は小さくなります。)
なお、加減算や乗算は、筆算のアルゴリズムを使って1ビットずつ処理したりはしないので、除算の場合ほど、単精度と倍精度の差は生じません。

==================
Wed Feb 08 2012
Naoyuki Sawa
nsawa@piece-me.org
==================
