Lua表如何在内存中处理? [英] How are Lua tables handled in memory?

问题描述

lua如何处理表的增长?

How does lua handle a table's growth?

它等效于Java中的ArrayList吗? IE.一个需要连续的内存空间，并且当它变得比已分配的空间更大时，内部数组将被复制到另一个内存空间.

Is it equivalent to the ArrayList in Java? I.e. one that needs continuous memory space, and as it grows bigger than the already allocated space, the internal array is copied to another memory space.

有一个聪明的方法来解决这个问题吗?

Is there a clever way to led with that?

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

My question is, how is a table stored in the memory? I'm not asking how to implement arrays in Lua.

推荐答案

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

(Assuming you're referring to recent versions of Lua; describing the behavior of 5.3 which should be (nearly?) the same for 5.0-5.2.)

在后台，一个表包含一个数组和一个哈希部分.两者都(独立地)以两步幂的方式增长和收缩，并且如果不需要它们，可能两者都不存在.

Under the hood, a table contains an array and a hash part. Both (independently) grow and shrink in power-of-two steps, and both may be absent if they aren't needed.

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

Most key-value pairs will be stored in the hash part. However, all positive integer keys (starting from 1) are candidates for storing in the array part. The array part stores only the values and doesn't store the keys (because they are equivalent to an element's position in the array). Up to half of the allocated space is allowed to be empty (i.e. contain nils – either as gaps or as trailing free slots). (Array candidates that would leave too many empty slots will instead be put into the hash part. If the array part is full but there's leftover space in the hash part, any entries will just go to the hash part.)

对于数组和散列部分，插入都可以触发调整大小，如果先前已删除足够多的条目，则可以调整为下一个较大的2的幂或减小为任何较小的2的幂. (实际上触发缩减大小并非易事: rehash 是唯一可以调整表大小(并且同时调整两个部分的大小)的地方，并且只能从

For both array and hash part, insertions can trigger a resize, either up to the next larger power of two or down to any smaller power of two if sufficiently many entries have been removed previously. (Actually triggering a down-resize is non-trivial: rehash is the only place where a table is resized (and both parts are resized at the same time), and it is only called from luaH_newkey if there wasn't enough space in either of the two parts¹.)

有关更多信息，请参阅 Lua 5.0的实现的第4章.或检查来源:基本上所有相关的内容都在 ltable.c 中发生，有趣的阅读起点是 rehash(在ltable.c中)(调整大小的功能)，并且主解释器循环 luaV_execute (在lvm.c中)或更具体地 luaV_settable( (在表中存储键值对时会发生什么).

For more information, you can look at chapter 4 of The Implementation of Lua 5.0, or inspect the source: Basically everything of relevance happens in ltable.c, interesting starting points for reading are rehash (in ltable.c) (the resizing function), and the main interpreter loop luaV_execute (in lvm.c) or more specifically luaV_settable (also there) (what happens when storing a key-value pair in a table).

¹ _{例如，要收缩包含大数组部分且没有哈希的表，您必须清除所有数组条目，然后将条目添加到哈希部分(即，使用非整数键，该值可以是包括 nil的任何值)，最后得到一个不包含数组部分和1元素哈希部分的表.
如果两个部分都包含条目，则必须首先清除哈希部分，然后将足够的条目添加到数组部分以填充数组和哈希值的组合(以触发调整大小，这将使您得到一个包含较大数组部分的表，并且 ² (先清除数组，然后再进行哈希运算将不起作用，因为在清除了这两个部分之后，您将没有数组，并且将没有很大的哈希值，并且您无法触发调整大小，因为任何条目都只会进入哈希值.)}

¹_{As an example, in order to shrink a table that contained a large array part and no hash, you'd have to clear all array entries and then add an entry to the hash part (i.e. using a non-integer key, the value may be anything including nil), to end up with a table that contains no array part and a 1-element hash part.
If both parts contained entries, you'd have to first clear the hash part, then add enough entries to the array part to fill both array and hash combined (to trigger a resize which will leave you with a table with a large array part and no hash), and subsequently clear the array as above.² (First clearing the array and then the hash won't work because after clearing both parts you'll have no array and a huge hash part, and you cannot trigger a resize because any entries will just go to the hash.)}

² _{实际上，丢掉桌子并制作一张新桌子要容易得多.为了确保缩小表，您需要知道实际分配的容量(哪个不是当前的条目数，哪个Lua不会告诉您，至少不是直接告诉您) ，然后正确设置所有步骤和所有大小–混合步骤顺序或无法触发调整大小，最终将得到一个巨大的表，如果将其用作数组，它甚至可能执行得更慢…(存储在哈希中的候选数组也存储了其键，例如高速缓存行中有用数据的一半.)}

²_{Actually, it's much easier to just throw away the table and make a new one. To ensure that a table will be shrunk, you'd need to know the actual allocated capacity (which is not the current number of entries, and which Lua won't tell you, at least not directly), then get all the steps and all the sizes just right – mix up the order of the steps or fail to trigger the resize and you'll end up with a huge table that may even perform slower if you're using it as an array… (Array candidates stored in the hash also store their keys, for half the amount of useful data in e.g. a cache line.)}

这篇关于Lua表如何在内存中处理?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！