模式匹配编译过程的简单概述
本文研究了在一些简单的常见场景中，模式匹配在底层是如何编译的。
介绍
本文研究了在一些简单的常见场景中，模式匹配在底层是如何编译的。
背景
模式匹配会被编译成一个高效的自动机。 有两种自动机风格，“决策树”和“法式风格”。每种风格都有不同的优点：决策树检查做出决定所需的最少数量的值，但是一个简单的实现可能在最坏的情况下需要指数级的代码空间。法式风格提供了不同的时间-空间权衡，对于两者都有良好但非最佳的保证。
关于这个问题的绝对权威的著作是 Luc Maranget 的优秀论文 "将模式匹配编译成良好的决策树"，来自 2008 年的 ML Workshop。 Luc 的论文基本上展示了如何兼顾两者的优点。
然而，在这里我们不会深入理论。因此，从一个工作的程序员的角度来看，我们假设编译器总是聪明的，这样有效吗？程序员的编码风格会影响编译器检测冗余分支并解析为最佳方法的能力吗？
源代码
您可以在这里查看源代码。
测试 1
F#
let test1 x =
match x with
| [| 1; 2; 3 |] -> A
| [| 1; 2; _ |] -> A
| [| 1; _; _ |] -> A
反编译的 C#
if (x != null && x.Length == 3)
{
switch (x[0])
{
case 1:
switch (x[1])
{
case 2:
switch (x[2])
{
case 3:
return Program.MyType.A;
default:
return Program.MyType.A;
}
break;
default:
return Program.MyType.A;
}
break;
}
}
throw new MatchFailureException(...);反编译的 IL
代码大小 107
结论
- 模式匹配不会根据
->后的值进行优化。 - 在结论 1 下，模式匹配能够找到数组分解的优化方法。
- 不完整的模式匹配总是会抛出异常，因此添加一个通配符来捕获缺失的模式并显式抛出异常没有坏处。
测试 1a & 1b
F#
let test1a x =
match x with
| [| 1; 2; 3 |] | [| 1; 2; _ |] | [| 1; _; _ |] -> A // redundancy
let test1b x =
match x with
| [| 4; 5; 6 |] & [| 4; 5; _ |] & [| 4; _; _ |] -> A // redundancy
反编译的 C#
public static Program.MyType test1a(int[] x)
{
if (x != null && x.Length == 3)
{
switch (x[0])
{
case 1:
switch (x[1])
{
case 2:
switch (x[2])
{
}
break;
}
return Program.MyType.A;
}
}
throw new MatchFailureException(...);
}
public static Program.MyType test1b(int[] x)
{
if (x != null && x.Length == 3)
{
switch (x[0])
{
case 4:
switch (x[1])
{
case 5:
switch (x[2])
{
case 6:
if (x != null && x.Length == 3)
{
switch (x[0])
{
case 4:
switch (x[1])
{
case 5:
if (x != null && x.Length == 3)
{
switch (x[0])
{
case 4:
return Program.MyType.A;
}
}
break;
}
break;
}
}
break;
}
break;
}
break;
}
}
throw new MatchFailureException(...);
} 结论
- 编译器无法检查 And / Or 模式中的完整性/重复性，因此无法找到最佳方法。
测试 2
F#
let test2 x =
match x with
| [| 1; 2; 3 |] -> A
| [| _; 2; 3 |] -> B
| [| _; _; 3 |] -> C 反编译的 C#
if (x != null && x.Length == 3)
{
switch (x[0])
{
case 1:
switch (x[1])
{
case 2:
switch (x[2])
{
case 3:
return Program.MyType.A;
default:
goto IL_49;
}
break;
default:
switch (x[2])
{
case 3:
break;
default:
goto IL_49;
}
break;
}
break;
default:
switch (x[1])
{
case 2:
switch (x[2])
{
case 3:
return Program.MyType.B;
default:
goto IL_49;
}
break;
default:
switch (x[2])
{
case 3:
goto IL_58;
}
goto IL_49;
}
break;
}
IL_58:
return Program.MyType.C;
}
IL_49:
throw new MatchFailureException(...); 反编译的 IL
代码大小 185
结论
- 模式匹配从数组的开头到结尾检查值。因此，它无法找到最佳方法。
- 代码大小是最佳代码大小的两倍。
测试 3
F#
let test3 x =
match x with
| [| 1; 2; 3 |] -> A
| [| 1; 2; a |] when a <> 3 -> B
| [| 1; 2; _ |] -> C 反编译的 C#
if (x != null && x.Length == 3)
{
switch (x[0])
{
case 1:
switch (x[1])
{
case 2:
switch (x[2])
{
case 3:
return Program.MyType.A;
default:
if (x[2] != 3)
{
int a = x[2];
return Program.MyType.B;
}
break;
}
break;
}
break;
}
}
if (x != null && x.Length == 3)
{
switch (x[0])
{
case 1:
switch (x[1])
{
case 2:
return Program.MyType.C;
}
break;
}
}
throw new MatchFailureException(...); 结论
- 编译器不够聪明，无法通过 Guard 检查完整性/重复性。
- Guard 使模式匹配产生奇怪的未优化代码。
测试 4
F#
let (| Is3 | IsNot3 |) x =
if x = 3 then Is3 else IsNot3
let test4 x =
match x with
| [| 1; 2; 3 |] -> A
| [| 1; 2; Is3 |] -> B
| [| 1; 2; IsNot3 |] -> C
| [| 1; 2; _ |] -> D // This rule will never be matched.反编译的 C#
if (x != null && x.Length == 3)
{
switch (x[0])
{
case 1:
switch (x[1])
{
case 2:
switch (x[2])
{
case 3:
return Program.MyType.A;
default:
{
FSharpChoice<Unit, Unit> fSharpChoice = Program.|Is3|IsNot3|(x[2]);
if (fSharpChoice is FSharpChoice<Unit, Unit>.Choice2Of2)
{
return Program.MyType.C;
}
return Program.MyType.B;
}
}
break;
}
break;
}
}
throw new MatchFailureException(...);结论
- 多个 case 的 Active Patterns 编译为
FSharpChoice。 - 编译器能够检查 Active Patterns 的完整性/重复性，但是无法将它们与普通模式进行比较。
- 无法访问的模式不会被编译。
测试 5
F#
let (| Equal3 |) x =
if x = 3 then Equal3 1 else Equal3 0 // Equivalent to "then 1 else 0"
let test5 x =
match x with
| [| 1; 2; 3 |] -> A
| [| 1; 2; Equal3 0 |] -> B
| [| 1; 2; Equal3 1 |] -> C
| [| 1; 2; _ |] -> D 反编译的 C#
if (x != null && x.Length == 3)
{
switch (x[0])
{
case 1:
switch (x[1])
{
case 2:
switch (x[2])
{
case 3:
return Program.MyType.A;
default:
{
int num = x[2];
switch ((num != 3) ? 0 : 1)
{
case 0:
return Program.MyType.B;
case 1:
return Program.MyType.C;
default:
return Program.MyType.D;
}
break;
}
}
break;
}
break;
}
}
throw new MatchFailureException(...);结论
- 单个 case 的 Active Patterns 编译为返回类型。
- 编译器有时会自动
inline函数。（惊喜！）
测试 6
F#
let (| Partial3 | _ |) x =
if x = 3 then Some (Partial3 true) else None // Equivalent to "then Some true"
let test6 x =
match x with
| [| 1; 2; 3 |] -> A
| [| 1; 2; Partial3 true |] -> B
| [| 1; 2; Partial3 true |] -> C反编译的 C#
if (x != null && x.Length == 3)
{
switch (x[0])
{
case 1:
switch (x[1])
{
case 2:
switch (x[2])
{
case 3:
return Program.MyType.A;
default:
{
FSharpOption<bool> fSharpOption = Program.|Partial3|_|(x[2]);
if (fSharpOption != null && fSharpOption.Value)
{
return Program.MyType.B;
}
break;
}
}
break;
}
break;
}
}
if (x != null && x.Length == 3)
{
switch (x[0])
{
case 1:
switch (x[1])
{
case 2:
{
FSharpOption<bool> fSharpOption = Program.|Partial3|_|(x[2]);
if (fSharpOption != null && fSharpOption.Value)
{
return Program.MyType.C;
}
break;
}
}
break;
}
}
throw new MatchFailureException(...); 结论
- Partial Active Patterns 编译为
FSharpOption。 - 编译器无法检查 Partial Active Patterns 的完整性/重复性。
测试 7
F#
type MyOne =
| AA
| BB of int
| CC
type MyAnother =
| AAA
| BBB of int
| CCC
| DDD
let test7a x =
match x with
| AA -> 2
let test7b x =
match x with
| AAA -> 2 反编译的 C#
public static int test7a(Program.MyOne x)
{
if (x is Program.MyOne._AA)
{
return 2;
}
throw new MatchFailureException(...);
}
public static int test7b(Program.MyAnother x)
{
if (x.Tag == 0)
{
return 2;
}
throw new MatchFailureException(...);
} 结论
- 如果 union 中有 3 个以上的 case，模式匹配将使用
Tag属性而不是is。（它也适用于 Multiple cases Active Patterns。） - 通常，模式匹配会导致多个
is，这可能会大大降低性能。
更改历史
- 2013 年 1 月 3 日 - 第一版
- 2013 年 1 月 4 日 - 添加了测试 1a & 1b