为什么地图的查找速度属性比 Erlang 中的记录慢？

Question

我在读 Programming Erlang，在书的第 5 章中说：

Records are just tuples in disguise, so they have the same storage and performance characteristics as tuples. Maps use more storage than tuples and have slower lookup properties.

我以前学过的语言不是这样的。 maps通常实现为一个HashTable，所以查找时间复杂度为O(1)； Records（带名字的元组）通常实现为不可变的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} 开始。代码验证参数是一个元组，然后验证元组的元数，并从中提取两个元素。在验证元组的第一个元素等于原子 foo 后，它 returns 第二个元素的值，即记录字段 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.

此代码验证参数是一个映射，然后提取与映射键关联的值 f。

每个功能的成本归结为汇编指令的成本。 record 函数有更多指令，但它们可能比 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

这意味着调用该函数一千万次平均耗时 238 毫秒。现在，地图功能：

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

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

更新：根据评论中的对话，我澄清了随着 fields/keys 数量的增加讨论性能差异的答案，并指出记录和地图并不意味着可以互换。

更新：对于 Erlang/OTP 24 的 Erlang Efficiency Guide was augmented with a chapter on maps 值得一读以获得此问题的详细答案。

Answer 2

用 Erlang/OTP 22 [erts-10.6] 重复测试时我得到了不同的结果。

r/1的反汇编代码不同：

记录查找速度提高 1.5 倍以上。

{function, r, 1, 2}.
  {label,1}.
    {line,[{location,"f2.erl",9}]}.
    {func_info,{atom,f2},{atom,r},1}.
  {label,2}.
    {test,is_tagged_tuple,{f,1},[{x,0},2,{atom,foo}]}.
    {get_tuple_element,{x,0},1,{x,0}}.
    return.

{function, m, 1, 4}.
  {label,3}.
    {line,[{location,"f2.erl",12}]}.
    {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,1}]}}.
    {move,{x,1},{x,0}}.
    return.


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

After I declared -compile({inline, [r/1, m/1]}).

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

Answer 3

我将具有 10 个元素的记录与相同大小的地图进行了比较。在这种情况下，记录被证明快了 2 倍多。

-module(f22).

-compile({inline, [r/1, m/1]}).

-export([call_r/1, call_r/2, call_m/1, call_m/2]).

-define(I, '2').
-define(V,  2 ).

-record(foo, {
    '1',
    '2',
    '3',
    '4',
    '5',
    '6',
    '7',
    '8',
    '9',
    '0'
    }).

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

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

call_r(N) ->
    call_r(#foo{
    '1' = 1,
    '2' = 2,
    '3' = 3,
    '4' = 4,
    '5' = 5,
    '6' = 6,
    '7' = 7,
    '8' = 8,
    '9' = 9,
    '0' = 0
    }, N).
call_r(_,0) ->
    ok;
call_r(F,N) ->
    ?V = r(F),
    call_r(F,N-1).

call_m(N) ->
    call_m(#{
    '1' => 1,
    '2' => 2,
    '3' => 3,
    '4' => 4,
    '5' => 5,
    '6' => 6,
    '7' => 7,
    '8' => 8,
    '9' => 9,
    '0' => 0
    }, N).
call_m(_,0) ->
    ok;
call_m(F,N) ->
    ?V = m(F),
    call_m(F,N-1).


% lists:sum([element(1,timer:tc(f22,call_r,[10000000])) || _ <- lists:seq(1,50)])/50.
% 229777.3
% lists:sum([element(1,timer:tc(f22,call_m,[10000000])) || _ <- lists:seq(1,50)])/50.
% 395897.68

% After declaring 
% -compile({inline, [r/1, m/1]}).
% lists:sum([element(1,timer:tc(f22,call_r,[10000000])) || _ <- lists:seq(1,50)])/50.
% 130859.98
% lists:sum([element(1,timer:tc(f22,call_m,[10000000])) || _ <- lists:seq(1,50)])/50.
% 306490.6
% 306490.6 / 130859.98 .
% 2.34212629407401

为什么地图的查找速度属性比 Erlang 中的记录慢？

Why do Maps have slower lookup property than Records in Erlang?

erlang

为什么地图的查找速度 属性 比 Erlang 中的记录慢？

Why do Maps have slower lookup property than Records in Erlang?

erlang

为什么地图的查找速度属性比 Erlang 中的记录慢？