[GHC] #14644: Improve cmm/assembly for pattern matches with two constants.

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
17 messages Options
Reply | Threaded
Open this post in threaded view
|

[GHC] #14644: Improve cmm/assembly for pattern matches with two constants.

GHC - devs mailing list
#14644: Improve cmm/assembly for pattern matches with two constants.
-------------------------------------+-------------------------------------
           Reporter:  AndreasK       |             Owner:  (none)
               Type:  task           |            Status:  new
           Priority:  normal         |         Milestone:
          Component:  Compiler       |           Version:  8.2.2
  (CodeGen)                          |
           Keywords:  Codegen, CMM,  |  Operating System:  Unknown/Multiple
  Patterns, Pattern Matching         |
       Architecture:                 |   Type of failure:  None/Unknown
  Unknown/Multiple                   |
          Test Case:                 |        Blocked By:
           Blocking:                 |   Related Tickets:
Differential Rev(s):                 |         Wiki Page:
-------------------------------------+-------------------------------------
 For a pattern like:
 {{{
 f_test :: Int#->Int#
 f_test a = case a of
     1# -> 33#
     7# -> 34#
      _ -> -1#
 }}}

 GHC currently generates code that works best if the default branch is
 taken most often.

 Pseudo-Code
 {{{
 if (a >= 8)
     return -1;
 else {
     if (a < 7) {
         if(a != 1)
             return -1;
         else
             return 33;
     }
     else
         return 34;
 }
 }}}

 CMM:
 {{{
        c1cr: // global
            if (%MO_S_Ge_W64(R2, 8)) goto c1co; else goto u1cu;
        u1cu: // global
            if (%MO_S_Lt_W64(R2, 7)) goto u1cv; else goto c1cq;
        u1cv: // global
            if (R2 != 1) goto c1co; else goto c1cp;
        c1co: // global
            R1 = (-1);
            call (P64[Sp])(R1) args: 8, res: 0, upd: 8;
        c1cp: // global
            R1 = 33;
            call (P64[Sp])(R1) args: 8, res: 0, upd: 8;
        c1cq: // global
            R1 = 34;
            call (P64[Sp])(R1) args: 8, res: 0, upd: 8;
      }

 }}}

 Wouldn't the following be better?
 {{{
 if(a == 1)
     return 33
 else if(a == 7)
     return 34
 else
     return -1
 }}}

 I would expect that to
 * Improve the cases:
   * a = 1
   * a < 7
 * Be the same for:
   * a = 7
 * Be worse for
   * a > 8

 This would be especially nice for the cases where the default branch is
 raising a pattern match exception.
 Which is a code path I wouldn't expect to be taken often nor be very
 performance sensitive.

 Even if we keep the current logic there is room for improvement.
 GHC currently creates the following assembly:

 {{{
 _c1cr:
         cmpq $8,%r14
         jge _c1co
 _u1cu:
         cmpq $7,%r14
         jl _u1cv
 _c1cq:
         movl $34,%ebx
         jmp *(%rbp)
 _u1cv:
         cmpq $1,%r14
         jne _c1co
 _c1cp:
         movl $33,%ebx
         jmp *(%rbp)
 _c1co:
         movq $-1,%rbx
         jmp *(%rbp)
 }}}

 It would be nice if we could remove one comparison at least.
 {{{
 _c1cr:
         cmpq $7,%r14
         jg _c1co
 _u1cu:
         ;No longer neccesary cmpq $7,%r14
         jl _u1cv
 _c1cq:
         movl $34,%ebx
         jmp *(%rbp)
 _u1cv:
         cmpq $1,%r14
         jne _c1co
 _c1cp:
         movl $33,%ebx
         jmp *(%rbp)
 _c1co:
         movq $-1,%rbx
         jmp *(%rbp)
 }}}

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14644>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

Re: [GHC] #14644: Improve cmm/assembly for pattern matches with two constants.

