[PROPOSAL] Add `FiniteBits(count{Leading,Trailing}Zeros)`

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

[PROPOSAL] Add `FiniteBits(count{Leading,Trailing}Zeros)`

Herbert Valerio Riedel
Hello *,

As GHC 7.10.1 will have support for new assembler-optimized CLZ & CTZ[1]
primops[2], it'd be useful to provide also a convenient high-level
interface to avoid having to work with -XMagicHash and unboxed values.

To this end, I hereby propose to add two new methods to the 'FiniteBits'
class, specifically


  class Bits b => FiniteBits b where
    {- ... -}

    countLeadingZeros :: b -> Int
    countLeadingZeros x = (w-1) - go (w-1)
      where
        go i | i < 0       = i -- no bit set
             | testBit x i = i
             | otherwise   = go (i-1)

        w = finiteBitSize x

    countTrailingZeros :: b -> Int
    countTrailingZeros x = go 0
      where
        go i | i >= w      = i
             | testBit x i = i
             | otherwise   = go (i+1)

        w = finiteBitSize x


The full patch (including Haddock doc-strings) is available for code
review at

  https://phabricator.haskell.org/D158

I suggest to try to keep the discussion/voting/bikeshedding about the
proposal proper here (including any bike-shedding about naming). At same
time, I'd like to invite you to try out the Phab code-revision tool[3]
for pointing-out/discussing technical issues with the proposed patch.


Cheers,
  hvr

 [1]: http://en.wikipedia.org/wiki/Find_first_set provides a good
      overview why CLZ/CTZ are desirable primitive operations.

 [2]: http://git.haskell.org/ghc.git/commit/e0c1767d0ea8d12e0a4badf43682a08784e379c6

 [3]: Phab code-revisions allow you to directly annotate code-fragments.
      However, after having written inline annotations, you have to actually
      submit those by submitting a non-inline (possibly empty) comment
      (see bottom of that page) to make them visible for everyone.
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: [PROPOSAL] Add `FiniteBits(count{Leading,Trailing}Zeros)`

David Feuer
+1 from me. The names sound reasonable.

On Fri, Aug 15, 2014 at 4:22 AM, Herbert Valerio Riedel <[hidden email]> wrote:

> Hello *,
>
> As GHC 7.10.1 will have support for new assembler-optimized CLZ & CTZ[1]
> primops[2], it'd be useful to provide also a convenient high-level
> interface to avoid having to work with -XMagicHash and unboxed values.
>
> To this end, I hereby propose to add two new methods to the 'FiniteBits'
> class, specifically
>
>
>   class Bits b => FiniteBits b where
>     {- ... -}
>
>     countLeadingZeros :: b -> Int
>     countLeadingZeros x = (w-1) - go (w-1)
>       where
>         go i | i < 0       = i -- no bit set
>              | testBit x i = i
>              | otherwise   = go (i-1)
>
>         w = finiteBitSize x
>
>     countTrailingZeros :: b -> Int
>     countTrailingZeros x = go 0
>       where
>         go i | i >= w      = i
>              | testBit x i = i
>              | otherwise   = go (i+1)
>
>         w = finiteBitSize x
>
>
> The full patch (including Haddock doc-strings) is available for code
> review at
>
>   https://phabricator.haskell.org/D158
>
> I suggest to try to keep the discussion/voting/bikeshedding about the
> proposal proper here (including any bike-shedding about naming). At same
> time, I'd like to invite you to try out the Phab code-revision tool[3]
> for pointing-out/discussing technical issues with the proposed patch.
>
>
> Cheers,
>   hvr
>
>  [1]: http://en.wikipedia.org/wiki/Find_first_set provides a good
>       overview why CLZ/CTZ are desirable primitive operations.
>
>  [2]: http://git.haskell.org/ghc.git/commit/e0c1767d0ea8d12e0a4badf43682a08784e379c6
>
>  [3]: Phab code-revisions allow you to directly annotate code-fragments.
>       However, after having written inline annotations, you have to actually
>       submit those by submitting a non-inline (possibly empty) comment
>       (see bottom of that page) to make them visible for everyone.
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: [PROPOSAL] Add `FiniteBits(count{Leading,Trailing}Zeros)`

Johan Tibell-2
In reply to this post by Herbert Valerio Riedel
+1


On Fri, Aug 15, 2014 at 10:22 AM, Herbert Valerio Riedel <[hidden email]> wrote:
Hello *,

As GHC 7.10.1 will have support for new assembler-optimized CLZ & CTZ[1]
primops[2], it'd be useful to provide also a convenient high-level
interface to avoid having to work with -XMagicHash and unboxed values.

