Opened 3 years ago

Last modified 3 years ago

#11527 new bug

Pattern match translation suboptimal

Reported by: augustss Owned by:
Priority: normal Milestone:
Component: Compiler Version: 7.8.3
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:


Compile the following code and look at the (sad) intermediate code:

baz :: Integer -> Int -> Int
baz 10 1 = 1
baz 20 1 = 2
baz 10 2 = 2
baz 20 2 = 3
baz 10 3 = 1
baz 20 3 = 2
baz 10 4 = 2
baz 20 4 = 3
baz _ _  = 0

The pattern match compiler has not rearranged the clauses, and so it produces an 8 level deep nested test.

Now change the type signature to

baz :: Int -> Int -> Int

Now the pattern match compiler does its job and rearranges the clauses to make the tests 2 levels deep.

The same phenomenon happens when matching string literals. For the predefined String type the right thing happens, but for some other string type (using OverloadedStrings) it doesn't.

Change History (5)

comment:1 Changed 3 years ago by simonpj

For Integer I agree we could and should do better. But what about

baz :: (Num a) => a -> Int -> Int

which is what you'll get if you don't have a type signature.

The report specifies something like this:

baz n x
 | n == fromInteger 10, x == 1 = 1
 | n == fromInteger 20, x == 1 = 2
 | n == fromInteger 10, x == 2 = 2

Now you might think that we can common up all those tests for n == fromInteger 10 to get

baz n x
  | n == fromInteger 10
  = case x of
      1 -> 1
      2 -> 2
      ... etc ...

  | n == fromInteger 20
  = ...etc..

But what if both n == fromInteger 10 and n == fromInteger 20 are both true? Now it's not OK to group together all the matches against 10. How annoying!

The best we can do is to do CSE on those fromInteger calls.

It's all very irritating but I don't see how to do better. Except for Integer when we know that the Num instance has good properties. Is that particular case worth improving? Perhaps, and it would not be hard -- I can offer guidance.

comment:2 Changed 3 years ago by augustss

I agree that in general we can't rearrange the tests. Unfortunately, this means that using your own string type instead of String can be quite costly if you do pattern matching (that's actually my use case).

Since we can't assume that the compiler can deduce the necessary property, I suggest we add some way to convey the information. Some different ways:

  • Annotation on the Eq instance to say that it is sane.
  • Annotation on the case expression to say that we want more aggressive reordering.
  • A compiler flag that says we want more aggressive reordering.

An annotation on the Eq instance seems like the nicest option.

I'm quite keen to minimize the performance penalty for using a different string type.

comment:3 Changed 3 years ago by augustss

Or maybe the annotation should be on the type. Or, in the case of strings, maybe on the IsString instance. What we need to know is that if x /= y then fromString x /= fromString y.

So being able to mark fromInteger and fromString as injective would do it.

Last edited 3 years ago by augustss (previous) (diff)

comment:4 Changed 3 years ago by simonpj

Sounds great to me. Yes, injectivity of fromString and fromInteger seem like the key points.

Would you like to propose a design, describe it on a wiki page, agree it, and maybe implement it?


comment:5 Changed 3 years ago by augustss

OK, I'll start by making a wiki page.

Note: See TracTickets for help on using tickets.