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

[Edward Kmett]

In my quick tests, the branchless form only looked to be about 10% faster.

If others have better benchmarks, I'm happy to defer as my methodology was
rather sloppy.

Considering the alternative is an asymptotic hit, I'm having a hard time
favoring the branchless form as well.

-Edward

On Sun, Sep 28, 2014 at 6:06 AM, Milan Straka <fox at ucw.cz> wrote:

> Hi all,
>
> I am not really convinced that the proposed implementation will be
> faster -- if the short-circuiting kicks in, I believe it will perform
> better, even if it uses conditional branching.
>
> So unless being convinced by benchmark results, I would prefer the
> lazier version of these operators.
>
> Cheers,
> Milan
>
> > -----Original message-----
> > From: David Feuer <david.feuer at gmail.com>
> > Sent: 27 Sep 2014, 13:59
> >
> > ...
> > Currently, the (.&.) and (.|.) methods for Bool are short-circuiting,
> > defined like this:
> >
> > instance Bits Bool where
> >     (.&.) = (&&)
> >
> >     (.|.) = (||)
> >
> > Unlike the instances for Int, Word, etc., this gives short-circuiting
> > behavior (conditionally lazy in the second operand). Unfortunately, this
> > requires a conditional branch to implement, which can sometimes be bad.
> > Since (&&) and (||) are readily available to anyone who wants
> > short-circuiting, I propose that we use the following instead. Note that
> > the Bits class does not specify anything about this aspect of instance
> > behavior.
> >
> >   x .&. y = tagToEnum# (dataToTag# x `andI#` dataToTag# y)
> >
> >   x .|. y = tagToEnum# (dataToTag# x `orI#` dataToTag# y)
> >
> > The rest of the operations look like this:
> >
> >     x `xor` y = tagToEnum# (dataToTag# x `xorI#` dataToTag# y)
> >
> >     complement x = tagToEnum# (dataToTag# x `xorI#` 1#)
> >
> >     shift x s = testBit x s
> >
> >     rotate x _ = x
> >
> > -- I don't think we gain anything changing this one.
> >     bit 0 = True
> >     bit _ = False
> >
> >     testBit x b = tagToEnum# (dataToTag# x `andI#` (dataToTag# b ==# 0#))
> >
> >     bitSizeMaybe _ = Just 1
> >
> >     bitSize _ = 1
> >
> >     isSigned _ = False
> >
> >     popCount x = I# (dataToTag# x)
> >
> > instance FiniteBits Bool where
> >     finiteBitSize _ = 1
> >     countTrailingZeros x = I# (dataToTag# x `xorI#` 1#)
> >     countLeadingZeros  x = I# (dataToTag# x `xorI#` 1#)
>
> > _______________________________________________
> > Libraries mailing list
> > Libraries at haskell.org
> > http://www.haskell.org/mailman/listinfo/libraries
>
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20140928/a2fa08f4/attachment.html>