GHC - devs mailing list
#14644: Improve cmm/assembly for pattern matches with two constants.
-------------------------------------+-------------------------------------
        Reporter:  AndreasK          |                Owner:  (none)
            Type:  task              |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.2.2
  (CodeGen)                          |             Keywords:  Codegen, CMM,
      Resolution:                    |  Patterns, Pattern Matching
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by simonpj):

 Looks plausible to me.  I wonder how we'd measure any potential benefit?

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14644#comment:1>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

Re: [GHC] #14644: Improve cmm/assembly for pattern matches with two constants.

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#14644: Improve cmm/assembly for pattern matches with two constants.
-------------------------------------+-------------------------------------
        Reporter:  AndreasK          |                Owner:  (none)
            Type:  task              |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.2.2
  (CodeGen)                          |             Keywords:  Codegen, CMM,
      Resolution:                    |  Patterns, Pattern Matching
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by AndreasK):

 It should also be possible to see the difference using criterion or
 instruction counters when running affected code in a tight loop.

 I will take a stab at changing the logic to `if ... else if ... else` for
 these cases. I think that's a good starting point to learn how Cmm works
 inside GHC.

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14644#comment:2>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

Re: [GHC] #14644: Improve cmm/assembly for pattern matches with two constants.

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#14644: Improve cmm/assembly for pattern matches with two constants.
-------------------------------------+-------------------------------------
        Reporter:  AndreasK          |                Owner:  (none)
            Type:  task              |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.2.2
  (CodeGen)                          |             Keywords:  Codegen, CMM,
      Resolution:                    |  Patterns, Pattern Matching
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by svenpanne):

 I am not sure if things are that easy: To do these kind of switches in a
 really good way, one would need a probability distribution how often the
 individual cases actually happen.

 If we e.g. assume that all Ints happen equally often in the example above,
 it would be best to check for <1 and >7 first, so we would get roughly 1.5
 comparisons on average. Depending on the number of registers available,
 you can even get away with 1 subtraction and 1 unsigned comparison for
 this range check, a classic C hack (ab)using wrap-around for unsigned
 ints.

 If we have some hints, e.g. raising a pattern matching exception, we could
 do better, e.g. assume 0% probability for this case. If we have more
 detailed (estimated) probabilities, we could do a Huffman-like decision
 tree. This is where profile-guided optimization shines.

 Additional things to consider: Performance in tight loops is often vastly
 different, because branch prediction/caching will most likely kick in
 visibly. Correctly predicted branches will cost you almost nothing, while
 unknown/incorrectly predicted branches will be much more costly. In the
 absence of more information from their branch predictor, quite a few
 processors assume that backward branches are taken and forward branches
 are assumed to be not taken. So code layout has a non-trivial performance
 impact.

 Instruction counts are quite misleading nowadays...

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14644#comment:3>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

Re: [GHC] #14644: Improve cmm/assembly for pattern matches with two constants.

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#14644: Improve cmm/assembly for pattern matches with two constants.
-------------------------------------+-------------------------------------
        Reporter:  AndreasK          |                Owner:  (none)
            Type:  task              |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.2.2
  (CodeGen)                          |             Keywords:  Codegen, CMM,
      Resolution:                    |  Patterns, Pattern Matching
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by AndreasK):

 Replying to [comment:3 svenpanne]:
 > I am not sure if things are that easy: To do these kind of switches in a
 really good way, one would need a probability distribution how often the
 individual cases actually happen.

 This is by no means meant as a "this is optimal" idea.

 As far as I'm aware there is currently no way to propagate probabilities
 through GHC's various stages. So even in cases where we can make a
 judgement on the probability we can't really use it at the Cmm level.

 In the end I suggested it because it:
 * I think it has a good chance of being faster
 * Leads to smaller code
 * Seems to be what gcc/clang do (using conditional moves instead of jumps
 but still).

 > Additional things to consider: Performance in tight loops is often
 vastly different, because branch prediction/caching will most likely kick
 in visibly. Correctly predicted branches will cost you almost nothing,
 while unknown/incorrectly predicted branches will be much more costly. In
 the absence of more information from their branch predictor, quite a few
 processors assume that backward branches are taken and forward branches
 are assumed to be not taken. So code layout has a non-trivial performance
 impact.
 >
 > Instruction counts are quite misleading nowadays...

 Indeed :(

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14644#comment:4>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

Re: [GHC] #14644: Improve cmm/assembly for pattern matches with two constants.

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#14644: Improve cmm/assembly for pattern matches with two constants.
-------------------------------------+-------------------------------------
        Reporter:  AndreasK          |                Owner:  AndreasK
            Type:  task              |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.2.2
  (CodeGen)                          |             Keywords:  Codegen, CMM,
      Resolution:                    |  Patterns, Pattern Matching
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):  Phab:D4294
       Wiki Page:                    |
