こんにちは､びしょ〜じょです｡ アイカツ! Top of worksはぶっちゃけヤバイ｡幸せがグッと詰まってるのでぜひ買ってください｡ でかいので買う前にスペース確保などしてください｡
縦幅が2.2TAPLある。 pic.twitter.com/Pk4b1QugEX
— びしょ〜じょ (@Nymphium) May 16, 2016
1. はじめに
はじめにの前に
先日はこんな発表をしました｡
内容はLua 5.2のVMのバイトコードを読むというもので､VMの命令とか定数をデコードするというものを作りました｡ もうすこしなんかやりたいところでしたね…｡
他には面白い発表が聞けたので楽しかったです｡
intro
さて､同イベントに参加した@_yyu_ さんにLuaのtableの実装について聞かれたんですが､そこまで詳しくなかったので答えられないというインシデントがありました｡ 唯一のデータ構造といわれると確かにそこが気になるはずだ｡ちなみにScalaではHAMTという高速な操作ができるデータ構造が用意されているようだ｡
さんざんLuaについて語っておいてそれはマズい､というわけでちょっとだけ調べた｡ 実装の詳細については資料がなかったのでソースを読まざるを得ない､しかしCはもう読みたくない､ということで実装の詳細には迫れなかったが､動作の概略を今回は掴んでみたい｡
2. Luaのtableについて
今回はtableのhashとメモリ確保について｡
Lua 4.0まではtableは完全にhash tableだったようですが､5.0以降はhash partとarray partという2つの構造を併せ持つハイブリッドな物体になっています｡
これによりt[1]､t[2]､…などは､arrayのn番目という内部表現から得られるため､indexを保持する必要がなくなるなどの改善が得られました｡さて｡
3. allocationとindex/key
3-1. key or index?
では以下のようなコードはどないすんじゃヴォケという考えに至ります｡
local x = {}
x[10000] = "voke"
xの10000番目に値を入れるのか? 実はそうではない｡この場合10000というkeyに"voke"というvalueが入るため､xのarray partの長さは0のままです｡
数字は､プログラマーは､俺は､こいつはindexなのかkeyなのか､という問題に頭を抱えます｡
3-2. key to index
数字の気持ちはともかく､プログラマーにはとりあえずなんとかわかりそうな気がしないでもない方法があります｡
まずはarray partのサイズの確保について話します｡
メモリ確保のタイミングはいつなのか｡ array partに関しては､以下のタイミングでメモリの確保が行われる｡
- tableに一つ値が追加され､メモリ確保が必要となるとき､次のような
nが確保される｡- array partの
1〜nのうち半分に値が入ってる -
n/2+1〜nのうち最低一つに値が入ってる
- array partの
メモリの確保というのは､つまりより長いtableを作って突っ込んでいくということ｡ここでkeyがn ≧ kとなるnumber kの場合､indexとして変換される｡
せっかくなのでmoorを使ってみまつ｡
$ moor
moor on MoonScript version 0.4.0 on Lua 5.3
> t = {1, 2, 3}
> t[8] = 8
> table.remove t, 1
1
> t
{ 2, 3,
[8] = 8
}
> t2 = {1, 2, 3, 4}
> t2[8] = 8
> table.remove t2, 1
1
> t2
{ 2, 3, 4,
[7] = 8
}
tでは長さ3のarray partが定義時に作られます｡で､t[8]に値を入れますが､上記のメモリ確保の方法からいくと長さ8まで取ってくれないので8はindexではなくkeyとして保持されます｡
そのため､1番目の要素をtable.remove()で取り除いても8はkeyなので変わりません｡
一方､t2ではまず長さ4のarray partを定義時に用意しています｡それでt[8]を突っ込むと､n/2個の要素が使われててn/2+1〜nの間に値が1つ以上あるnがちょうど8なので､8はindexになります｡
その証拠にほら､8を格納してるindexが7になってるだろう?
次はメモリ確保のタイミングについての計測です｡ そろそろ飽きてきたのでちゃんと理解できてないうちに書いてみたやつを動かしてみます｡ 何をしてるかというと､tableにガンガンものを突っ込んでるというだけで､tableの成長はサイズがでかいとちょっと時間がかかるというヤツですね｡
local sock = require'socket'
local get_exectime = function(fn)
local t1 = sock.gettime()
fn()
local t2 = sock.gettime()
return t2 - t1
end
local t = {}
local function printrangetime(a, b)
io.write((" %10d 〜 %-10d (+%8d )\t"):format(a, b, b-a))
print(get_exectime(function()
for i = a, b do
t[i] = i
end
end))
end
print((" %10s %-10s ( %7s ) %10s"):format("from", "to", "div", "sec"))
print(("-"):rep(60))
printrangetime(0, 4999)
printrangetime(5000, 2^21 - 1)
printrangetime(2^21, 2^22-1)
printrangetime(2^22, 2^22+2^21 - 1)
printrangetime(2^22+2^21, 2^22+2^22-1)
printrangetime(2^22+2^22, 2^22+2^22+2^21-1)
print((" "):rep(19) .. "adding", (2^22+2^22+2^22-10001) - (2^22+2^22+2^21))
for i = 2^22+2^22+2^21 , 2^22+2^22+2^22 - 10001 do
t[i] = i
end
printrangetime(2^22+2^22+2^22-10000, 2^22+2^22+2^22-5001)
printrangetime(2^22+2^22+2^22-5000, 2^22+2^22+2^22-1)
printrangetime(2^22+2^22+2^22, 2^22+2^22+2^22+4999)
以下の実行結果が得られる｡
$ lua test.lua
from to ( div ) sec
------------------------------------------------------------
0 〜 4999 (+ 4999 ) 0.00021195411682129
5000 〜 2097151 (+ 2092151 ) 0.065406084060669
2097152 〜 4194303 (+ 2097151 ) 0.090538024902344
4194304 〜 6291455 (+ 2097151 ) 0.10658502578735
6291456 〜 8388607 (+ 2097151 ) 0.058128118515015
8388608 〜 10485759 (+ 2097151 ) 0.15600204467773
adding 2087151.0
12572912 〜 12577911 (+ 4999 ) 0.00013303756713867
12577912 〜 12582911 (+ 4999 ) 0.00014400482177734
12582912 〜 12587911 (+ 4999 ) 0.00014877319335938
なるほど｡面白いのは最初(from 0 to 4999)のtableへの値の追加とケツの方ではあまり時間が変わらないんですねぇ｡ 前者は短い内でのtableの成長が大量に起きるので若干遅くなっている｡
4. おわりに
@_yyu_ さんが知りたいのは多分key-valueの保持とひも付けの方法だと思うんです､ボクもそれが知りたかった｡
参考文献
院に行くかどうかは確定的ではないが充分視野に入れているので､来月のTOEFLかTOEICかなんかがタダで受けられるらしいので頑張りたい｡ ということでLua workshop 2015の発表をYoutubeで聞いてるわけですがポルトガルなまりの英語が難しいですおわり｡
ところでTOEなんとかが終わるのが1300で､同日1630にはSB69一挙放送イベントに行くわけですが気持ち高まってんぞ､ その翌日はチケットがあたったらりりくるのイベントにも行くので6月も全力だぞオイ