Lua堆栈操作的复杂性(Lua C API)

Question

在Lua C API中，它提供了几个堆栈操作函数，如Lua's document中提到的。

int   lua_gettop (lua_State *L);
void  lua_settop (lua_State *L, int index);
void  lua_pushvalue (lua_State *L, int index);
void  lua_remove (lua_State *L, int index);
void  lua_insert (lua_State *L, int index);
void  lua_replace (lua_State *L, int index);

我的第一个问题是，这些函数的复杂度是多少？是 O(1) 还是 O(|index|)？我检查了Lua manual Lua 似乎有两种不同的堆栈实现(基于堆栈和基于寄存器)。

更具体地说，如果我想从lua堆栈中读取并弹出前三个元素，我可以想到以下两种实现方式，我可以知道哪一种更高效/建议的方式吗？

解决方案 1 - 读取并弹出每个值:

for (int i = 0; i < 3; ++i) {
  values[i] = lua_tostring(lua_state, -1);
  ...
  lua_pop(lua_state, 1);
}

解决方案 2 -- 读取全部内容，然后弹出全部内容:

for (int i = 0; i < 3; ++i) {
  values[i] = lua_tostring(lua_state, -1 - i);
}
...
lua_pop(lua_state, 3);

Answer 1

Lua 5.3 defines lua_pop 为

#define lua_pop(L,n)            lua_settop(L, -(n)-1)

和lua_settop可见here ;它将用nil填充堆栈槽，以便可以对这些值进行GC。所以它的 O(1) 与 arg 1。

读取每个值的复杂度为 O(1)，N 个值的弹出复杂度为 O(N)。

因此，您的两种方法应该大致相同。

回复:在 O(1) 中读取值，函数 index2addr是将堆栈偏移量转换为地址的东西。