-------------------------------------+-------------------------------------
Changes (by AndreasK):

 * owner:  (none) => AndreasK
 * differential:   => Phab:D4294


Comment:

 I ran a simple Benchmark and the results seem almost too good with >10%
 gains in almost all cases.

 If it really is that good then, well, I guess good for us.

 Assuming I didn't introduce an error somewhere I assume the combination of
 smaller code and less instructions on some paths is just better in
 general.


 > If we e.g. assume that all Ints happen equally often in the example
 above, it would be best to check for <1 and >7 first, so we would get
 roughly 1.5 comparisons on average. Depending on the number of registers
 available, you can even get away with 1 subtraction and 1 unsigned
 comparison for this range check, a classic C hack (ab)using wrap-around
 for unsigned ints.

 I thought about this a bit. While true it also means the first comparison
 has a hard time with prediction if the numbers are a random distribution
 over the range. So two 99.9% correctly predicted comparisons might still
 be better even without considering code size.

 `range check, jg, je, cmp, je, j <default>` could still be better. But not
 sure if I will look into that and it might warrant it's own ticket as GHC
 also uses this for range checks on jump tables I think.

 Code used for the test:
 {{{
 f_test :: Int -> Int
 f_test  111 = 1111
 f_test  222 = 2222
 f_test  _ = -1

 run = print . sum . map f_test

 --main = print . sum . map f_test $ ([(-1500000000::Int) .. 0])
 main = do
     args <- getArgs :: IO [String]
     if null args
         then putStrLn "Usage: pos|neg|both"
         else case (head args) of
             "pos" -> run [0 .. (1500000000::Int)]
             "neg" -> run [-1500000000::Int .. 0]
             "both" -> run [-750000000::Int .. 750000000::Int]
             "negrep" -> run . concat . replicate 100000000 $ [-311, -322,
 -333, -444]
             "posrep" -> run . concat . replicate 100000000 $ [311, 322,
 333, 444]
             "unpre" -> run . concat . replicate 100000000 $ [111, 322,
 -333, 222]
 }}}

 I get these results for the current approach (range) and mine (if) on an
 6700K

 === With inlining:
 {{{
 benchmarking execute: range pos
 mean                 1.196 s    (1.196 s .. 1.198 s)
 benchmarking execute: if pos
 mean                 806.0 ms   (803.5 ms .. 807.3 ms)

 benchmarking execute: range neg
 mean                 2.384 s    (2.383 s .. 2.385 s)
 benchmarking execute: if neg
 mean                 1.841 s    (1.841 s .. 1.842 s)

 benchmarking execute: range negrep
 mean                 840.1 ms   (838.1 ms .. 841.3 ms)
 benchmarking execute: if negrep
 mean                 728.6 ms   (728.3 ms .. 728.8 ms)

 benchmarking execute: range unpre
 mean                 852.2 ms   (851.1 ms .. 853.1 ms)
 benchmarking execute: if unpre
 mean                 789.7 ms   (789.3 ms .. 789.9 ms)
 }}}

 === With inlining disabled on f_test
 {{{
 benchmarking execute: range pos
 mean                 2.385 s    (2.383 s .. 2.386 s)
 benchmarking execute: if pos
 mean                 2.383 s    (2.382 s .. 2.384 s)

 benchmarking execute: range neg
 mean                 2.845 s    (2.839 s .. 2.848 s)
 benchmarking execute: if neg
 mean                 2.047 s    (2.041 s .. 2.053 s)

 benchmarking execute: range negrep
 mean                 1.204 s    (1.201 s .. 1.205 s)
 benchmarking execute: if negrep
 mean                 829.4 ms   (828.4 ms .. 830.1 ms)

 benchmarking execute: range unpre
 mean                 1.165 s    (1.164 s .. 1.166 s)
 benchmarking execute: if unpre
 mean                 1.118 s    (1.117 s .. 1.119 s)
 }}}

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14644#comment:5>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

