

# Implementing new primitive comparisons to allow branchless algorithms









This page gathers the notes about implementing new primitive logical operations and thus resolving ticket [\#6135](https://gitlab.haskell.org//ghc/ghc/issues/6135).



This page gathers the notes about implementing new primitive logical operations and thus resolving ticket [\#6135](https://gitlab.haskell.org//ghc/ghc/issues/6135). See [ this page](http://ghc.haskell.org/trac/ghc/wiki/NewPrimopsInGHC7.8) for a instructions how to adjust your already existing code to work with new primops.






## The problem




...  ...  @@ 92,7 +92,7 @@ Note: this example was produced with GHC 7.6.3. At the moment of merging new pri 


## Solution









This problem was solved by modifying comparison primops to return unboxed unlifted `Int#` instead of `Bool`. Having `Int#` returned as a result of logical comparison will allow to use branchless bitwise logical operators instead of branching logical operators defined for `Bool` values.



This problem was solved by modifying comparison primops to return unboxed unlifted `Int#` instead of `Bool` (which is lifted and thus is returned as a thunk that needs to be evaluated). Having `Int#` returned as a result of logical comparison will allow to use branchless bitwise logical operators instead of branching logical operators defined by Haskell.






## Implementation details




...  ...  @@ 103,44 +103,41 @@ Below is a summary of implementation details and decisions: 


 as a small sidetask, four new logical bitwise primops have been implemented: `andI#`, `orI#`, `xorI#` and `negI#` ([\#7689](https://gitlab.haskell.org//ghc/ghc/issues/7689)). These operate on values of type `Int#`. Earlier we had only bitwise logical primops operating on values of type `Word#`.



 names of the existing comparison primops were changed. Operators had `$` added before `#`, others had `I` added before the `#` (this is a mnemonic denoting that this primop returns and `Int#`). Examples:






```wiki



>=$# :: Int# > Int# > Int#



/=$## :: Double# > Double# > Int#



gtCharI# :: Char# > Char# > Int#



eqWordI# :: Word# > Word# > Int#



ltFloatI# :: Float# > Float# > Int#



leAddrI# :: Addr# > Addr# > Int#



sameMutableArrayI# :: MutableArray# s a > MutableArray# s a > Int#



```



```wiki



>=$# :: Int# > Int# > Int#



/=$## :: Double# > Double# > Int#



gtCharI# :: Char# > Char# > Int#



eqWordI# :: Word# > Word# > Int#



ltFloatI# :: Float# > Float# > Int#



leAddrI# :: Addr# > Addr# > Int#



```






 built in `GHC.Prim` modules was renamed to `GHC.Prim.BuiltIn`. In `ghcprim` we added a module `GHC.Prim` which reexports all definitions from `GHC.Prim.BuiltIn` but also adds wrappers for new comparison primops. These wrappers have names identical to removed primops and return a `Bool`. Examples:



 a new module `GHC.PrimWrappers` was added to ghcprim library. This module contains wrappers for comparison primops. These wrappers have names identical to removed primops and return a `Bool`. Examples:






```wiki



gtChar# :: Char# > Char# > Bool



gtChar# a b = tagToEnum# (a `gtCharI#` b)



```wiki



gtChar# :: Char# > Char# > Bool



gtChar# a b = tagToEnum# (a `gtCharI#` b)






(>=#) :: Int# > Int# > Bool



(>=#) a b = tagToEnum# (a >=$# b)



(>=#) :: Int# > Int# > Bool



(>=#) a b = tagToEnum# (a >=$# b)






eqWord# :: Word# > Word# > Bool



eqWord# a b = tagToEnum# (a `eqWordI#` b)



eqWord# :: Word# > Word# > Bool



eqWord# a b = tagToEnum# (a `eqWordI#` b)






(/=##) :: Double# > Double# > Bool



(/=##) a b = tagToEnum# (a /=$## b)



(/=##) :: Double# > Double# > Bool



(/=##) a b = tagToEnum# (a /=$## b)






ltFloat# :: Float# > Float# > Bool



ltFloat# a b = tagToEnum# (a `ltFloatI#` b)



ltFloat# :: Float# > Float# > Bool



ltFloat# a b = tagToEnum# (a `ltFloatI#` b)






leAddr# :: Addr# > Addr# > Bool



leAddr# a b = tagToEnum# (a `leAddrI#` b)



leAddr# :: Addr# > Addr# > Bool



leAddr# a b = tagToEnum# (a `leAddrI#` b)



```






sameMutableArray# :: MutableArray# s a > MutableArray# s a > Int#



sameMutableArray# a b = tagToEnum# (a `sameMutableArrayI#` b)



```






Thanks to renaming of previously existing `GHC.Prim` module and adding wrappers in new `GHC.Prim` module **the whole change of primops is backwards compatible**.



Thanks to these wrappers the change is almost backwards compatible. **The only thing primop users need to change in their existing code to make it work again is adding import of GHC.PrimWrappers module.**






 functions for comparing `Integer` type, implemented in `integergmp` and `integersimple` libraries, received a similar treatment. Technically they are not primops, because they are implemented in Haskell (in case of `integergmp` also with FFI), but they pretend to be ones. There are six primops for comparing `Integer` values:



 functions for comparing `Integer` type, implemented in integergmp and integersimple libraries, received a similar treatment. Technically they are not primops, because they are implemented in Haskell (in case of integergmp also with FFI), but they pretend to be ones. There are six primops for comparing `Integer` values:






```wiki



eqInteger# :: Integer > Integer > Int#

...  ...  @@ 151,9 +148,12 @@ Below is a summary of implementation details and decisions: 


geInteger# :: Integer > Integer > Int#



```






Each of these functions has a wrapper that calls `tagToEnum#` and returns a `Bool`. These wrappers are: `eqInteger`, `neqInteger`, `leInteger`, `ltInteger`, `gtInteger` and `geInteger`.






 This change also required some small adjustments in `base` package.



Each of these functions has a wrapper that calls `tagToEnum#` and returns a `Bool`. These wrappers are: `eqInteger`, `neqInteger`, `leInteger`, `ltInteger`, `gtInteger` and `geInteger`.






 Six primops are an exception to the rules above: `sameMutableArray#`, `sameMutableByteArray#`, `sameMutableArrayArray#`, `sameMutVar#`, `sameMVar#` and `sameTVar#`. Their names have remained the same as before and new wrappers created for them lack `#` at the end of their name. We made that decission because this naming feels more consistent and these primops are rarely used so we expect that they won't break a lot of existing code.






 Other libraries that were modified to work with the new primops are: base, ghcprim and primitive. The only required modifications were imports of the GHC.PrimWrappers module in modules that use the primops.






## Eliminating branches using new primops




...  ...  