✍️ 🔱 ♒️ LuaJIT表的剖析及其使用特点 👨‍🍳 👤 🏢

我不了解您，但我喜欢在不同系统中探索。在本文中，我想讨论Lua表的内部结构及其功能。Lua是我负责工作的主要编程语言，为了编写优质的代码，您至少需要了解一些幕后发生的事情。很好奇，我要我。

Lua有几种实现和几种版本。本文将主要关注Tarantool中使用的LuaJIT 2.1.0。与真正的LuaJIT相比，我们的版本略有修补，但这些差异与表无关。

如果您有兴趣，关于PUC-Rio实施中的表格，还有另一个很好的介绍[1]。

教育计划

Lua — , . ( ), key-value . ( nil). , — [2].

-- Empty table
local t1 = {}

-- Table as an array
local t2 = { 'Sunday', 'Monday', 'Im tired' }

-- Table as a hashtable
local t3 = {
    cat = 'meow',
    dog = 'woof',
    cow = 'moo',
}

-- Ordered map
local t4 = {
    'k1', 'k2', 'k3' -- stored in the array part
    ['k1'] = 'v1',   -- stored in the hash part
    ['k2'] = 'v2',   -- stored in the hash part
    ['k3'] = 'v3',   -- stored in the hash part
}

LuaJIT [3] ( , , ):

typedef struct GCtab {
  /* GC stuff */
  MRef array;     /* Array part. */
  MRef node;      /* Hash part.  */
  uint32_t asize; /* Size of array part (keys [0, asize-1]). */
  uint32_t hmask; /* Hash part mask (size of hash part - 1). */
} GCtab;

: -. . , LuaJIT , . , , Lua, , . : , . , .

LuaJIT tostring(), stdout printf().

, , [4]. :

diff --git a/src/lj_strfmt.c b/src/lj_strfmt.c
index d7893ce..45df53c 100644
--- a/src/lj_strfmt.c
+++ b/src/lj_strfmt.c
@@ -392,6 +392,51 @@ GCstr * LJ_FASTCALL lj_strfmt_obj(lua_State *L, cTValue *o)
     if (tvisfunc(o) && isffunc(funcV(o))) {
       p = lj_buf_wmem(p, "builtin#", 8);
       p = lj_strfmt_wint(p, funcV(o)->c.ffid);
+    } else if (tvistab(o)) {
+      GCtab *t = tabV(o);
+      /* print array part */
+      printf("--  a[%d]: ", asize);
+      for (i = 0; i < asize; i++) {
+        // printf(...);
+      }
+
+      /* print hashmap part */
+      printf("--  h[%d]: ", hmask+1);
+      for (i = 0; i <= hmask; i++) {
+        // printf(...);
+      }
     } else {
       p = lj_strfmt_wptr(p, lj_obj_ptr(o));
     }

, :

t = {}
tostring(t)
-- table: 0x40eae3a8
--  a[0]:
--  h[1]: nil=nil

, LuaJIT 0 1 -, nil nil (.. ). :

t["a"] = "A"
t["b"] = "B"
t["c"] = "C"
tostring(t)
-- table: 0x40eae3a8
--  a[0]:
--  h[4]: b=B, nil=nil, a=A, c=C

, , -. , — . LuaJIT ~~[5]~~ [5] ( ).

, , . traverse(), for .

traverse

- [4]. .

function traverse(fn, t)
    local str = ''
    for k, v, n in fn(t) do
        str = str .. string.format('%s=%s ', k, v)
    end
    print(str)
end

t1 = {a = 1, b = 2, c = 3}
tostring(t1)
-- table: 0x40eaeb08
--  a[0]:
--  h[4]: b=2, nil=nil, a=1, c=3

t2 = {c = 3, b = 2, a = 1}
tostring(t2)
-- table: 0x40ea7e70
--  a[0]:
--  h[4]: b=2, nil=nil, c=3, a=1

traverse(pairs, t1)
-- b=2, a=1, c=3

traverse(pairs, t2)
-- b=2, c=3, a=1

: . -, .

t2["c"] = nil
traverse(pairs, t2)
-- b=2, a=1
tostring(t2)
-- table: 0x411c83c0
--  a[0]:
--  h[4]: b=2, nil=nil, c=nil, a=1

print(next(t2, "c"))
-- a

, . — , .

: , lookup' . . main node , predecessor main ( ). O(n), . dead node . . [5].

, , . — :

t = {1, 2}
tostring(t)
-- table: 0x41735918
--  a[3]: nil, 1, 2
--  h[1]: nil=nil

Lua , . , LuaJIT . / .

, , ( ) — :

t = {[2] = 2, 1}
tostring(t)
-- table: 0x416a3998
--  a[2]: nil, 1
--  h[2]: nil=nil, 2=2

, , -. , : , .

: ?

: LuaJIT, Lua, .

, .

$ luac -l - <<< "t1 = {1, 2}"

        1       [1]     NEWTABLE        0 2 0   -- 2  , 0  -
        ...

— 1 -.

$ luac -l - <<< "t2 = {[2] = 2, 1}"

        1       [1]     NEWTABLE        0 1 1   -- 1  , 1  -
        ...

, , , . LuaJIT -, . , . .

pairs()

pairs() . . . LuaJIT pairs() , -. - -, :

t = table.new(4, 4)
for i = 1, 8 do t[i] = i end

