Re: [GHC] #9661: Branchless ==# is compiled to branchy code

15 Oct 2014

      ...
Well, when a table-driven jump doesn't work GHC generates a binary tree,
 reverting a table-driven jump whenever it finds a sufficiently dense
#9661: Branchless ==# is compiled to branchy code
-------------------------------------+-------------------------------------
              Reporter:  dfeuer      |            Owner:
                  Type:  feature     |           Status:  new
  request                            |        Milestone:
              Priority:  normal      |          Version:  7.9
             Component:  Compiler    |         Keywords:
            Resolution:              |     Architecture:  Unknown/Multiple
      Operating System:              |       Difficulty:  Unknown
  Unknown/Multiple                   |       Blocked By:
       Type of failure:  Runtime     |  Related Tickets:
  performance bug                    |
             Test Case:              |
              Blocking:              |
Differential Revisions:              |
-------------------------------------+-------------------------------------

Comment (by dfeuer):

 Replying to [comment:14 simonpj]:
 patch.  (I'm not sure this is fully done, but that's the intention.)  Even
 if there are no dense patches, log(N) is better than N.

 For sufficiently small N, it is likely better to do a linear search to
 avoid branch mispredictions (possibly even a branchless search using
 conditional moves or bit hacks). But it almost certainly depends to a
 certain extent on details of what is and what is not likely, which may be
 better known to the programmer than to the compiler. For example: suppose
 I we have

 {{{#!hs
 weird x = case x of
   1732 -> 12
   37893 -> 4
   98231 -> 5
   47835 -> 3
   98002 -> 17
   324 -> 56
   _ -> x * 74
 }}}

 If we're applying this to a uniform random distribution of numbers from
 `1` to `100000`, binary search will give us a tremendously high rate of
 mispredicted branches, if I understand things correctly (never a certain
 thing). Looping through all the possibilities will work better. Of course,
 the compiler does not know anything about the distribution! I'm not saying
 I know "the right answer" (certainly I don't); I just think this could use
 a bit more thinking, and I like the idea of giving the programmer more
 tools to express intention in this realm.

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