Re: [GHC] #14644: Improve cmm/assembly for pattern matches with two constants.

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#14644: Improve cmm/assembly for pattern matches with two constants.
-------------------------------------+-------------------------------------
        Reporter:  AndreasK          |                Owner:  AndreasK
            Type:  task              |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.2.2
  (CodeGen)                          |             Keywords:  Codegen, CMM,
      Resolution:                    |  Patterns, Pattern Matching
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):  Phab:D4294
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by simonpj):

 A 10% improvement is amazing.

 If you commit this, please include a Note explaining the strategy, and
 pointing to the ticket.

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14644#comment:6>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

Re: [GHC] #14644: Improve cmm/assembly for pattern matches with two constants.

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#14644: Improve cmm/assembly for pattern matches with two constants.
-------------------------------------+-------------------------------------
        Reporter:  AndreasK          |                Owner:  AndreasK
            Type:  task              |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.2.2
  (CodeGen)                          |             Keywords:  Codegen, CMM,
      Resolution:                    |  Patterns, Pattern Matching
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):  Phab:D4294
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by AndreasK):

 Replying to [comment:6 simonpj]:
 > A 10% improvement is amazing.

 Indeed! Nothing in nofib gets up to 10% but wheel-sieve1 comes close.

 * 17 programs are changed (contain that kind of case statement)
 * 15 Show no significant runtime difference. (It's fair to assume it's an
 improvement but not mensurable with the noise on my machine)
 * k-nucleotide improves by ~1.2%
 * wheel-sieve1 has the code in a inner loop. It improves by ~4.3% in
 mode=normal. Increasing the problem size makes the difference even bigger
 up to somewhere around 8-9%

 >
 > If you commit this, please include a Note explaining the strategy, and
 pointing to the ticket.

 Will do.

 ****

 The patch is up on phab. If someone can run this on an older intel (or
 even better amd) processor and check the result that would be great to
 make sure it's not just a pecularity of my i7-6700K.

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14644#comment:7>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

Re: [GHC] #14644: Improve cmm/assembly for pattern matches with two constants.

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#14644: Improve cmm/assembly for pattern matches with two constants.
-------------------------------------+-------------------------------------
        Reporter:  AndreasK          |                Owner:  AndreasK
            Type:  task              |               Status:  patch
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.2.2
  (CodeGen)                          |             Keywords:  Codegen, CMM,
      Resolution:                    |  Patterns, Pattern Matching
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):  Phab:D4294
       Wiki Page:                    |
-------------------------------------+-------------------------------------
Changes (by AndreasK):

 * status:  new => patch


--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14644#comment:8>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