tostring(t)
-- table: 0x412c6df0
--  a[5]: nil, 1, 2, 3, 4
--  h[4]: 7=7, 8=8, 5=5, 6=6
traverse(pairs, t)
-- 1=1, 2=2, 3=3, 4=4, 7=7, 8=8, 5=5, 6=6

: ?

: table.new(narr, nrec) — lua_createtable(L, a, h) Lua C API. (, ), .

. ( ) :

t[9] = 9
tostring(t)
-- table: 0x411e1e30
--  a[17]: nil, 1, 2, 3, 4, 5, 6, 7, 8, 9, nil, nil, nil, nil, nil, nil, nil
--  h[1]: nil=nil

. 99.9 % "" Lua , .

table.getn()

- . , — Lua [6].

3.4.6 – The Length Operator

The length of a table t is only defined if the table is a sequence, that is,
the set of its positive numeric keys is equal to {1..n} for some non-negative
integer n. In that case, n is its length. Note that a table like

    {10, 20, nil, 40}

is not a sequence, because it has the key 4 but does not have the key 3. (So,
there is no n such that the set {1..n} is equal to the set of positive numeric
keys of that table.) Note, however, that non-numeric keys do not interfere with
whether a table is a sequence.

, . — Lua undefined behavior. "" . LuaJIT lj_tab_len [7] :

/*
** Try to find a boundary in table `t'. A `boundary' is an integer index
** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
*/
MSize LJ_FASTCALL lj_tab_len(GCtab *t);

LuaJIT "". , , LuaJIT , :

print(#{nil, 2})
-- 2

print(#{[2] = 2})
-- 0

: ?

: .

tostring({nil, 2})
-- table: 0x410d5528
--  a[3]: nil, nil, 2
--  h[1]: nil=nil

tostring({[2] = 2})
-- table: 0x410d5810
--  a[0]:
--  h[2]: nil=nil, 2=2

LuaJIT , . , -, .

, . , undefined behavior . , .

table.sort()

1 #t, . , , :

local function is_array(t)
    if type(t) ~= 'table' then
        return false
    end

    local i = 0
    for _, _ in pairs(t) do
        i = i + 1
        if type(t[i]) == 'nil' then
            return false
        end
    end
    return true
end

Lua, , , , .

Pack / unpack

? , - . , :

local function vararg(...)
    local args = {...}
    -- #args == undefined behavior
end

— , .

- vararg(nil, "err"), . unpack(t), ( , , UB).

Lua [8] :

6.5 – Table Manipulation

unpack (list [, i [, j]])

Returns the elements from the given table. This function is equivalent to

    return list[i], list[i+1], ···, list[j]

except that the above code can be written only for a fixed number of elements.
By default, i is 1 and j is the length of the list, as defined by the length
operator #list.

, unpack(t, 1, #t) unpack(t, 1, n), n? , . varargs, table.pack(), :

t = table.pack(nil, 2)
tostring(t)
-- table: 0x41053540
--  a[3]: nil, nil, 2
--  h[2]: nil=nil, n=2

traverse(pairs, t)
-- 2=2, n=2
print(unpack(t, 1, t.n))
-- nil, 2 --  ,   UB

LuaJIT ( Tarantool) table.pack - , -DLUAJIT_ENABLE_LUA52COMPAT. :

function table.pack(...)
    return {..., n = select('#', ...)}
end

select('#', ...) [9], . , Lua [10] — , Lua C (Lua C API). .

ipairs()

— . . ipairs , while:

local i = 1
while type(t[i]) ~= 'nil' do
    -- do something
    i = i + 1
end

, "" undefined behavior — .

t = {1, 2, nil, 4}
print(#t) -- UB
-- 4
traverse(ipairs, t) -- Not UB
-- 1=1, 2=2

FFI

, type(x) ~= 'nil'. x == nil? , LuaJIT, PUC-Rio Lua, cdata:

ffi = require('ffi')
NULL = ffi.new('void*', nil)

print(type(NULL))
-- cdata
print(type(nil))
-- nil

print(NULL == nil)
-- true

if NULL then print('NULL is not nil') end
-- NULL is not nil

Tarantool, box.NULL. — if NULL ( if nil), NULL == nil.

LuaJIT — FFI . Lua, FFI Lua . LuaJIT . , [11]:

Lua tables may be indexed by cdata objects, but this doesn't provide any useful
semantics — cdata objects are unsuitable as table keys!

A cdata object is treated like any other garbage-collected object and is hashed
and compared by its address for table indexing. Since there's no interning for
cdata value types, the same value may be boxed in different cdata objects with
different addresses. Thus t[1LL+1LL] and t[2LL] usually do not point to the
same hash slot and they certainly do not point to the same hash slot as t[2].

, cdata- ( void*), , . Tarantool:

tarantool> t = {1}; t[1ULL] = 2; t[1ULL] = 3;
---
...

tarantool> t
---
- 1: 1
  1: 3
  1: 2
...

tarantool> t[1ULL]
---
- null
...

, , cdata , . uuid [12] clock.time64() Tarantool. , unsigned .

, FFI, :

tarantool> t = {'normal one'}
    t[1.0 + 2^-52] = '1.0 + 2^-52'
    t[0.1 + 0.3*3] = '0.1 + 0.3*3'
---
...
tarantool> t
---
- 1: normal one
  1: 1.0 + 2^-52
  1: 0.1 + 0.3*3
...

#t . — Undefined behavior.
ipairs() while type(t[i]) ~= 'nil' — , , .
pairs() , .
unpack, table.sort, table.insert, table.remove, -, undefined behavior #t.
"" (ffi) . .