haskell Solo如何防止空间泄漏?

vcirk6k6  于 2022-11-14  发布在  其他
关注(0)|答案(3)|浏览(151)

我偶然看到了关于Solo的文档,一个元素元组,有点困惑于它是如何说它可以防止空间泄漏的,这让我怀疑我没有理解Haskell内存模型和/或垃圾收集器是如何工作的。
引用医生的话,他们说:
Solo最重要的特性是可以强制其“外部”(通常通过模式匹配)而不强制其“内部”,因为它被定义为一个数据类型而不是一个新类型。当编写一个函数从数据结构中提取一个值时,这一点很有用。假设你编写了一个数组的实现,并只提供这个函数来索引它们:

index :: Array a -> Int -> a

现在,假设有人想从数组中提取一个值,并将其存储在一个惰性值有限Map/字典中:

insert "hello" (arr `index` 12) m

这实际上会导致空间泄漏。直到值(现在隐藏在Map中)被强制,值才真正从数组中提取出来。这意味着整个数组可能只通过该值保持活动!通常,解决方案是使用严格的Map,或者在存储值之前强制该值,但对于某些用途,这是不希望的。
这就是我理解起来有困难的地方。假设a被装箱了,因此数组arr是一个指针数组(如果它没有被装箱,a就已经被求值了,这个参数就没有意义了)。
我猜在这个数组arr中有一个指针指向一个未赋值的thunk,它的类型是a,然后我们把它放在map中,所以map现在包含了一个指向a类型的未赋值thunk的指针。现在我不明白为什么这个数组arr需要在这个点上保持活动状态。我们在map中创建的任何东西都不指向arr。map有自己的指针指向a类型的未赋值thunk,它可以在空闲时对它求值。唯一能让arr保持活动的可能是未赋值thunk是否依赖于数组arr,但如果是这种情况,我不确定将值 Package 在Solo数据类型中有什么帮助?
我确信我错过了一些东西。我怀疑理解我错过了什么会暴露我上面的想法是错误的。如果我能找出我错在哪里,那是一件好事。所以有什么想法/解释吗?

hwamh0ep

hwamh0ep1#

Haskell中有两种“空间泄漏”:一种是在thunk上浪费空间,而在早期生成值会更有空间效率;另一种是在大数据结构上浪费空间,而在后期生成它们(或者根本不生成)会更有效率。
作者们正在考虑这样一个表达式:

index arr 12

想象arr是一个大的数据结构,结果是包含在其中的单个元素; index所做的一切就是选择元素。如果表达式index arr 12被保留为形实转换,则形实转换将必然包含对arr的引用,因此,当形实转换处于活动状态时,垃圾收集器将无法回收arr的内存。
通常要做的事情是安排index arr 12比实际需要的时间更早执行(正如作者所建议的,将其放在严格的Map中而不是放在懒惰的Map中,但实际上并不需要“将其放在Map中”的上下文)。如果您在决定要得到的结果时强制使用表达式index arr 12(就像一个严格的Map在你插入一些东西时所做的那样),而不是在你实际使用它做任何事情的时候,那么函数index已经在那个决定点运行完成,对arr的引用不再需要保留,直到你使用结果。
但是请记住,强制某个值将其计算为最外层的数据构造函数. index并不涉及任何数据构造函数,因为它只返回一个已经在arr中的值.所以通过计算index arr 12得到的最外层的数据构造函数将是来自任何类型的元素.但是如果arr的元素(或至少索引为12的元素)* 本身存储为未计算的thunk ?如果这些元素实际上很大,完全生成其中一个元素并不比存储一个thunks 1的大数组好多少。(保持一个大的thunk太长时间),但导致了另一个(过早地产生一个大的值)。如果不确定所涉及的类型,我们就不能知道哪个更糟糕!
问题是对最外层数据构造函数的求值已经“太多”了。我们希望求值进行得足够远,不再依赖于arr(即知道它包含了我们要返回的元素中的哪一个),但我们不希望实际输入一个表示该元素的形实转换程序。
在这里使用Solo的方法就是简单地将数据构造函数 * 包裹 * 返回的元素,因此当您将thunk强制到最外层的构造函数时,您将得到Solo,而不会再进一步。作者指出,对于索引thunk占用整个数组而导致的空间泄漏问题,一个常见的解决方案是“为了包括能够在任意应用上下文中产生其结果的索引函数:indexA :: Applicative f => Array a -> Int -> f a“,并且您可以使用Solo作为应用函数,将额外的数据构造函数放在正确的位置,而无需使用实际上具有任何有趣效果的应用函子。
据我所知,用Solo Package 只能解决 * 第二个 * 潜在的空间泄漏。如果将indexA arr 12 :: Solo a作为thunk,它不会神奇地停止依赖arr。但是,它使您能够使用早期求值来解决arr空间泄漏,而不必接受来自元素本身的潜在泄漏。
1或者仅仅是因为完全生产它在时间或空间上的成本已经足够高,以至于我们还不想为此付出代价,而且我们可能还没有完全确定要使用它;如果下游消费者不需要它,而我们宁愿不产生它,
即使 * 该元素比原始数组小得多(我们所需要的只是它比表示自身的thunk小)。

