ほとんどの環境において、値のサイズ\(S_v\)は16バイトである。
空のテーブルのサイズ\(S_t\)は、ILP32では32バイト、LP64/LLP64では56バイトである。
1以上の連続した整数だけをインデックスに使うとき、テーブルは配列のように、つまり、C++のstd::vectorのようにふるまう。
倍々でメモリが確保されるので、要素数\(n\)のとき、およそ\(S_a(n) = S_v 2^{\mathrm{ceil}(\log_2(n))}\)バイトが必要になる。
当然、\(S_v n \le S_a(n) \lt 2 S_v n\)である。
std::vectorのreserveと同様の機能は命令セットレベルでは提供されているが、言語レベルでは提供されていない。
値を束縛することにより、クロージャをデータ構造として利用できる。 必要なメモリの量はテーブルよりも増える。
リンクリストの素朴な実装は
template <class T>
struct node {
node* next;
node* prev;
T value;
};
のように与えられる。要素数\(n\)のとき、C++の構造体をLuaのテーブルで表現する場合、およそ\((S_t + 3 S_v) n\)バイトが必要になる（実際の値はこれよりも大きくなる）。
以下のように、前後のノードへのポインタと値を個々のテーブルに分解して保存する場合、すくなくともおよそ\(3 S_a(n)\)バイトが必要になる。
local next = {}
local prev = {}
local value = {}
LP64/LLP64では、あきらかに\(3 S_a(n) \lt (S_t + 3 S_v) n\)が成立する。 ILP32では、配列が伸長した直後など必ずしも成立しない。
\(m\)個の要素を持つ場合について、\(m S_a(n)\)と\((S_t + m S_v) n\)を比較すると、 \[ \mathrm{ceil}(\log_2(n)) - \log_2(n) \lt \log_2(\frac{1}{m} \frac{S_t}{S_v} + 1) \] 個々のテーブルに分解して保存したほうが有利になる確率を下表に示す。
| m | ILP32 | LP64/LLP64 |
|---|---|---|
| 1 | 100.0% | 100.0% |
| 2 | 100.0% | 100.0% |
| 3 | 80.0% | 100.0% |
| 4 | 66.7% | 93.3% |
| 5 | 57.1% | 82.4% |
| 6 | 50.0% | 73.7% |
| 7 | 44.4% | 66.7% |
| 8 | 40.0% | 60.9% |
| 9 | 36.4% | 56.0% |
| 10 | 33.3% | 51.9% |
| 11 | 30.8% | 48.3% |
| 12 | 28.6% | 45.2% |
なお、前後のノードへのポインタと値を個々のテーブルに分解して保存するほうが、GC対象が減る点において有利であると考えられる。 また、C++の構造体をLuaのテーブルで表現する際に文字列キーを用いるならば、そのコストにも注意する必要がある。
\(m\)行\(n\)列の密な行列を考える。 1次元で表現する場合、\(S_1(m, n) = S_t + S_a(m n)\)バイトが必要になる。 2次元で表現する場合、\(S_2(m, n) = S_t + S_a(m) + m (S_t + S_a(n))\)バイトが必要になる。 \(S_1\)の上限は\(S_t + 2 S_v m n\)で、\(S_2\)の下限は\(S_t m + S_v m + S_v m n\)なので、 \(S_1\)が常に有利になるのは\(\frac{S_t}{S_v} \gt \frac{m}{m - 1}(n - 1)\)のときだけである。 つまり、基本的な議論は前節に準じたものとなる。
MicroXMLが示したように、単純化されたDOMノードは名前と属性マップと子要素のリストで構成できる。 Luaにおいてはひとつのテーブルで表現することもできる。
木構造の素朴な実装は、
template <class T>
struct node {
node* parent;
node* child;
node* next;
node* prev;
T value;
};
のように与えられるので、リンクリストと同様に考察ができる。