To this end, I hereby propose to add two new methods to the 'FiniteBits'
class, specifically


  class Bits b => FiniteBits b where
    {- ... -}

    countLeadingZeros :: b -> Int
    countLeadingZeros x = (w-1) - go (w-1)
      where
        go i | i < 0       = i -- no bit set
             | testBit x i = i
             | otherwise   = go (i-1)

        w = finiteBitSize x

    countTrailingZeros :: b -> Int
    countTrailingZeros x = go 0
      where
        go i | i >= w      = i
             | testBit x i = i
             | otherwise   = go (i+1)

        w = finiteBitSize x


The full patch (including Haddock doc-strings) is available for code
review at

  https://phabricator.haskell.org/D158

I suggest to try to keep the discussion/voting/bikeshedding about the
proposal proper here (including any bike-shedding about naming). At same
time, I'd like to invite you to try out the Phab code-revision tool[3]
for pointing-out/discussing technical issues with the proposed patch.


Cheers,
  hvr

 [1]: http://en.wikipedia.org/wiki/Find_first_set provides a good
      overview why CLZ/CTZ are desirable primitive operations.

 [2]: http://git.haskell.org/ghc.git/commit/e0c1767d0ea8d12e0a4badf43682a08784e379c6

 [3]: Phab code-revisions allow you to directly annotate code-fragments.
      However, after having written inline annotations, you have to actually
      submit those by submitting a non-inline (possibly empty) comment
      (see bottom of that page) to make them visible for everyone.
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: [PROPOSAL] Add `FiniteBits(count{Leading,Trailing}Zeros)`

Milan Straka
In reply to this post by Herbert Valerio Riedel
Hi all,

+1 here.

Cheers,
Milan

> -----Original message-----
> From: Herbert Valerio Riedel <[hidden email]>
> Sent: 15 Aug 2014, 10:22
>
> Hello *,
>
> As GHC 7.10.1 will have support for new assembler-optimized CLZ & CTZ[1]
> primops[2], it'd be useful to provide also a convenient high-level
> interface to avoid having to work with -XMagicHash and unboxed values.
>
> To this end, I hereby propose to add two new methods to the 'FiniteBits'
> class, specifically
>
>
>   class Bits b => FiniteBits b where
>     {- ... -}
>
>     countLeadingZeros :: b -> Int
>     countLeadingZeros x = (w-1) - go (w-1)
>       where
>         go i | i < 0       = i -- no bit set
>              | testBit x i = i
>              | otherwise   = go (i-1)
>
>         w = finiteBitSize x
>
>     countTrailingZeros :: b -> Int
>     countTrailingZeros x = go 0
>       where
>         go i | i >= w      = i
>              | testBit x i = i
>              | otherwise   = go (i+1)
>
>         w = finiteBitSize x
>
>
> The full patch (including Haddock doc-strings) is available for code
> review at
>
>   https://phabricator.haskell.org/D158
>
> I suggest to try to keep the discussion/voting/bikeshedding about the
> proposal proper here (including any bike-shedding about naming). At same
> time, I'd like to invite you to try out the Phab code-revision tool[3]
> for pointing-out/discussing technical issues with the proposed patch.
>
>
> Cheers,
>   hvr
>
>  [1]: http://en.wikipedia.org/wiki/Find_first_set provides a good
>       overview why CLZ/CTZ are desirable primitive operations.
>
>  [2]: http://git.haskell.org/ghc.git/commit/e0c1767d0ea8d12e0a4badf43682a08784e379c6
>
>  [3]: Phab code-revisions allow you to directly annotate code-fragments.
>       However, after having written inline annotations, you have to actually
>       submit those by submitting a non-inline (possibly empty) comment
>       (see bottom of that page) to make them visible for everyone.
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/libraries
>
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: [PROPOSAL] Add `FiniteBits(count{Leading,Trailing}Zeros)`

Herbert Valerio Riedel
In reply to this post by Herbert Valerio Riedel
On 2014-08-15 at 10:22:38 +0200, Herbert Valerio Riedel wrote:
> As GHC 7.10.1 will have support for new assembler-optimized CLZ & CTZ[1]
> primops[2], it'd be useful to provide also a convenient high-level
> interface to avoid having to work with -XMagicHash and unboxed values.
>
> To this end, I hereby propose to add two new methods to the 'FiniteBits'
> class, specifically

PS: I forgot to explicitly declare the usual *2-week discussion period*
    (which I guess many would have implicitly assumed anyway...)
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: [PROPOSAL] Add `FiniteBits(count{Leading,Trailing}Zeros)`