Re: [GHC] #14644: Improve cmm/assembly for pattern matches with two constants.

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#14644: Improve cmm/assembly for pattern matches with two constants.
-------------------------------------+-------------------------------------
        Reporter:  AndreasK          |                Owner:  AndreasK
            Type:  task              |               Status:  patch
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.2.2
  (CodeGen)                          |             Keywords:  Codegen, CMM,
      Resolution:                    |  Patterns, Pattern Matching
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):  Phab:D4294
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by simonpj):

 Didn't you say "I ran a simple Benchmark and the results seem almost too
 good with >10% gains in almost all cases.".  But now you say "mostly no
 change; one gets 5-9%".   Were the earlier measurements wrong?

 Anyway the patch looks good.  Thanks

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14644#comment:9>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

Re: [GHC] #14644: Improve cmm/assembly for pattern matches with two constants.

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#14644: Improve cmm/assembly for pattern matches with two constants.
-------------------------------------+-------------------------------------
        Reporter:  AndreasK          |                Owner:  AndreasK
            Type:  task              |               Status:  patch
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.2.2
  (CodeGen)                          |             Keywords:  Codegen, CMM,
      Resolution:                    |  Patterns, Pattern Matching
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):  Phab:D4294
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by AndreasK):

 Replying to [comment:9 simonpj]:
 > Didn't you say "I ran a simple Benchmark and the results seem almost too
 good with >10% gains in almost all cases.".  But now you say "mostly no
 change; one gets 5-9%".   Were the earlier measurements wrong?

 No these are right. But the simple benchmark was running the code I posted
 above in
 [https://ghc.haskell.org/trac/ghc/ticket/14644?replyto=9#comment:5 comment
 5]. All cases referred to the  pos/neg/.. branches in that case.

 Nofib seems to be in a permanent state of breakdown on windows so I
 stopped using it in my initial benchmarks.
 And it was the [https://ghc.haskell.org/trac/ghc/ticket/14656 right]
 [https://ghc.haskell.org/trac/ghc/ticket/14655 thing]
 [https://ghc.haskell.org/trac/ghc/ticket/14654 to do ] as it took some
 work to get it running.

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14644#comment:10>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

Re: [GHC] #14644: Improve cmm/assembly for pattern matches with two constants.

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#14644: Improve cmm/assembly for pattern matches with two constants.
-------------------------------------+-------------------------------------
        Reporter:  AndreasK          |                Owner:  AndreasK
            Type:  task              |               Status:  patch
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.2.2
  (CodeGen)                          |             Keywords:  Codegen, CMM,
      Resolution:                    |  Patterns, Pattern Matching
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):  Phab:D4294
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by AndreasK):

 Replying to [comment:3 svenpanne]:

 > Additional things to consider: Performance in tight loops is often
 vastly different, because branch prediction/caching will most likely kick
 in visibly. Correctly predicted branches will cost you almost nothing,
 while unknown/incorrectly predicted branches will be much more costly. In
 the absence of more information from their branch predictor, quite a few
 processors assume that backward branches are taken and forward branches
 are assumed to be not taken. So code layout has a non-trivial performance
 impact.

 I went over Agners guide and it seems like this is only for Netburst
 CPU's, the last of which was released in 2001 so I'm not too worried about
 these. And even if you have on of these according to Agner:

 > It is rarely worth the effort to take static prediction into account.
 Almost any branch that is executed sufficiently often for its timing to
 have any significant effect is likely to stay in the BTB so that only the
 dynamic prediction counts.

 All other architectures he lists default to not taken if they use static
 prediction at all.


 ----

 What might help explain the difference is that jumps not taken should be
 faster than taken jumps on both modern Intel and AMD CPU's.

 If someone wants to dig deeper Agner probably has enough info in the
 guides to explain the change completely based on the assembly generated.
 But I don't think that is necessary.

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14644#comment:11>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

Re: [GHC] #14644: Improve cmm/assembly for pattern matches with two constants.

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#14644: Improve cmm/assembly for pattern matches with two constants.
-------------------------------------+-------------------------------------
        Reporter:  AndreasK          |                Owner:  AndreasK
            Type:  task              |               Status:  patch
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.2.2
  (CodeGen)                          |             Keywords:  Codegen, CMM,
      Resolution:                    |  Patterns, Pattern Matching
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):  Phab:D4294
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by simonpj):

 It would be great to ensure that there is a Note to explain the thinking
 before you tie the bow on this.  Thanks!

 Simon

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14644#comment:12>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

