如何在Elixir / Erlang中通过指针相等性比较两个结构体

8

(以下示例为Elixir语言。)

假设我有以下代码:

x = {1, 2}
a1 = {"a", {1, 2}}
a2 = {"a", {1, 2}}
a3 = {"a", x}

据我所知,以下代码会在不同的内存位置创建三个元组{1, 2}
使用运算符=====比较任何a变量始终返回true。这是可以预期的,因为这两个运算符仅在比较数字类型(即1 == 1.01 === 1.0不同)时有所区别。
因此,我尝试通过模式匹配比较结构,使用以下模块(严格创建以测试我的情况)。
defmodule Test do
  def same?({x, y}, {x, y}), do: true
  def same?(_, _), do: false
end

但是调用Test.same?(a1, a3)也会返回true

我该如何使用指针相等性比较两个结构体,以便确定它们是否是内存中的同一结构体?

谢谢


1
那是一个非常有趣的问题,我希望看到一个带有参考资料的答案,介绍Erlang虚拟机的工作原理,这将有助于解释Elixir/Erlang的机制。 - Nathan Ripert
@NathanRipert 我认为我已经回答了你想要的方式。 - mljrg
3
您可以查看这个链接:https://github.com/happi/theBeamBook,它可能有助于回答这类问题。简短回答:您不需要关心。Erlang被有意设计为隐藏这些实现细节。 - Onorio Catenacci
@OnorioCatenacci 是的,我不应该在意。但是我应该关注大型结构之间的重复,特别是当重复非常大时。正是在这种情况下,为了消除这种重复,我提出了这个问题。请参见我下面对这个问题的回答。 - mljrg
1
@OnorioCatenacci 如果我理解你所担心的问题(感谢这一点,我很赞赏),我知道 Erlang 会复制除大型二进制之外的所有内容,这意味着它将复制大型结构,从而再次生成重复,对吗?但是,如果这些可能有重复子树的结构始终存在于同一个进程中,那么在进程内去除这样的重复可以节省大量的内存。我所说的就是压缩同一进程内的大量重复数据。 - mljrg
显示剩余3条评论
5个回答

15
没有“官方”的方法来做到这一点,如果您认为您实际上需要这样做,我会说您正在做错事情,应该询问另一个关于如何实现您想要实现的目标的问题。因此,本答案以玩味和探索的精神提供,希望它能传播一些有关Erlang/Elixir VM的有趣知识。
有一个函数erts_debug:size/1,它告诉您一个Erlang/Elixir术语占用了多少内存“字”。 这张表格 告诉您各种术语使用多少字。特别是一个元组使用1个字,加上每个元素的1个字,再加上任何“非立即”元素的存储空间。我们正在使用小整数作为元素,它们是“立即数”因此是“自由”的。所以这个检查通过:
> :erts_debug.size({1,2})
3

现在让我们创建一个包含这两个元组的元组:

> :erts_debug.size({{1,2}, {1,2}})
9

有道理:两个内部元组各包含3个单词,而外部元组有1+2个单词,总共是9个单词。

但如果我们把内部元组放到一个变量中怎么办?

> x = {1, 2}
{1, 2}
> :erts_debug.size({x, x})
6

看,我们节省了3个单词!这是因为x的内容只计算一次;外部元组在两次指向同一内部元组。

因此,让我们编写一个小函数来帮助我们实现这一点:

defmodule Test do
  def same?(a, b) do
    a_size = :erts_debug.size(a)
    b_size = :erts_debug.size(b)
    # Three words for the outer tuple; everything else is shared
    a_size == b_size and :erts_debug.size({a,b}) == a_size + 3
  end
end

系统工作正常?看起来是的:

> Test.same? x, {1,2}
false
> Test.same? x, x
true

目标达成!


但是如果我们试图从已编译的模块中的另一个函数中调用此函数,而不是从iex shell中调用:

  def try_it() do
    x = {1, 2}
    a1 = {"a", {1, 2}}
    a2 = {"a", {1, 2}}
    a3 = {"a", x}

    IO.puts "a1 and a2 same? #{same?(a1,a2)}"
    IO.puts "a1 and a3 same? #{same?(a1,a3)}"
    IO.puts "a3 and a2 same? #{same?(a3,a2)}"
  end

那会打印:

> Test.try_it
a1 and a2 same? true
a1 and a3 same? true
a3 and a2 same? true

那是因为编译器足够聪明,能够看到这些文字相等,并在编译时将它们合并为一个项。


请注意,当术语被发送到另一个进程或存储在/从ETS表中检索时,此共享术语会丢失。有关详细信息,请参见Erlang效率指南的进程消息部分