Edward Kmett-2
In reply to this post by Herbert Valerio Riedel
A very enthusiastic +1 from me. I'll finally be able to drop custom foreign prims from my own code.


On Fri, Aug 15, 2014 at 4:22 AM, Herbert Valerio Riedel <[hidden email]> wrote:
Hello *,

As GHC 7.10.1 will have support for new assembler-optimized CLZ & CTZ[1]
primops[2], it'd be useful to provide also a convenient high-level
interface to avoid having to work with -XMagicHash and unboxed values.

To this end, I hereby propose to add two new methods to the 'FiniteBits'
class, specifically


  class Bits b => FiniteBits b where
    {- ... -}

    countLeadingZeros :: b -> Int
    countLeadingZeros x = (w-1) - go (w-1)
      where
        go i | i < 0       = i -- no bit set
             | testBit x i = i
             | otherwise   = go (i-1)

        w = finiteBitSize x

    countTrailingZeros :: b -> Int
    countTrailingZeros x = go 0
      where
        go i | i >= w      = i
             | testBit x i = i
             | otherwise   = go (i+1)

        w = finiteBitSize x


The full patch (including Haddock doc-strings) is available for code
review at

  https://phabricator.haskell.org/D158

I suggest to try to keep the discussion/voting/bikeshedding about the
proposal proper here (including any bike-shedding about naming). At same
time, I'd like to invite you to try out the Phab code-revision tool[3]
for pointing-out/discussing technical issues with the proposed patch.


Cheers,
  hvr

 [1]: http://en.wikipedia.org/wiki/Find_first_set provides a good
      overview why CLZ/CTZ are desirable primitive operations.

 [2]: http://git.haskell.org/ghc.git/commit/e0c1767d0ea8d12e0a4badf43682a08784e379c6

 [3]: Phab code-revisions allow you to directly annotate code-fragments.
      However, after having written inline annotations, you have to actually
      submit those by submitting a non-inline (possibly empty) comment
      (see bottom of that page) to make them visible for everyone.
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: [PROPOSAL] Add `FiniteBits(count{Leading,Trailing}Zeros)`

Carter Schonwald
+1


On Fri, Aug 15, 2014 at 11:26 AM, Edward Kmett <[hidden email]> wrote:
A very enthusiastic +1 from me. I'll finally be able to drop custom foreign prims from my own code.


On Fri, Aug 15, 2014 at 4:22 AM, Herbert Valerio Riedel <[hidden email]> wrote:
Hello *,

As GHC 7.10.1 will have support for new assembler-optimized CLZ & CTZ[1]
primops[2], it'd be useful to provide also a convenient high-level
interface to avoid having to work with -XMagicHash and unboxed values.

To this end, I hereby propose to add two new methods to the 'FiniteBits'
class, specifically


  class Bits b => FiniteBits b where
    {- ... -}

    countLeadingZeros :: b -> Int
    countLeadingZeros x = (w-1) - go (w-1)
      where
        go i | i < 0       = i -- no bit set
             | testBit x i = i
             | otherwise   = go (i-1)

        w = finiteBitSize x

    countTrailingZeros :: b -> Int
    countTrailingZeros x = go 0
      where
        go i | i >= w      = i
             | testBit x i = i
             | otherwise   = go (i+1)

        w = finiteBitSize x


The full patch (including Haddock doc-strings) is available for code
review at

  https://phabricator.haskell.org/D158

I suggest to try to keep the discussion/voting/bikeshedding about the
proposal proper here (including any bike-shedding about naming). At same
time, I'd like to invite you to try out the Phab code-revision tool[3]
for pointing-out/discussing technical issues with the proposed patch.


Cheers,
  hvr

 [1]: http://en.wikipedia.org/wiki/Find_first_set provides a good
      overview why CLZ/CTZ are desirable primitive operations.

 [2]: http://git.haskell.org/ghc.git/commit/e0c1767d0ea8d12e0a4badf43682a08784e379c6

 [3]: Phab code-revisions allow you to directly annotate code-fragments.
      However, after having written inline annotations, you have to actually
      submit those by submitting a non-inline (possibly empty) comment
      (see bottom of that page) to make them visible for everyone.
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries



_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: [PROPOSAL] Add `FiniteBits(count{Leading,Trailing}Zeros)`

Vincent Hanquez
In reply to this post by Herbert Valerio Riedel
good stuff ! +1

On 15/08/2014 10:22, Herbert Valerio Riedel wrote:

