Proposal: change the Bits instance for Bool to align with other basic types and support branchless calculations

Carter Schonwald carter.schonwald at
Sun Sep 28 20:15:01 UTC 2014

Brandon, I think you're articulating a very good point here, in noting that
the current set of instances for Bits that *are* *strict* are precisely so
because their underlying representations are *spine strict*!

>From that perspective, it is definitely valid to argue that the
shortcircuiting behavior of bool is in fact correct.

Its also  important to keep in mind that theres many examples where the
branchless version of bool is not a win,
and we've not yet articulated an example where someone will be writing code
that is both generic AND branchless (indeed, I'm not certain if there is
actually a meaningful performance win in the fully polymorphic case when
its the desired semantics).

Additionally, one entire space left unaddressed here is this: "why cant we
formulate an optimization algorithm to add to ghc that tries to estimate
when transformation into a (relatively) branchless formulation of the same

a style i've grown to favor is the following: make it easy to write generic
code thats always correct (wrt complexity), and make it sane to do
specialization/optimization by hand later (and/or teach the compiler.)

I guess my point here is this: while i've many examples of code i've
written that has benefited from being rewritten in a branch free form, that
is because of *bad branch prediction* rather than branching itself.
Branchless code is immune to that problem, but if you dont have bad branch
prediction, the *branching* code will be *faster* */ simpler* than the *branch
free * code.

On Sun, Sep 28, 2014 at 4:03 PM, Brandon Allbery <allbery.b at>

> On Sun, Sep 28, 2014 at 2:45 PM, David Feuer <david.feuer at>
> wrote:
>> I would think what you're trying to do would likely be better with a
>> different class, by another name, supporting things like .&&., .||., etc.,
>> or maybe even moving && and || into a class.
> So, if I look at this from the angle that the strictness of other Bits
> instances is an artifact of their being spine-strict bit vectors, I get
> that the correct answer to this is not a new class but a "strict" newtype
> on Bool. The standard lazy Bool is by far the more common one, so it's the
> strict variant that gets the newtype. (Compare the Sum and Product monoid
> newtype-s.)
> --
> brandon s allbery kf8nh                               sine nomine
> associates
> allbery.b at
> ballbery at
> unix, openafs, kerberos, infrastructure, xmonad
> _______________________________________________
> Libraries mailing list
> Libraries at
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the Libraries mailing list