Index

核心 Erlang 优化

2018 年 5 月 18 日 · Björn Gustavsson

这篇博客文章继续探索核心 Erlang，着眼于 sys_core_fold 编译器传递所做的一些优化。核心 Erlang 语言在之前的博客文章中介绍过。

为了准备这篇博客文章中的示例，我使用了两个命令。

$ erlc +time +dcore core_fold_example.erl
Compiling "core_fold_example"
 parse_module                  :      0.000 s       9.4 kB
 transform_module              :      0.000 s       9.4 kB
 lint_module                   :      0.005 s       9.4 kB
 expand_records                :      0.000 s       9.4 kB
 core                          :      0.000 s      59.3 kB
 listing                       :      0.003 s      59.3 kB

dcore 选项生成文件 core_fold_example.core，其中包含 core 解析（由模块 v3_core 实现）生成的核心 Erlang 代码的清单。

$ erlc +time +dcopt core_fold_example.erl
Compiling "core_fold_example"
 parse_module                  :      0.000 s       9.4 kB
 transform_module              :      0.000 s       9.4 kB
 lint_module                   :      0.002 s       9.4 kB
 expand_records                :      0.000 s       9.4 kB
 core                          :      0.000 s      59.3 kB
 sys_core_fold                 :      0.000 s      25.3 kB
 core_transforms               :      0.000 s      25.3 kB
 listing                       :      0.002 s      25.3 kB

dcopt 选项生成文件 core_fold_example.copt，其中包含核心 Erlang 代码的清单，该代码在通过 sys_core_fold 传递优化后呈现。

正如我在关于编译器的第一篇博客文章中提到的，compile:options() 将打印编译器的大部分隐藏选项。

最基本的优化 #

sys_core_fold 执行的最基本优化是常量传播。

考虑这个 Erlang 函数

a() ->
    A = 42,
    {ok,A}.

它可以像这样翻译成核心 Erlang

'a'/0 =
    fun () ->
       let <A> = 42
       in {'ok',A}

变量 A 被绑定到一个常量（与函数调用等表达式相反）。我们可以用常量值 42 替换变量 A 的所有出现，并消除 let

'a'/0 =
    fun () ->
	{'ok',42}

优化 `case` 表达式 #

实际上，我展示的第一个版本的 a/0 已经被我稍微优化过了。

这是实际的核心 Erlang 代码（仅经过少量编辑以删除注释和不必要的换行符）

'a'/0 =
    fun () ->
        case <> of
	  <> when 'true' ->
	      let <A> = 42
	      in {'ok',A}
	  <> when 'true' ->
		primop 'match_fail'({'function_clause'})
	end

let 被包装在一个无用的外部 case 中。如果存在一些函数参数，则 case 将会起到一定的作用，但是如果 sys_core_fold 完全能够简化此代码，为什么还要使代码生成器复杂化呢？

sys_core_fold 将分几个步骤简化代码。

首先，它将查看每个子句。如果某个子句不可能被执行（例如，如果它的守卫是 false），则会被删除。如果某个子句将始终匹配，则该子句之后的所有子句都将被删除。

在这种情况下，第一个子句将始终匹配，因为该模式是一个不包含无法匹配的变量的列表，并且守卫为 true。因此，第二个子句无法到达并被删除

'a'/0 =
    fun () ->
        case <> of
	  <> when 'true' ->
	      let <A> = 42
	      in {'ok',A}
	end

下一步是查看是否只剩下一个子句。如果是，则可以保留该子句的主体并消除 case

'a'/0 =
    fun () ->
       let <A> = 42
       in {'ok',A}

另一个案例示例 #

让我们看看如何按照刚刚描述的步骤优化更复杂的函数。考虑这个 Erlang 函数

aa() ->
    case {a,tuple} of
	[List] -> List;
	{A,B} ->  {tuple,A,B};
	_ ->      something_else
    end.

翻译成核心 Erlang 代码（删除了外部 case 和注释）后，它看起来像这样

'aa'/0 =
    fun () ->
      case {'a','tuple'} of
	<[List|[]]> when 'true' ->
	    List
	<{A,B}> when 'true' ->
	    {'tuple',A,B}
	<_@c1> when 'true' ->
	    'something_else'
	<_@c0> when 'true' ->
	    primop 'match_fail'({'case_clause',_@c0})
      end

让我们逐个检查这些子句

第一个子句只会匹配恰好包含一个元素的列表。case 表达式是一个元组，因此第一个子句不可能匹配。它将被删除。
第二个子句将匹配包含（任意）两个元素的元组。case 表达式是一个包含两个元素的元组，因此该子句将始终匹配。
由于第二个子句将始终匹配，因此无需查看其余子句。其余子句将被删除。

