gpt4 book ai didi

arrays - Lua 表是如何在内存中处理的?

转载 作者:行者123 更新时间:2023-12-04 18:39:20 25 4
gpt4 key购买 nike

lua 如何处理表的增长?

是否相当于ArrayList在 java ? IE。一个需要连续内存空间的,随着它比已经分配的空间大,内部数组被复制到另一个内存空间。

有没有聪明的方法来引导它?

我的问题是,表是如何存储在内存中的?我不是在问如何在 Lua 中实现数组。

最佳答案

(假设您指的是 Lua 的最新版本;描述 5.3 的行为应该(几乎?)与 5.0-5.2 相同。)

在幕后,一个表包含一个数组和一个散列部分。两者(独立地)以二次幂的形式增长和收缩,如果不需要,两者都可能不存在。

大多数键值对将存储在哈希部分。但是,所有正整数键(从 1 开始)都是存储在数组部分的候选对象。数组部分只存储值而不存储键(因为它们等价于数组中元素的位置)。最多允许一半的分配空间为空(即包含 nil s - 作为间隙或作为尾随空闲插槽)。 (会留下太多空槽的数组候选将被放入散列部分。如果数组部分已满但散列部分有剩余空间,则任何条目都将进入散列部分。)

对于数组和散列部分,插入可以触发调整大小,如果之前已经删除了足够多的条目,则可以调整到下一个较大的 2 次方或下降到任何较小的 2 次方。 (实际上触发向下调整是非常重要的: rehash 是唯一调整表格大小的地方(并且两个部分同时调整大小),如果没有,它只会从 luaH_newkey 调用两部分中的任何一个都有足够的空间1。)

更多信息可以查看The Implementation of Lua 5.0的第4章。 ,或检查来源:基本上所有相关的事情都发生在 ltable.c 中。 ,有趣的阅读起点是 rehash (in ltable.c ) (调整大小功能)和主解释器循环 luaV_execute (in lvm.c )或更具体地说 luaV_settable (also there) (在表中存储键值对时会发生什么)。

1举个例子,为了缩小包含大数组部分且没有散列的表,您必须清除所有数组条目,然后向散列部分添加一个条目(即使用非整数键,该值可能是任何包括 nil ),最终得到一个不包含数组部分和 1 元素哈希部分的表。
如果两个部分都包含条目,则必须首先清除哈希部分,然后向数组部分添加足够的条目以填充数组和哈希组合(以触发调整大小,这将使您拥有一个包含大数组部分的表和没有散​​列),然后像上面一样清除数组。 2(首先清除数组,然后散列将不起作用,因为在清除这两个部分后,您将没有数组和一个巨大的散列部分,并且您无法触发调整大小,因为任何条目都将进入散列。)

2实际上,扔掉 table 并重新制作一张 table 要容易得多。为了确保表会缩小,您需要知道实际分配的容量(这不是当前的条目数,而且 Lua 不会告诉您,至少不会直接告诉您),然后获取所有步骤和所有大小都恰到好处——混淆步骤的顺序或无法触发调整大小,你最终会得到一个巨大的表,如果你将它用作数组,它甚至可能执行得更慢......(数组候选存储在hash 还存储它们的键,例如缓存行中有用数据量的一半。)

关于arrays - Lua 表是如何在内存中处理的?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29928379/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com