Unboxed Booleans

Right now the only way to compare two integers is with primops that produce boxed bools:

<#  :: Int# -> Int# -> Bool
==# :: Int# -> Int# -> Bool

To consume the resulting Bool we need a case-expression, which introduces branches into the core IR and object code. Case expressions are bad in the presence of heavy inlining because case-of-case performed by the GHC simplifier tends to duplicate code (like in DPH and Repa programs). Mis-predicted branches are bad in object code because they stall the pipeline.

Consider the following expression:

 case  x <# 0# || x >=# aWidth
    || y <# 0# || y >=# aHeight of 
  True  -> ...
  False -> ...

This is very common in array programming. Ideally, it should turn into some straight-line code to compute the flag, and then a single branch instruction once we've worked out what alternative to take. However, as the only way to consume the Bools produced by the comparisons is to introduce more case expressions, we end up with *four* cases in the core IR.

What I want is this:

data Bool#
(.<#)  :: Int#  -> Int#  -> Bool#
(.==#) :: Int#  -> Int#  -> Bool#
(.||#) :: Bool# -> Bool# -> Bool#

case    x .<# 0# .||# x .>=# aWidth
   .||# y .<# 0# .||# y .>=# aHeight of
 True#  -> ...
 False# -> ...

Bool# is the type of one bit integers. I can compute with them algebraically and be sure that I'll get at most one branch instruction in the resulting object code.

mentioned in issue #605

changed weight to 5

added Tfeature request Trac import labels

Good point. I had not fully grokked that reason for having unboxed Bool#. See also #605.

However I don't think it would be a good plan to define

data Bool = B# Bool#

For one thing, the definition of Bool is in the language spec. Well I suppose we could define

fromBool :: Bool -> Bool#
toBool   :: Bool# -> Bool

(Actually these already exist, more or less, in the form of tagToEnum# and dataToTag#.)

I suppose we could then define not, (&&) etc thus:

not :: Bool -> Bool
not b = toBool (not# (fromBool b))

(&&) :: Bool -> Bool -> Bool
a && b = toBool (and# (fromBool a) (fromBool b))

What would happen to optimisations? As thing stand we get

not (not x) 

= { inline not, twice }
  case (case x of { T -> F; F -> T }) of { T -> F; F -> T }

= { case of case transformation }
  case x of
     T -> case F of { T -> F; F -> T }
     F -> case T of { T -> F; F -> T }

= { simplify cases }
  case x of 
     T -> T
     F -> F

= { case of identity }
  x

(And then we simplify to just x, but that's a separate matter.) To get this behaviour with the new stuff we would presumably say:

not (not x)

= { inline not, twice }
  toBool (not# (fromBool (toBool (not# (fromBool x)))))

= { RULE fromBool (toBool v) = v }
  toBool (not# (not# (fromBool x)))

= { RULE not# (not# v) = v }
  toBool (fromBool x)

= { RULE fromBool (toBool v) = v }
  x

If anything this seems simpler. We'd also need constant folding stuff like

   case x of
     True -> ....(fromBool x)....
===>
   case x of
     True -> ....True#....

but that should not be hard.

I was not optimistic when I started writing this, but now I've got this far it does actually look plausible. It is certainly true that conditionals with a lot of conditions can generate an absolute rats-nest of join points -- and that in turn can inhibt inlining. So the change would help that too.

I suppose that Bool# might be better spelt Word1#.

Can anyone think of any other wrinkles to consider?

Simon

Simon, your && is strict in both arguments so it doesn't work.

In general, I don't really think there is a lot to be gained here. You have to make sure that you (a) don't change the semantics of a program and (b) don't do too much unnecessary work. Let's take Ben's two examples:

case  x <# 0# || x >=# aWidth
    || y <# 0# || y >=# aHeight of 
  True  -> ...
  False -> ...

case    x .<# 0# .||# x .>=# aWidth
   .||# y .<# 0# .||# y .>=# aHeight of
 True#  -> ...
 False# -> ...

It is impossible to tell which of the two will be faster. If we expect x <# 0 to hold most of the time, then the second one will be slower since it will be doing three unnecessary comparisons in most iterations for no benefit. On the other hand, if the condition doesn't hold most of the time, then the second one might be slightly faster.

I fully agree that join points etc. can be very annoying, though.

Darn. I'd forgotten about the strictness issue!

If we end up doing something like this, we should consider if it could be extended to work for any enumeration (i.e. data type with only nullary constructors.)

Note that the case expressions are optimised to a simple inline comparison in the code generator, so it's not as bad as it seems.

However, the special case in the code generator is annoying, so I had been meaning to change all these primops to return Int#.

In your example:

case  x <# 0# || x >=# aWidth
    || y <# 0# || y >=# aHeight of 
  True  -> ...
  False -> ...

We would want to end up with

case  x <# 0# `or#` x >=# aWidth
    `or#` y <# 0# `or#` y >=# aHeight of 
  0# -> ...
  _  -> ...

But getting there could be a bit tricky. Still, I think changing the primops is a good first step.

changed milestone to %7.8.1

Trac metadata

Trac field	Value
Related	→ #605

It would be pretty awesome if any enumeration (all-nullary constructors) could be treated as codegen-equivalent to Int# internally, with Enum, Eq, and Ord just being wrappers around the obvious primops. Though I'm not sure what the moving parts of such a proposal would be.

Trac metadata

Trac field	Value
CC	dterei → dterei, hackage.haskell.org@liyang.hu

See PrimBool.

Janek, great initiative thanks. But I think it would be helpful to articulate a very clear story about the goal. I believe that the goal is to achieve much better performance, without changing the source language. The programmer does not change the program, but they run faster.

If so, then can we have (on the wiki page, not here):

• A description of why programs will go faster, with specific examples.
• Some example programs that will in fact go faster. Maybe you can code the examples up in Haskell, using inconvenient and messy Int# or whatever, to demonstrate that they really do go faster.

The sub-text is that I only want to introduce new complexity if it demonstrably buys us something.

One reason that things may go faster is this. At the moment, if a function is strict in a Bool argument, that argument is still passed boxed. But it could very sensibly be passed unboxed instead, just as we do with pairs, say. So perhaps strictness analysis would work well with unboxed enumerations.

But it's not entirely obvious that it will. Unboxing a pair is great because the pair is never allocated. But enumerations are never allocated either! (True and False are statically allocated.) Moreover, even though passing True passes a pointer to a (statically allocated) heap object, the True/False tag is in the pointer (see Faster laziness using dynamic pointer tagging), so no memory access is needed when discriminating True/False. So the gains from unboxing may be modest.

Pointer tagging only works for data types with a handful of constructors. Big enumerations really do keep the tag in memory. (See the paper.)

None of this is to say it's a bad idea. Just that we need clarity about where the gains are going to come from, and measurements that suggest the gains are real.

Simon

assigned to @trac-jstolarek

I agree with Simon, I think we already got a lot of the benefit to be had here from pointer tagging. Perhaps for enums larger than the threshold (3 or 7 for 32-bit or 64-bit respectively) we should be unboxing them in worker/wrapper. It wouldn't be hard to write some examples by hand and measure the difference between using enums and Int#.

I would like to see the simplification I mentioned above - changing the comparison primops to return Int# rather than Bool - and I believe that would lead to more optimisations later. At the least it would expose the magic tagToEnum# that arises from these primops to the simplifier, where it could be optimised away.

I read paper about pointer tagging and things seem to be clearer now. I rewrote wiki page about PrimBool from scratch. I think that now it defines the goal very clearly by giving code examples. There are also workarounds for the problem. If you guys could take a look and tell me if this makes sense it would be great.

I failed to figure out a code example that would actually go faster using my workarounds. The ones I created have about 0,4% increase in performance, which is a negligible difference. I will be working on this.

I linked the wrong page in my comment. Here's the correct one.