Re: [GHC] #14644: Improve cmm/assembly for pattern matches with two constants.

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#14644: Improve cmm/assembly for pattern matches with two constants.
-------------------------------------+-------------------------------------
        Reporter:  AndreasK          |                Owner:  AndreasK
            Type:  task              |               Status:  patch
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.2.2
  (CodeGen)                          |             Keywords:  Codegen, CMM,
      Resolution:                    |  Patterns, Pattern Matching
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):  Phab:D4294
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by simonpj):

 Are we good to go on this?  I.e. commit?

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14644#comment:13>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

Re: [GHC] #14644: Improve cmm/assembly for pattern matches with two constants.

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#14644: Improve cmm/assembly for pattern matches with two constants.
-------------------------------------+-------------------------------------
        Reporter:  AndreasK          |                Owner:  AndreasK
            Type:  task              |               Status:  patch
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.2.2
  (CodeGen)                          |             Keywords:  Codegen, CMM,
      Resolution:                    |  Patterns, Pattern Matching
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):  Phab:D4294
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by AndreasK):

 Replying to [comment:13 simonpj]:
 > Are we good to go on this?  I.e. commit?

 From my side the patch is good to go as it is.

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14644#comment:14>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

Re: [GHC] #14644: Improve cmm/assembly for pattern matches with two constants.

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#14644: Improve cmm/assembly for pattern matches with two constants.
-------------------------------------+-------------------------------------
        Reporter:  AndreasK          |                Owner:  AndreasK
            Type:  task              |               Status:  patch
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.2.2
  (CodeGen)                          |             Keywords:  Codegen, CMM,
      Resolution:                    |  Patterns, Pattern Matching
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):  Phab:D4294
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by Ben Gamari <ben@…>):

 In [changeset:"7ff6023537fdef32bbe9b4c357012d705d9b931f/ghc" 7ff6023/ghc]:
 {{{
 #!CommitTicketReference repository="ghc"
 revision="7ff6023537fdef32bbe9b4c357012d705d9b931f"
 cmm: Use two equality checks for two alt switch with default

 For code like:
 f 1 = e1
 f 7 = e2
 f _ = e3

 We can treat it as a sparse jump table, check if we are outside of the
 range in one direction first and then start checking the values.

 GHC currently does this by checking for x>7, then x <= 7 and at last x
 == 1.

 This patch changes this such that we only compare for equality against
 the two values and jump to the default if non are equal.

 The resulting code is both faster and smaller.
 wheel-sieve1 improves by 4-8% depending on problem size.

 This implements the idea from #14644

 Reviewers: bgamari, simonmar, simonpj, nomeata

 Reviewed By: simonpj, nomeata

 Subscribers: nomeata, simonpj, rwbarton, thomie, carter

 Differential Revision: https://phabricator.haskell.org/D4294
 }}}

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14644#comment:15>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

Re: [GHC] #14644: Improve cmm/assembly for pattern matches with two constants.

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#14644: Improve cmm/assembly for pattern matches with two constants.
-------------------------------------+-------------------------------------
        Reporter:  AndreasK          |                Owner:  AndreasK
            Type:  task              |               Status:  closed
        Priority:  normal            |            Milestone:  8.6.1
       Component:  Compiler          |              Version:  8.2.2
  (CodeGen)                          |             Keywords:  Codegen, CMM,
      Resolution:  fixed             |  Patterns, Pattern Matching
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):  Phab:D4294
       Wiki Page:                    |
-------------------------------------+-------------------------------------
Changes (by bgamari):

 * status:  patch => closed
 * resolution:   => fixed
 * milestone:   => 8.6.1


--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14644#comment:16>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets