Click here to Skip to main content
Click here to Skip to main content
 
Go to top

A Simple Overview on How Pattern Match Compiles

, 3 Jan 2013
Rate this:
Please Sign up or sign in to vote.
This article investigates how Pattern Match compiles under the hood in a number of simple common scenarios.
This is an old version of the currently published article.

Introduction  

This article investigates how Pattern Match compiles under the hood in a number of simple common scenarios.  

Background  

It is well known that a good compiler would generate optimized code for Pattern Match.  However is it valid that we assume the compiler is always smart? Would the programmers' coding styles affect the compiler's ability to detect redundant branches and resolves to an optimal approach at all?  

Source Code 

You can view the source code here

Test 1  

F# 

let test1 x =
    match x with
    | [| 1; 2; 3 |] -> A
    | [| 1; 2; _ |] -> A
    | [| 1; _; _ |] -> A
    | _ -> A 

Decompiled 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(...);

Decompiled IL 

Code size 107 

Conclusion

  1. Pattern Match doesn't optimize based on the values after ->.
  2. Pattern Match is able to find the optimized approach for array decomposition under conclusion 1.
  3. Incomplete pattern matches always throw exceptions, so there is no harm to add a wildcard to catch the missing patterns and throw exceptions explicitly. 

Test 2  

F# 

let test2 x =
    match x with
    | [| 1; 2; 3 |] -> A
    | [| _; 2; 3 |] -> B
    | [| _; _; 3 |] -> C 

Decompiled 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(...);  

Decompiled IL 

Code size 185 

Conclusion

  1. Pattern Match checks values from the beginning of an array to end. So it fails to find the optimized approach.
  2. Code size is 2x as much as an optimal one.

Test 3

F# 

let test3 x =
    match x with
    | [| 1; 2; 3 |] -> A
    | [| 1; 2; a |] when a <> 3 -> B
    | [| 1; 2; _ |] -> C 

Decompiled 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(...);   

Conclusion

  1. The compiler isn't smart enough to see through Guard to check completeness/duplicity.
  2. Guard makes Pattern Match produce weird unoptimized code.

Test 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.

Decompiled 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(...);

Conclusion

  1. Multiple cases Active Patterns compile to FSharpChoice.
  2. The compiler is able to check completeness/duplicity of active patterns, however it cannot compare them with normal patterns.
  3. Unreached patterns are not compiled. 

Test 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 

Decompiled 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(...);

Conclusion

  1. Single case Active Patterns compile to the return type. 
  2. The compiler sometimes auto inline the function. 

Test 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

Decompiled 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(...);

Conclusion

  1. Partial Active Patterns compile to FSharpOption.
  2. The compiler is unable to check completeness/duplicity of partial active patterns. 

Test 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 

Decompiled 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(...);
} 

Conclusion

  1. If there are more than 3 cases in the union, Pattern Match would use Tag property instead of is. (It also applies to Multiple cases Active Patterns.)
  2. Often a Pattern Match would result in multiple is which degenerate performance greatly. 

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

colinfang

United Kingdom United Kingdom
No Biography provided

Comments and Discussions


Discussions posted for the Published version of this article. Posting a message here will take you to the publicly available article in order to continue your conversation in public.
 
QuestionCompilation Settings PinmemberMuigai Mwaura4-Jan-13 9:01 
AnswerRe: Compilation Settings Pinmembercolinfang4-Jan-13 10:29 
GeneralRe: Compilation Settings PinmemberMuigai Mwaura5-Jan-13 2:57 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web02 | 2.8.140916.1 | Last Updated 3 Jan 2013
Article Copyright 2013 by colinfang
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid