Luaの区間
Luaの添え字が1から始まることは衆人の知るところである。毀誉褒貶について、私は知らない。添え字を1から始めるとLuaの仮装機械と標準ライブラリが喜ぶということを、私は知る。
それはさておき。
不要なメモリの確保は絶対悪である。もちろん、絶対悪などという言葉は存在しない。訂正しよう。不要なメモリの確保は単なる悪である。
だから、メモリの区間を指定する。C++ならば[first, last)が一般的だ。last - firstによって（差の演算が許されていたならば）距離を計算できて便利だ。
Luaでは[i, j]であることは衆人の知るところである。そろそろ衆人の意味が崩壊しているけれど、気にせずともよろしい。閉区間である。
本物のLuaの区間の話をしよう。
[i, j]の解釈について、いくつかの規則がある。以下では、区間が対象とする文字列やシークエンスの長さをnとする。また、iおよびjはnilまたは整数であるとする。
i==nilならば、エラーになるか既定値が用いられるstring.byteの既定値は1である。string.subはエラーになる
j==nilならば、エラーになるか既定値が用いられるstring.byteの既定値はiである。string.subの既定値はnである。
i<0ならば、i=n+i+1に変換されるj<0ならば、j=n+j+1に変換されるi<1ならば、i=1に修正されるj>nならば、j=nに修正されるi>jならば、空の区間である
くだくだしく書いた。しかし、lstrlib.cのstr_subの実装を見たほうが早い。
Lua 5.3の命令セット入門
MOVEを基準として、命令ごとにどれくらい時間がかかるかを比べた。当たり前だけれど、メモリ確保は時間がかかるので避ける。
MOVEとだいたい同じくらい
MOVELOADKLOADBOOLGETUPVALSETUPVALUNMNOT
MOVEの1.5倍くらいまで
ADDSUBMULBORBXORBNOTVARARG（書き込み先がレジスタ1個の場合）
MOVEの3倍くらいまで
DIVBANDSHLSHRLENTESTTESTSETCLOSURE（上位値を持たない空の関数の場合）
MOVEの5倍くらいまで
GETTABUP（整数インデックス）GETTABLE（整数インデックス）SETTABUP（整数インデックス）SETTABLE（整数インデックス）POWEQLTLE
MOVEの8倍くらいまで
MODIDIV
それ以上
おしなべてTAILCALLはCALLよりも速い。速くならない場合もあるので、高速化を目的として、無理にTAILCALLを使う必要はないかもしれない。それよりも、おそらく、メモリ確保のコストが効いている。
関数呼び出しのコストは、だいたいMOVEの15〜30倍程度だと見なせばよいと思われる。
NEWTABLECONCATCALLTAILCALL
正規表現入門 (3)
前回までのあらすじ。EREに入門したはずなのに、Localeの隘路にはまりこんでいた。
今回のあらすじ。不正 (invalid) と未定義 (undefined) の隘路にはまりこむ。
正規表現クイズ！
a{4,2}a{4}{2}^$$^^{0}$${0}^
答えあわせタイム！
a{m,n}はmがn以下でなければならないので不正- 未定義（GNU実装では
a{8}と等価になる。エラーになる実装もある） - 空文字列にマッチする
- 空文字列にマッチする
- 未定義（GNU実装では空文字列にマッチする。エラーになる実装もある）
- よく判らない（GNU実装では空文字列にマッチする。エラーになる実装もある）
よく判らないのはEREの文法がウンコだから。歴史があるンだろう。経緯があるンだろう。実装を拾いあつめ、最大公約数を求めたら、ウンコがあった。きっと、そういうことなんだろう。
One or more
ERE_dupl_symbolsappearing first in an ERE, or immediately following '|', '^', or '('
だいたい、^や$に結合の優先順位が定められているのも良く判らない。^foo|bar$が、(^foo)|(bar$)であって^(foo|bar)$でないことを明確にしたいという思いがあるンだろう。思いなんて知ったことか。（PCREやECMAScriptがそうであるように）ゼロ幅表明として扱ったほうがスッキリする。
続くだろうか。
正規表現入門 (2)
前回までの正規表現！ 「POSIX LocaleのLC_COLLATEにはcollating symbolもcollating elementもない。伝説の木の下で告白を、じゃなかった、POSIX Localeの下で[.または[=で始まるハイクを詠め。カイシャクしてやる」と言ったな。あれは嘘だ。ゴメン！ ゴメン！ 一旦ゴメン！
META_CHARを含むBracket Expressionを書くたったひとつの冴えないやりかたは、
[[.^.][.-.][.].]]
と書くこと。ホントだよ。BoostのEREの説明にも書いてある。
Collating elements may be used in place of escapes (which are not normally allowed inside character sets), for example [[.^.]abc] would match either one of the characters 'abc^'.
人類のおおかたの直感に反して、なかんずく私の浅い理解に反して、
[^\^\-\.]
と書くことはできないらしい。
Localeを笑う者はLocaleに泣く。POSIX Localeであっても、ASCIIの範囲について照合順序が定義されている。定義されていないと困る。とても困る。POSIX LocaleのLC_COLLATEを再読する。collating-symbolキーワードもcollating-elementキーワードもない。collating-identifierはあった。127個あった。つまり、自分自身であるような127個のcollating elementが存在する。そういうことなんだろうと思う。Locale難しい。Locale難しすぎて、あやまり倒しに進化するレベル。土下座deドミノ！
続くかも。
あるいはHash DoS
配列など存在しない（キットラー風に）。Luaには存在しない。
にもかかわらず、Luaのテーブルは配列のようにふるまう。あなたがC++ならば、連続した整数をインデックスに使うとき、Luaのテーブルはあたかもstd::vectorのようにふるまうと理解してかまわない。時間的にも、空間的にも。
連続していない整数をインデックスに使う場合は？
次の人工的な例を考えてみてほしい。
local M = 1024
local N = ...
local t = {}
for i = 0, M - 1 do
t[i * N + 1] = 42
end
いくつかのNについてマイクロベンチマークを行った（2.7GHzのCore i7のうえのMac OS X 10.9のうえのLua 5.3.0で）。
| name | average |
|:----- | -----------:|
| N=1 | 30.55 usec |
| N=255 | 60.30 usec |
| N=256 | 609.38 usec |
| N=257 | 60.05 usec |
Nが1のとき、もっとも高速である。このとき、Luaのテーブルはおそらくハッシュ表を使わない。つまり、インデックスは実装内部のCの配列の添字にほとんど等しい。
Nが256のとき、しかし、Nが255や257の場合に比べても10倍遅い。いったいなぜだろう？
理由は簡単で明白だ。そういうハッシュ関数だから。
Nが大きいとき、Luaのテーブルはまさにハッシュ表となる（ハッシュ表を経由せず、直接に配列にアクセスできる場合がほとんどなくなる）。整数のハッシュ関数は、実は単なるビットマスクである。ハッシュ表のサイズに応じて下位ビットがハッシュ値に採用される。Nが256のとき、下位8ビットは常に0x01になる。ハッシュが衝突する。
このハッシュ関数は、とても素直で、おおかたの場合にうまくいく。あるいは素直すぎるというべきかもしれない。
それじゃあ、現実の世界でこれが問題になるのはどんな場合だろう。たとえば、疎行列をLuaのテーブルで表現するときに気をつけるべきかもしれない。うかつなサイズのほぼ対角行列を作るのは人生によくあることだ。あれはもう十五年前の話になる。私が物理シミュレーションのコードを書いていたころ、おっと、この話は長くなるからやめよう。
正規表現入門 (1)
私の正規表現の理解は浅い。SUSのRegular Expressionsの節を読みたくないあまり、うっかりpcregrepを使ってしまうくらい浅い。と言い条、PCREとECMAScriptの正規表現の区別もあいまいだ。一念発起してEREの仕様を読みはじめた。なんたることか、いつのまにかLocaleの勉強をしていた。Locale死すべし、慈悲は無い。
BREであれ、EREであれ、複雑さの大半はBracket Expressionにある（だって共通なんだもの）。
[fuck]
みたいなの。なんだ、簡単じゃん。うん、Localeさえなければね。NISやNFSやX Window Systemが存在するように、Localeが存在する残念な世界に私たちは生きている。だから、
[.fuck.] collating symbol
[=fuck=] equivalence class expression
[:fuck:] character class expression
たちが存在する。死に体。まえのふたつは、LC_COLLATEで定義されるあれで、さいごのはLC_CTYPEで定義されるこれだ。
朗報がある。私たちがUNIXであり、また、UNIXが私たちであるならば、POSIXつまりC Localeだけが必要である。というか、それ以外のことなんか知らないし知りたくない（知りたくなかった！ 知りたくなかったんだ！）し、Unicodeに詳しいオトナにはならないと、あの夏の日、校庭に沈む夕陽に誓ったじゃないか。あるいは、あの秋の日、金色に染めあげられた銀杏並木で。いやいや、誓ったのはもっと別のことだ。
与太はさておき。POSIX LocaleのLC_COLLATEにはcollating symbolもcollating elementもない。伝説の木の下で告白を、じゃなかった、POSIX Localeの下で[.または[=で始まるハイクを詠め。カイシャクしてやる。けれど、character class expressionだけはマジメに扱わなければならない。POSIX LocaleのLC_CTYPEに書かれたとおりに読みかえるくらいのフマジメさで。つまり、
[:alpha:] = A-Za-z
続くかも。
配列など存在しない（キットラー風に）。Luaには存在しない。
配列など存在しない（キットラー風に）。Luaには存在しない。シークエンスは存在するけれど。にもかかわらず、LuaのJSONエンコーダは、テーブルをオブジェクトとしてエンコードするか配列としてエンコードするかを決定しなければならない。
典型的な問題の例を挙げよう。
{ 17, nil, 23, nil, 37, nil, 42, nil, 69 }
というテーブルが与えられたとき、どちらのJSONにエンコードされるべきだろう。
{"0":17,"2":23,"4":37,"6":42,"8":69}
だろうか？（そう、オブジェクトの名前は文字列でなければならない、JSONにおいては）
[17,null,23,null,37,null,42,null,69]
だろうか？
おそらく、後者だろう。しかし、いったいどうして？
問題を整理しよう。
シークエンスは存在する。しかし、シークエンスをJSON配列として扱うべきかどうかは判らない。
setmetatable({ [666] = 42 }, { __len = function () return 666 end })
は配列として扱われるべきだろうか。
判らない。
LuaのJSONエンコーダは、だからおそらく、疎密という概念を導入した。疎なシークエンスはオブジェクトとしてエンコードし、密なシークエンスは配列としてエンコードする。
最大の添字が要素数の二倍、これが判定基準（のひとつ）である。魔法の数字。しかし、いったいどうして？
最大の添字がmであり、要素数がnであるようなテーブルを考えよう。簡単のためにmが1以上9以下だとすると、オブジェクトとしてエンコードした場合のオーバーヘッドは
n * 4
文字ぶんである。これは各要素に、たとえば添字が2の場合に
“2”:
という名前を付けなければならないから（ここではmが一桁だと仮定している）。配列としてエンコードした場合のオーバヘッドは
(m - n) * 5
文字ぶんである。これは存在しない要素について
null,
を挿入しなければならないから。つまり、オブジェクトとしてエンコードしたほうが配列としてエンコードするよりも文字数が少なくなる条件は
n * (9 / 5) < m
となる。つまり、最大の添字が要素数の1.8倍よりも大きな場合ということ。最初に挙げた問題の例はちょうどこの場合になっている。もちろん、mの桁数が増えれば、オブジェクトとしてエンコードした場合のオーバーヘッドは増えていく。もちろん、ここでは人間の《思い》は論じられていない。
人間の《思い》なんて窓から投げすてちまえ！
（このようなrationaleはどこかに書かれているはずだけれど、私は見つけられなかった）
