[GHC] #6135: Unboxed Booleans

[GHC]

#6135: Unboxed Booleans
---------------------------------+------------------------------------------
    Reporter:  benl              |       Owner:  jstolarek       
        Type:  feature request   |      Status:  patch           
    Priority:  normal            |   Milestone:  7.8.1           
   Component:  Compiler          |     Version:  7.4.1           
    Keywords:                    |          Os:  Unknown/Multiple
Architecture:  Unknown/Multiple  |     Failure:  None/Unknown    
  Difficulty:  Unknown           |    Testcase:                  
   Blockedby:                    |    Blocking:                  
     Related:  #605              |  
---------------------------------+------------------------------------------

Comment(by gregorycollins):

 > One possible use of unboxed booleans is branchless search. There are
 some algorithms where you can replace branches (e.g. case statements) with
 bit twiddling operators. I believe Gregory Collins used one such trick in
 the hashtables package.

 Didn't see this before now. Yes, this is true, part of the reason I wrote
 the cache-line-sized hash code search is that I couldn't get efficient
 straight-line code out of GHC for doing it. One very useful bit-twiddling
 hack that the processor can do but GHC can't:

     int mask(int a, int b) { return -(a == b); }

 The C code gives me this:

 {{{
         xorl    %eax, %eax
         cmpl    %esi, %edi
         sete    %al
         negl    %eax
 }}}

 The Haskell code gives me code with branches because of the case on
 `Bool`, which I couldn't figure out how to get rid of. I did manage to get
 straight-line code for a pure Haskell function with the same semantics,
 but at a cost of about twice as many instructions. Interestingly, getting
 rid of the branch here, even in the roundabout way the Haskell version did
 it, was worth O(30%) on hash table lookup (it's in an inner loop). The C
 version I wrote for cache line-sized hash code lookups was good for
 another 20-30% besides that, and I chalked up the difference to this
 comparison issue with Bool and much better register allocation on the C
 side. (GHC was spilling even when it seemed there were many free 64-bit
 registers).

 So a solid +1 for me for implementing something like this, although maybe
 not with the names in the patch?

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