yftpprvb

yftpprvb2#

首先 , 你 引用 的 文档 有 一 个 错误 , 它 实际 上 相当 相关 。

insert "hello" (arr index 12) m

中 的 每 一 个
应该 是

insert "hello" (index arr 12) m

格式
实际 上 , 它 确实 保存 了 一 个 指向 arr 的 指针 。 在 index arr 12 被 求值 之前 , 它 是 一 个 thunk , 保存 了 指向 indexarr12 的 指针 。 指向 index12 的 指针 不是 什么 大 问题 , 但 arr 可能 很 大 。
至于 Solo 的 作用 ... ... 一般 来说 , 它 不会 起 作用 。 这 是 一 个 非常 奇怪 的 说法 。 比如 , 他们 提出 了 一 个 函数

indexA :: Applicative f => Array a -> Int -> f a

格式
然后 使用 它 :

case arr indexA 12 of
    Solo a -> insert "hello" a m

格式
但是 这 实际 上 不会 有 任何 帮助 , 除非 indexA 有 一 个 真正 意 想不到 的 实现 。 Solopure 的 实现 是 非 严格 的 , 正如 从 数据 类型 的 描述 中 所 预期 的 那样 。 因此 , 预期 的 indexA 的 实现 只是 用 pure Package 查找 的 结果 :

indexA arr i = pure $ index arr i

格式
为了 使 所 提供 的 解释 有 任何 意义 , 实现 需要 更 像 这样 :

indexA arr i = pure $! index arr i

格式
我 想 , 如果 一 个 库 提供 了 该 函数 , 那么 只有 当 它 具有 更 严格 的 实现 时 , 它 才 有 意义 , 但 我 很 谨慎 地 假设 这 是 这样 一 个 函数 的 实现 , 或者 Solo 实际 上 对 解决 本 文档 提出 的 问题 很 有用 。
现在 , 关于 Solo 的 严格 性 属性 有 一些 实际 上 有用 的 东西 , 特别 是 对于 Monad 示例 。 让 我们 与 IdentityMonad 示例 进行 对比 :

ghci> do { x <- pure () ; y <- undefined ; pure x } :: Identity ()
Identity ()

ghci> do { x <- pure () ; y <- undefined ; pure x } :: Solo ()
*** Exception: Prelude.undefined
CallStack (from HasCallStack):
  undefined, called at <interactive>:8:26 in interactive:Ghci4

格式
Solo 被 提升 而 Identity 没有 被 提升 的 事实 使得 SoloMonad 示例 更加 严格 。 (>>=) 在 其 第 一 个 参数 中 强制 对外 部 Solo 构造 函数 求值 ,这 意味 着 它 实际 上 会 注意 到 它 是否 得到 了 一 个 底部 值 作为 它 的 第 一 个 参数 , 而 它 在 其他 情况 下 是 不 被 使用 的 。t 在 运行 时 存在 , 对 它们 求值 只是 将 所有 计算 推迟 到 以后 进行 , 从而 使 (>>=) 实现 不 那么 严格

mrwjdhj3

mrwjdhj33#

我猜数组arr中有一个指针指向一个未赋值的,类型为a的thunk,然后我们把它放到map中,所以map现在包含一个指针指向一个未赋值的,类型为a的thunk,现在我不明白为什么这个数组arr需要在这一点上保持活跃。
关键是insert "hello" (index arr 12) m * 并不 * 只是将现有的未赋值的thunk放入map中,它创建了一个新的thunk来表示index arr 12,并将 * 那个 * 存储在map中,而且这个thunk需要arr仍然存在。

相关问题