为什么Maps的查找属性比Erlang中的Records慢？

Question

我正在阅读编程Erlang,在本书的第5章中说:

记录只是伪装的元组,因此它们具有与元组相同的存储和性能特征.映射比元组使用更多存储,并且查找属性较慢.

在我以前学过的语言中,情况并非如此.映射通常实现为哈希表,因此查找时间复杂度为O(1); 记录(具有名称的元组)通常实现为不可变List,查找时间复杂度为O(N).

在Erlang中实现这些数据结构有什么不同？

Answer 1

对于少量字段,记录查找和地图查找之间没有真正的实际性能差异.但是,对于大量字段,因为记录信息在编译时是已知的,而映射键不需要,因此映射使用与记录不同的查找机制.但是记录和地图并不是可互换的替代品,因此将它们与涉及少于几个字段的用例进行比较是毫无意义的IMO; 如果您在编译时知道所需的字段,请使用记录,但如果不知道,请使用映射或其他类似的机制.因此,以下仅关注查找一个记录字段和一个映射键的性能差异.

让我们看看两个函数的汇编程序,一个访问记录字段,另一个访问映射键.以下是功能:

-record(foo, {f}).

r(#foo{f=X}) ->
    X.

m(#{f := X}) ->
    X.

两者都使用模式匹配从给定的类型实例中提取值.

这是组件r/1:

{function, r, 1, 2}.
  {label,1}.
    {line,[{location,"f2.erl",6}]}.
    {func_info,{atom,f2},{atom,r},1}.
  {label,2}.
    {test,is_tuple,{f,1},[{x,0}]}.
    {test,test_arity,{f,1},[{x,0},2]}.
    {get_tuple_element,{x,0},0,{x,1}}.
    {get_tuple_element,{x,0},1,{x,2}}.
    {test,is_eq_exact,{f,1},[{x,1},{atom,foo}]}.
    {move,{x,2},{x,0}}.
    return.

这里有趣的部分开始于{label,2}.代码验证参数是否为元组,然后验证元组的arity,并从中提取两个元素.在验证元组的第一个元素等于原子后foo,它返回第二个元素的值,即记录字段f.

现在让我们看一下m/1函数的汇编:

{function, m, 1, 4}.
  {label,3}.
    {line,[{location,"f2.erl",9}]}.
    {func_info,{atom,f2},{atom,m},1}.
  {label,4}.
    {test,is_map,{f,3},[{x,0}]}.
    {get_map_elements,{f,3},{x,0},{list,[{atom,f},{x,0}]}}.
    return.

此代码验证参数是否为映射,然后提取与map键关联的值f.

每个功能的成本归结为装配说明的成本.记录函数有更多的指令,但它们可能比map函数中的指令便宜,因为所有记录信息在编译时都是已知的.当地图的关键数量增加时尤其如此,因为这意味着get_map_elements呼叫可能需要通过更多的地图数据来查找它正在寻找的内容.

我们可以编写函数来多次调用这些访问器,然后计算新函数的时间.以下是两组调用访问器的递归函数N时间:

call_r(N) ->
    call_r(#foo{f=1},N).
call_r(_,0) ->
    ok;
call_r(F,N) ->
    1 = r(F),
    call_r(F,N-1).

call_m(N) ->
    call_m(#{f => 1},N).
call_m(_,0) ->
    ok;
call_m(M,N) ->
    1 = m(M),
    call_m(M,N-1).

我们可以称之为 timer:tc/3来检查每个函数的执行时间.让我们每次拨打一千万次,但这样做50次并取平均执行时间.一,记录功能:

1> lists:sum([element(1,timer:tc(f2,call_r,[10000000])) || _ <- lists:seq(1,50)])/50.
237559.02

这意味着调用该函数一千万次平均需要238ms.现在,地图功能:

2> lists:sum([element(1,timer:tc(f2,call_m,[10000000])) || _ <- lists:seq(1,50)])/50.
235871.94

调用地图函数一千万次,平均每次调用236ms.你的里程当然会有所不同,我的也是如此; 我观察到,每次多次运行有时会导致记录功能更快,有时地图功能更快,但两者都没有更快的速度.我鼓励你做自己的测量,但似乎两者之间几乎没有性能差异,至少通过模式匹配访问单个字段.然而,随着字段数量的增加,性能差异变得更加明显:对于10个字段,地图慢了约0.5%,对于50个字段,地图慢了约50%.但正如我前面所说,我认为这是无关紧要的,因为如果你试图互换地使用记录和地图,那你就错了.

更新:基于评论中的对话,我澄清了在字段/键数增加时讨论性能差异的答案,并指出记录和映射不是可互换的.