@legoscia 我理解编译器在做什么,这与其他语言中许多编译器所进行的(常量折叠)[https://en.wikipedia.org/wiki/Constant_folding]非常相似。但如果我从两个文件创建了两个结构,并且在同一个进程中读取具有共享文本的内容,那么在运行时会发生什么?这些结构将共享与文件中相同内容对应的结构的相同部分吗? - mljrg
1
@legoscia 这意味着,如果两个文件中的相同内容必然导致两个结构中的内存重复,这正是我所期望的(也是正常的)。 - mljrg
1
那么我假设运算符=====会在内部检测两个子结构是否是同一个内存元素,如果是,则立即将它们比较为true,而不是在比较期间一直遍历相同的子结构。你知道这是真的吗? - mljrg
1
是的,这里发生了:https://github.com/erlang/otp/blob/fd591b6f7bb681dd5335a67e66b1d0b8ecf2a76f/erts/emulator/beam/utils.c#L2763-L2765 - legoscia
1
我想感谢您的时间,特别是告诉我关于函数 :erts_debug.size(x),这对我理解这个主题非常关键。 - mljrg
显示剩余2条评论

8
Erlang/OTP 22(以及可能是早期版本)提供了:erts_debug.same/2,它将允许您进行所需的内存指针测试。然而,请注意该函数未记录,并位于名为erts_debug的模块中,因此您应仅在调试和测试时依赖它,而永远不要在生产代码中使用它。
在我使用Erlang/Elixir的近9年中,我只用过一次,那是为了测试我们是否在Ecto中不必要地分配结构体。这里有提交记录供参考

7

让我回答这个问题:

开发者不需要显式地进行指针比较,因为Elixir已经在模式匹配和操作符=====(通过相应的Erlang操作符)中内部执行了该操作。

例如,给定以下代码:

a1 = {0, {1, 2}}
a2 = {1, {1, 2}}
x = {a1, a2}
s = {1, 2}
b1 = {0, s}
b2 = {1, s}
y = {b1, b2}

在IEx中,我们有以下内容:

Interactive Elixir (1.7.3) - press Ctrl+C to exit (type h() ENTER for help)
iex(1)> a1 = {0, {1, 2}}
{0, {1, 2}}
iex(2)> a2 = {1, {1, 2}}
{1, {1, 2}}
iex(3)> x = {a1, a2}
{{0, {1, 2}}, {1, {1, 2}}}
iex(4)> s = {1, 2}
{1, 2}
iex(5)> b1 = {0, s}
{0, {1, 2}}
iex(6)> b2 = {1, s}
{1, {1, 2}}
iex(7)> y = {b1, b2}
{{0, {1, 2}}, {1, {1, 2}}}
iex(8)> :erts_debug.size(x)
15
iex(9)> :erts_debug.size(y)
12
iex(10)> x == y
true
iex(11)> x === y
true

即,xy在内容上相等,但是在内存中不同,因为y占用的内存比x少,因为它在内部共享子结构s
简而言之,=====都进行内容和指针比较。指针比较是Erlang避免在比较的两侧遍历相同子结构的最有效方法,从而节省了大量时间。
现在,如果担心两个结构之间存在结构重复,例如当它们从具有类似内容的两个大文件中加载时,则必须将它们压缩成共享它们在其中内容相等的部分的两个新结构。这就是a1a2被压缩为b1b2的情况。

2
FYI: === 被映射到 Erlang 的 =:=,它会比较类型并在类型相同时委托给 ==。它不能再通过任何方式更加高效,因为它执行了一个额外的操作。 - Aleksei Matiushkin
3
@mudasobwa,这并不是完全正确的描述:例如,它会暗示{1.0, 1.0} === {1, 1}是真的,因为它们都是元组,它们的==是真的。相反,它与==一样是递归的,只是有一个单独的不同基本情况:它永远不会将浮点数和整数视为相等。 - Alexey Romanov
@AlexeyRomanov 是的,确实,我错过了递归部分,谢谢。 - Aleksei Matiushkin
2
@AlexeyRomanov 所以这两个运算符只在处理浮点数和整数时有所不同。 - mljrg
2
@mljrg 是的,那就是唯一的区别。 - Alexey Romanov

2
据我所知,它会在不同的内存位置创建三个元组{1, 2}。但实际上并非如此。Erlang虚拟机足够智能,只需创建一个元组并引用它即可。值得一提的是,这是因为所有内容都是不可变的。如果你发现自己像上面那样完成任务,那么你就错了。

你希望我在这里打出“Erlang VM in a nutshell”这本书吗? - Aleksei Matiushkin
你不能这样做,也不应该这样做。 - Aleksei Matiushkin
你真的希望我打字吗... 你不能简洁地用一段话解释一下Erlang是如何做到的吗?我很想知道它在运行时的效率如何。 - mljrg
1
假设我在同一进程中从两个文件创建了两个结构体,并且这些文件具有共同点。那么这些结构体是否会自动共享与文件中相同内容对应的结构体部分?如果不是,我该如何检测到? - mljrg
3
可能是,也可能不是。你不能依靠这个,这就是关键所在。 - Aleksei Matiushkin
显示剩余2条评论

2
似乎您无法获取Erlang变量的内存位置:我认为这是这个主题中的关键概念。因此,您只能比较数据,而不是指向这些数据的指针。

似乎当您创建多个具有相同值的变量时,它会在内存中创建新的数据,这些数据是变量名和与主要数据绑定(类似于指针)。 Erlang VM不会复制数据(我正在寻找一些证据..到目前为止,这只是我所看到的方式)。

请在此处写下证明,如果您找到了它。 - mljrg
@mljrg 我会的。我被好奇心吸引住了。 - Nathan Ripert

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接