> Hello *,
>
> As GHC 7.10.1 will have support for new assembler-optimized CLZ & CTZ[1]
> primops[2], it'd be useful to provide also a convenient high-level
> interface to avoid having to work with -XMagicHash and unboxed values.
>
> To this end, I hereby propose to add two new methods to the 'FiniteBits'
> class, specifically
>
>
>    class Bits b => FiniteBits b where
>      {- ... -}
>
>      countLeadingZeros :: b -> Int
>      countLeadingZeros x = (w-1) - go (w-1)
>        where
>          go i | i < 0       = i -- no bit set
>               | testBit x i = i
>               | otherwise   = go (i-1)
>
>          w = finiteBitSize x
>
>      countTrailingZeros :: b -> Int
>      countTrailingZeros x = go 0
>        where
>          go i | i >= w      = i
>               | testBit x i = i
>               | otherwise   = go (i+1)
>
>          w = finiteBitSize x
>
>
> The full patch (including Haddock doc-strings) is available for code
> review at
>
>    https://phabricator.haskell.org/D158
>
> I suggest to try to keep the discussion/voting/bikeshedding about the
> proposal proper here (including any bike-shedding about naming). At same
> time, I'd like to invite you to try out the Phab code-revision tool[3]
> for pointing-out/discussing technical issues with the proposed patch.
>
>
> Cheers,
>    hvr
>
>   [1]: http://en.wikipedia.org/wiki/Find_first_set provides a good
>        overview why CLZ/CTZ are desirable primitive operations.
>
>   [2]: http://git.haskell.org/ghc.git/commit/e0c1767d0ea8d12e0a4badf43682a08784e379c6
>
>   [3]: Phab code-revisions allow you to directly annotate code-fragments.
>        However, after having written inline annotations, you have to actually
>        submit those by submitting a non-inline (possibly empty) comment
>        (see bottom of that page) to make them visible for everyone.
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

[Summary][PROPOSAL] Add `FiniteBits(count{Leading,Trailing}Zeros)`

Herbert Valerio Riedel
In reply to this post by Herbert Valerio Riedel

This proposal passed with six +1s (other than myself), specifically by
 
 - David Feuer
 - Johan Tibell
 - Milan Straka
 - Edward Kmett
 - Carter Schonwald
 - Vincent Hanquez

There were no -1s (I'm aware of), and no concerns were raised.


The proposed implementation has already been pushed as per

   http://git.haskell.org/ghc.git/commitdiff/a8a969ae7a05e408b29961d0a2ea621a16d73d3e


On the whole, this was quite a bor^H^H^Hefficient proposal discussion :-)


Cheers,
  hvr

On 2014-08-15 at 10:22:38 +0200, Herbert Valerio Riedel wrote:

> Hello *,
>
> As GHC 7.10.1 will have support for new assembler-optimized CLZ & CTZ[1]
> primops[2], it'd be useful to provide also a convenient high-level
> interface to avoid having to work with -XMagicHash and unboxed values.
>
> To this end, I hereby propose to add two new methods to the 'FiniteBits'
> class, specifically
>
>
>   class Bits b => FiniteBits b where
>     {- ... -}
>
>     countLeadingZeros :: b -> Int
>     countLeadingZeros x = (w-1) - go (w-1)
>       where
>         go i | i < 0       = i -- no bit set
>              | testBit x i = i
>              | otherwise   = go (i-1)
>
>         w = finiteBitSize x
>
>     countTrailingZeros :: b -> Int
>     countTrailingZeros x = go 0
>       where
>         go i | i >= w      = i
>              | testBit x i = i
>              | otherwise   = go (i+1)
>
>         w = finiteBitSize x
>
>
> The full patch (including Haddock doc-strings) is available for code
> review at
>
>   https://phabricator.haskell.org/D158
>
> I suggest to try to keep the discussion/voting/bikeshedding about the
> proposal proper here (including any bike-shedding about naming). At same
> time, I'd like to invite you to try out the Phab code-revision tool[3]
> for pointing-out/discussing technical issues with the proposed patch.
>
>
> Cheers,
>   hvr
>
>  [1]: http://en.wikipedia.org/wiki/Find_first_set provides a good
>       overview why CLZ/CTZ are desirable primitive operations.
>
>  [2]: http://git.haskell.org/ghc.git/commit/e0c1767d0ea8d12e0a4badf43682a08784e379c6
>
>  [3]: Phab code-revisions allow you to directly annotate code-fragments.
>       However, after having written inline annotations, you have to actually
>       submit those by submitting a non-inline (possibly empty) comment
>       (see bottom of that page) to make them visible for everyone.

--
"Elegance is not optional" -- Richard O'Keefe
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries