lua - 垃圾收集和字符串到字符串函数的内存

Question

以下练习来自p。 Ierusalimschy 的 Programming in Lua(第 4 版)的 234。 (注意:在本书的前面，作者明确拒绝使用memoization这个词，并坚持使用memorization代替。记住这一点，因为你阅读下面的摘录。)

Exercise 23.3: Imagine you have to implement a memorizing table for a function from strings to strings. Making the table weak will not do the removal of entries, because weak tables do not consider strings as collectable objects. How can you implement memorization in that case?

我很难过!

我的部分问题是我无法设计出一种方法来实现字符串的(垃圾)收集。

相比之下，对于表，我可以为其配备终结器，它会在表即将被收集时报告。有没有办法确认给定的字符串(并且只有那个字符串)已被垃圾回收？

---

另一个困难是简单地弄清楚所需函数的规范是什么。我能做的最好的事情就是弄清楚它不是什么。在本书的前面(第 225 页)，作者给出了以下“内存”功能的示例:

Imagine a generic server that takes requests in the form of strings with Lua code. Each time it gets a request, it runs load on the string, and then calls the resulting function. However, load is an expensive function, and some commands to the server may be quite frequent. Instead of calling load repeatedly each time it receives a common command like "closeconnection()", the server can memorize the results from load using an auxiliary table. Before calling load, the server checks in the table whether the given string already has a translation. If it cannot find a match then (and only then) the server calls load and stores the result into the table. We can pack this behavior in a new function:

[standard memo(r)ized implementation omitted; see variant using a weak-value table below]

The savings with this scheme can be huge. However, it may also cause unsuspected waste. ALthough some commands epeat over and over, many other commands happen only once. Gradually, the ["memorizing"] table results accumulates all commands the server has ever received plus their respective codes; after enough time, this behavior will exhaust the server's memory.

A weak table provides a simple solution to this problem. If the results table has weak values, each garbage-collection cycle will remove all translations not in use at that moment (which means virtually all of them)¹:

local results = {}
setmetatable(results, {__mode = "v"})  -- make values weak
function mem_loadstring (s)
  local res = results[s]
  if res == nil then                   -- results not available?
    res = assert(load(s))              -- compute new results
    result[s] = res                    -- save for later reuse
  end
  return res
end

正如原始问题陈述所指出的，当要内存(r)化的函数返回字符串时，此方案将不起作用，因为垃圾收集器不会将字符串视为“可收集的”。

---

当然，如果允许更改所需函数的接口(interface)，而不是返回一个字符串，而是返回一个单例表，其唯一项是真实结果字符串，那么问题几乎就变成了微不足道，但我很难相信作者脑子里有这么粗略的“解决方案”²。

以防万一，我使用的是 Lua 5.3。

---

^{1 顺便说一句，如果 memo(r)ization 的基本原理是避免不必要地更频繁地调用 load，则作者提出的方案对我来说没有意义。在我看来，这个方案是基于这样一个假设(实际上是一种启发式)，即经常使用并因此会支付 memo(r)ize 费用的翻译也是始终可以访问(因此不可收集)的翻译.我不明白为什么情况必然如此，甚至可能如此。}

^{2 可以用 __tostring 方法的形式给这只 pig 涂上口红，这样表格(备忘录返回的表格) (r)ized function) 在某些上下文中伪装成字符串；不过，它仍然是一头 pig 。}

Answer 1

你的想法是正确的:将字符串包装成一个表(因为表是可收集的)。

function memormoize (func_from_string_to_string)
   local cached = {}
   setmetatable(cached, {__mode = "v"}) 
   return 
      function(s)
         local c = cached[s] or {func_from_string_to_string(s)} 
         cached[s] = c                    
         return c[1]
      end
end

而且我在这个解决方案中没有看到 pig :-)

one that is always reachable (and hence not collectable). I don't see why this should necessarily, or even likely, be the case.

在弱表中不会有“总是可达”的项目。
但是最频繁的项目只会在每个 GC 周期重新计算一次。
理想的解决方案(从不收集经常使用的元素)将需要更复杂的实现。
例如，当项目的“不活动计时器”达到某个阈值时，您可以将项目从普通缓存移至弱缓存。