现在我们有

'aa'/0 =
    fun () ->
      case {'a','tuple'} of
	<{A,B}> when 'true' ->
	    {'tuple',A,B}
      end

这是一个只有一个子句的 case，因此我们可以保留该子句的主体并删除 case。但是，如果我们天真地这样做，则会出现一个问题

'aa'/0 =
    fun () ->
       {'tuple',A,B}

使用了变量 A 和 B，但它们没有任何值绑定到它们。我们必须使用 let 在使用变量之前绑定变量

'aa'/0 =
    fun () ->
      let <A,B> = <'a','tuple'>
      in {'tuple',A,B}

传播常量，最终代码是

'aa'/0 =
    fun () ->
	{'tuple','a','tuple'}

避免元组构建 #

这是一个并行匹配多个表达式的常见模式示例

b(A, B) ->
    case {A,B} of
	{true,false} -> ok;
	{false,true} -> not_ok;
	{_,_} -> error
    end.

未优化的核心 Erlang 代码如下所示

'b'/2 =
    fun (_@c1,_@c0) ->
	case <_@c1,_@c0> of
	  <A,B> when 'true' ->
	      case {A,B} of
		<{'true','false'}> when 'true' ->
		    'ok'
		<{'false','true'}> when 'true' ->
		    'not_ok'
		<{_@c5,_@c6}> when 'true' ->
		    'error'
		<_@c2> when 'true' ->
		      primop 'match_fail'({'case_clause',_@c2})
	      end
	end

case 表达式是 {A,B}。当执行 case 时，将构建一个元组，然后几乎立即丢弃。这很浪费。因此，sys_core_fold 重写代码以消除元组构建

'b'/2 =
    fun (_@c1,_@c0) ->
	case <_@c1,_@c0> of
	  <'true','false'> when 'true' ->
	      'ok'
	  <'false','true'> when 'true' ->
	      'not_ok'
	  <_@c5,_@c6> when 'true' ->
	      'error'
	end

这里使用了一个值列表而不是元组。（有关值列表的几个示例，请参阅以前的博客文章。）

在此示例中显示了构建和立即丢弃元组的另一个常见模式

c(X) ->
    {A,B} = case X of
		a1 -> {10,1};
		b2 -> {20,2};
		_ ->  {100,42}
	    end,
    A+B.

未优化的核心 Erlang 代码如下所示

'c'/1 =
    fun (_@c0) ->
	case _@c0 of
	  <X> when 'true' ->
	      let <_@c2> =
		  case X of
		    <'a1'> when 'true' ->
			{10,1}
		    <'b2'> when 'true' ->
			{20,2}
		    <_@c5> when 'true' ->
			{100,42}
		    <_@c1> when 'true' ->
			  primop 'match_fail'({'case_clause',_@c1})
		  end
	      in
		  case _@c2 of
		    <{A,B}> when 'true' ->
			call 'erlang':'+'(A, B)
		    <_@c3> when 'true' ->
			  primop 'match_fail'({'badmatch',_@c3})
		  end
	  <_@c4> when 'true' ->
		  primop 'match_fail'({'function_clause',_@c4})
	end

这里构建了一个元组并将其分配给 _@c2。然后在 case 中进行匹配。

首先，优化代码如下，以消除第一个 case 的每个子句中的元组构建

'c'/1 =
    fun (_@c0) ->
	let <_@f4,_@f5> =
	    case _@c0 of
	      <'a1'> when 'true' ->
		  <10,1>
	      <'b2'> when 'true' ->
		  <20,2>
	      <_@c5> when 'true' ->
		  <100,42>
	    end
	in
            let <_@c2> = {_@f4,_@f5}
            in
	          case _@c2 of
		    <{A,B}> when 'true' ->
			call 'erlang':'+'(A, B)
		    <_@c3> when 'true' ->
			  primop 'match_fail'({'badmatch',_@c3})
		  end
	end

应用先前描述的所有优化，可以消除剩余的元组构建和匹配

'c'/1 =
    fun (_@c0) ->
	let <_@f4,_@f5> =
	    case _@c0 of
	      <'a1'> when 'true' ->
		  <10,1>
	      <'b2'> when 'true' ->
		  <20,2>
	      <_@c5> when 'true' ->
		  <100,42>
	    end
	in
	    call 'erlang':'+'(_@f4, _@f5)

结论 #

这是对 sys_core_fold 所做的一些优化的快速浏览。

其中一些优化非常简单。sys_core_fold 传递的强大功能来自优化的组合。正如在示例中看到的那样，一个优化为其他优化提供了机会。

值得思考的点 #

为什么优化传递称为 sys_core_fold？

可以在此 Wikipedia 文章的标题中找到提示：常量折叠。