Go: math/bits: an integer bit twiddling library

[brtzsnr]

Previous discussions at https://github.com/golang/go/issues/17373 and https://github.com/golang/go/issues/10757.

Abstract

This proposal introduces a set of API for integer bit twiddling.

Background

This proposal introduces a set of API for integer bit twiddling. For this proposal we are interested in the following functions:

• ctz - count trailing zeros.
• clz - count leading zeros; log_2.
• popcnt - count population; hamming distance; integer parity.
• bswap - reverses the order of bytes.

These functions were picked by surveying:

• Go compiler and tools
• Popular libraries
• golang-nuts@ discussions list
• Bit Twiddling Hacks - https://graphics.stanford.edu/~seander/bithacks.html
• A curated list of awesome bitwise operations and tricks - https://github.com/keonkim/awesome-bits

We limited ourselves to these four functions because other twiddling
tricks are very simple to implement using the proposed library,
or already available Go constructs.

We found implementations for a subset of the selected twiddling functions
in many packages including runtime, compiler and tools:

| package | clz | ctz | popcnt | bswap |
| --- | --- | --- | --- | --- |
| math/big | X | X | | |
| runtime/internal/sys | X | X | | X |
| tools/container/intsets | X | | X | |
| cmd/compile/internal/ssa | X | | X | |
| code.google.com/p/intmath | X | X | | |
| github.com/hideo55/go-popcount | | | X (asm) | |
| github.com/RoaringBitmap/roaring | | X | X (asm) | |
| github.com/tHinqa/bitset | X | X | X | |
| github.com/willf/bitset | X | | X (asm) | |
| gopl.io/ch2/popcount | | | X | |
| GCC builtins | X | X | X | X |

Many other packages implement a subset of these functions:

• http://go-search.org/search?q=popcount returns 58 packages.
• http://go-search.org/search?q=popcnt returns 11 packages.
• TODO(mosoi): Other relevant searches?

Similarly hardware providers have recognized the importance
of such functions and included machine level support.
Without hardware support these operations are very expensive.

| arch | clz | ctz | popcnt | bswap |
| --- | --- | --- | --- | --- |
| AMD64 | X | X | X | X |
| ARM | X | X | ? | X|
| ARM64 | X | X | ? | X|
| S390X | X | X | ? | X|

All bit twiddling functions, except popcnt, are already implemented by runtime/internal/sys and receive special support from the compiler in order to "to help get the very best performance". However, the compiler support is limited to the runtime package and other Golang users have to reimplement the slower variant of these functions.

Proposal

We introduce a new std library math/bits with the following external API, to provides compiler / hardware optimized implementations of clz, ctz, popcnt and bswap functions.

package bits

// SwapBytes16 reverses the order of bytes in a 16-bit integer.
func SwapBytes16(uint16) uint16
// SwapBytes32 reverses the order of bytes in a 32-bit integer.
func SwapBytes32(uint32) uint32
// SwapBytes64 reverses the order of bytes in a 64-bit integer.
func SwapBytes64(uint64) uint64

// TrailingZeros32 counts the number of trailing zeros in a 32-bit integer, and if all are zero, then 32.
func TrailingZeros32(uint32) uint
// TrailingZeros64 counts the number of trailing zeros in a 64-bit integer, and if all are zero, then 64.
func TrailingZeros64(uint64) uint

// LeadingZeros32 counts the number of trailing zeros in a 32-bit integer, and if all are zero, then 32.
func LeadingZeros32(uint32) uint
// LeadingZeros64 counts the number of trailing zeros in a 64-bit integer, and if all are zero, then 64.
func LeadingZeros64(uint64) uint

// Ones32 counts the number of bits set in a 32-bit integer.
func Ones32(uint32) uint
// Ones64 counts the number of bits set in a 64-bit integer.
func Ones64(uint64) uint

Rationale

Alternatives to this proposal are:

• Bit twiddling functions are implemented in an external library not supported by the compiler. This approach works and is the current state of affairs. Runtime uses the compiler supported methods, while Golang users continue to use the slower implementations.
• The external library is supported by the compiler. Given that we expect this library to replace runtime/internal/sys it means that this library must be in lock with the compiler and live in the standard library.

Compatibility

This proposal does not change or breaks any existing stdlib API and it conforms to compatibly guidelines.

Implementation

SwapBytes, TrailingZeros and LeadingZeros are already implemented. The only missing function is Ones which can be implemented similarly to the other functions. If this proposal is accepted it can be implemented in time for Go1.9.

Open issues (if applicable)

Names are hard, bike shed is in the comments.

Please suggest additional functions to be included in the comments. Ideally, please include where such function is used in stdlib (e.g. math/big), tools or popular packages.

So far the following functions have been proposed and are under consideration:

• RotateLeft / RotateRight
  
  
  
  • Pros: &63 is no longer need to compile a rotate with non-const argument to a single instruction on x86, x86-64..
  
  
  • Cons: very short/simple to implement and inline.
  
  
  • Used: crypto/ uses the constant rotate which is handled properly by the compiler.
  
  
• ReverseBits
  
  
  
  • Pros: ?
  
  
  • Cons: ?
  
  
  • Used: ?
  
  
• Add/Sub with carry return
  
  
  
  • Pros: Expensive otherwise
  
  
  • Cons: ?
  
  
  • Used: math/big
  
  

History

14.Jan: Clarified the output of TrailingZeros and LeadingZeros when the argument is 0.
14.Jan: Renamed methods: CountTrailingZeros -> TrailingZeros, CountLeadingZeros -> LeadingZeros, CountOnes -> Ones.
13.Jan: Fixed architecture name.
11.Jan: Initial proposal opened to public.

[cespare]

@brtzsnr perhaps you should submit this document to the proposal repo as outlined in the proposal process steps?

Since it's already markdown following the template, it should be easy to copy-paste into a CL creating a file design/18616-bit-twiddling.md (or whatever).

[brtzsnr]

@cespare from https://github.com/golang/proposal "if the author wants to write a design doc, then they can write one". It started as a design doc, if there is strong feeling that I should submit this, I'm totally fine.

[griesemer]

I'd be ok with this, it's common enough functionality used in many algorithmic libraries and math/bits seems like an appropriate place.

(For one, math/big also implements nlz (== clz).)

There's probably some bike shedding about the names. I for one would prefer the functions to say what they return rather than what they do; which in turn may lead to shorter names. For instance:

bits.TrailingZeros64(x) rather than bits.CountTrailingZeros64(x)

and so forth.

[griesemer]

The proposal seems pretty clear and minimal - a design doc seems overkill. I think a CL would be more appropriate at this point.

(That is a CL with API and basic implementation - for purpose of discussion in place of a design doc. We still need to decide if this proposal should be accepted or not.)

[cespare]

@brtzsnr has already written the design document: it's in the issue description and it follows the the template. I assumed that there was some value in having these documents all in one location.

[cespare]

The last arch listed in the hardware support table is "BSWAP" -- typo?

[josharian]

Thanks for writing this up.

The doc string for ctz and clz should specify the result when passed 0.

I also prefer (e.g.) TrailingZeros32 to CountTrailingZeros32. I'd also be happy with Ctz32. It is concise, familiar to most, and easily googleable for the rest.

[cherrymui]

Thanks for the proposal.
I just want to add that we probably also want to focus on the use, instead of focusing only on the instructions. For example, @dr2chase once found there are several log2 functions in the compiler/assembler. It is close to CLZ but not the same. Functions like this should probably also in the bit twiddling package. And maybe also include useful functions that are not related to these instructions.

[minux]

How about we provide a package for all bit twiddling primitives defined by
the Hacker's Delight?

When designing the package, we don't need to consider whether the function
can be intrinsicified or not. The optimization can happen later. That is,
don't let low level implementation control the upper level package
interface. We want a good package interface, even if some of them can not
be mapped to single instruction.

[dsnet]

@minux, fortunately, every bit twiddling function I've needed so far is exactly the ones that are in this proposal.

[dr2chase]

Following Hacker's Delight has the advantage that we don't need to waste time arguing about the names.

[minux]

I'd like to add the following:

ReverseBits (for uint32 and uint64)
RotateLeft/Right (can be expanded inline with two shifts, but the compiler
can't always do the transformation due to shift range issues)

Maybe also two results form of add and substract? E.g.

func AddUint32(x, y, carryin uint32) (carryout, sum uint32) // carryin must
be 0 or 1.
And similarly for uint64.

And SqrtInt.

Many of my suggestions can't be implemented in a single instruction, but
that is the point: we want a good bit twiddling package, not a mere
intrisics package. Don't let the hardware limit high level package
interface.

[josharian]

Relatedly, functions to check whether an add/multiply will overflow.

[thepudds]

A related data point: there are various issues that have been filed for faster cgo. In one such example (proposal #16051), the fact that fast implementation of bsr/ctz/etc. might happen was mentioned as hopefully chipping away at the set of use cases where people writing go are tempted to use cgo.

@aclements commented on Jul 1, 2016:

@eloff, there's been some discussion (though no concrete proposals to my knowledge) to add functions for things like popcount and bsr that would be compiled as intrinsics where supported (like math.Sqrt is today). With 1.7 we're trying this out in the runtime, which now has a ctz intrinsic available to it on amd64 SSA. Obviously that doesn't solve the overall problem, but it would chip away at one more reason to use cgo in a low-overhead context.

Many people (myself included) are attracted to go because of the performance, so things like this current proposal for bit twiddling would help. (And yes, cgo is also now faster in 1.8, which is nice as well).

[brtzsnr]

RotateLeft/Right (can be expanded inline with two shifts, but the compiler
can't always do the transformation due to shift range issues)

@minux Can you elaborate what is the problem?

[randall77]

@brtzsnr : I think what Minux is referring to is that when you write (x << k) | (x >> (64-k)), you know you're using 0 <= k < 64, but the compiler can't read your mind, and it is not obviously derivable from the code. If we had the function

func leftRot(x uint64, k uint) uint64 {
   k &= 63
   return (x << k) | (x >> (64-k))
}

Then we can make sure (via the &63) that the compiler knows that the range of k is bounded.
So if the compiler can't prove the input is bounded, then we need an extra AND. That's better than not generating the rotate assembly at all.

[minux]

On Fri, Jan 13, 2017 at 10:37 PM, Keith Randall [e-mail]
wrote:

@brtzsnr https://github.com/brtzsnr : I think what Minux is referring
to is that when you write (x << k) | (x >> (64-k)), you know you're using 0
<= k < 64, but the compiler can't read your mind, and it is not obviously
derivable from the code. If we had the function

func leftRot(x uint64, k uint) uint64 {
k &= 63
return (x << k) | (x >> (64-k))
}

Then we can make sure (via the &63) that the compiler knows that the range
of k is bounded.
So if the compiler can't prove the input is bounded, then we need an extra
AND. That's better than not generating the rotate assembly at all.

Right. If we define RotateLeft and RotateRight functions, we can formally
define the function rotate left/right k bits (no matter what k is). This is
similar to how our shift operations are defined. And this definition also
maps to actual rotate instruction nicely (unlike shifts, where our more
intuitive definition requires a compare on certain architectures).

[opennota]

How about byte and bit shuffling (and unshuffling) functions that are used by the blosc compression library? The slides (the shuffling starts from the slide 17). These functions can be SSE2/AVX2 accelerated.

[minux]

On Fri, Jan 13, 2017 at 11:24 PM, opennota [e-mail] wrote:

How about byte and bit shuffling functions that are used by the blosc
https://github.com/Blosc/c-blosc compression library? The slides
http://www.slideshare.net/PyData/blosc-py-data-2014 (the shuffling
starts from the slide 17). These functions can be SSE2/AVX2 accelerated.

SIMD is a bigger problem and it is out of the scope of this package. It's

17373.

[brtzsnr]

The current proposed functions have a Go native implementation much larger and disproportionally more expensive than optimum. On the other hand rotate is easy to write inline in a way that the compiler can recognize.

@minux and also everyone else: Do you know where rotate left/right is used with a non-constant number of rotated bits? crypto/sha256 uses rotate for example, but with constant number of bits.

[josharian]

rotate is easy to write inline in a way that the compiler can recognize.

It is easy for those who are familiar with the compiler's internals. Putting it in a math/bits package makes it easy for everyone.

Do you know where rotate left/right is used with a non-constant number of rotated bits?

Here's an example from #9337:

https://play.golang.org/p/rmDG7MR5F9

In each invocation it is a constant number of rotated bits each time, but the function itself is not currently inlined, so it compiles without any rotate instructions. A math/bits library function would definitely help here.

[minux]

On Sat, Jan 14, 2017 at 5:05 AM, Alexandru Moșoi [e-mail]
wrote:

The current proposed functions have a Go native implementation much larger
and disproportionally more expensive than optimum. On the other hand rotate
is easy to write inline in a way that the compiler can recognize.

As I stressed many times in this issue, this is not the correct way to
design a Go package. It ties too much to the underlying hardware. What we
want is a good bit twiddling package that is generally useful. Whether
functions can be expanded into a single instruction is irrelevant as long
as the API interface is well-known and generally useful.

@minux https://github.com/minux and also everyone else: Do you know
where rotate left/right is used with a non-constant number of rotated bits?
crypto/sha256 uses rotate for example, but with constant number of bits.

Even if in the actual problem the number of bits of rotate is constant, the
compiler might not be able to see that. E.g. when the shift count is stored
in an array, or hide in loop counter or even caller of a not inlined
function.

One simple example of using variable number of rotate is an interesting
implementation of popcount:
// https://play.golang.org/p/ctNRXsBt0z

func RotateRight(x, k uint32) uint32
func Popcount(x uint32) int {
    var v uint32
    for i := v - v; i < 32; i++ {
        v += RotateRight(x, i)
    }
    return int(-int32(v))
}

[brtzsnr]

@josharian The example looks like a bad inliner decision if rot is not inlined. Did you try to write the function as func rot(x, n) instead of rot = func(x, n)?

@minux: I agree with you. I'm not trying to tie the API to a particular instruction set; the hardware support is a nice bonus. My main focus is to find usages in the real code (not toy code) to understand the context, what is the best signature and how important is to provide everyone's favorite function. Compatibility promise will bite us later if we don't this properly now.

For example: What should be the signature of add with carry return? Add(x, y uint64) (c, s uint64)? Looking at math/big we probably need Add(x, y uintptr) (c, s uintptr) too.

[josharian]

The example looks like a bad inliner decision if rot is not inlined.

Yes. It is part of a bug complaining about inlining. :)

Did you try to write the function as func rot(x, n) instead of rot = func(x, n)?

It's not my code--and that's part of the point. And anyway, it is reasonable code.

[mundaym]

It would be nice to guarantee (in the package documentation?) that the rotate and byte-swap functions are constant-time operations so that they can be safely used in crypto algorithms. Possibly something to think about for other functions too.

[minux]

On Thu, Jan 19, 2017 at 11:50 AM, Michael Munday [e-mail]
wrote:

It would be nice to guarantee (in the package documentation?) that the
rotate and byte-swap functions are constant-time operations so that they
can be safely used in crypto algorithms. Possibly something to think about
for other functions too.

trivial implementation of byte swap is constant time, but if the underlying
architecture doesn't provide variable shift instructions, it will be hard
to guarantee constant time rotate implementation. Perhaps Go will never run
on those architectures though.

That said, there is also non-negligible chance that the underlying
microarchitecture uses a multi-cycle shifter, and we can't guarantee
constant time rotate on those implementations.

If strict constant time is required, perhaps the only way is write assembly
(and even in that case, it makes strong assumptions that all the used
instructions are itself constant time, which implicitly depends on the
microarchitecture.)

While I understand the need for such guarantees, but it's actually beyond
our control.

[randall77]

I'm inclined to agree with @minux. If you want constant-time crypto primitives, they should live in crypto/subtle. crypto/subtle can easily redirect to math/bits on platforms where those implementations have been verified. They can do something else if a slower but constant-time implementation is required.

[rsc]

This seems worth doing. Leaving for @griesemer and @randall77 to vet. The next step seems like a design doc checked into the usual place (I do see the sketch above).

[griesemer]

Now that this proposal can go forward, we should agree on the details of the API. Questions I see at the moment:

• which functions to include?
• which types to handle (uint64, uint32 only, or uint64, uint32, uint16, uint8, or uintptr)?
• signature details (e.g. TrailingZeroesxx(x uintxx) uint, with xx = 64, 32, etc., vs TrailingZeroes(x uint64, size uint) uint where size is one of 64, 32, etc. - the latter would lead to a smaller API and may still be fast enough dep. on implementation)
• some name bike shedding (I like the "Hacker's Delight" terminology but spelling it out may be more appropriate)
• is there a better place than math/bits for this package.

@brtzsnr Would you like to continue spearheading this effort? I'm ok if you want to take your initial design and iterate upon it in this issue or if you prefer setting up a dedicated design doc. Alternatively, I can pick this up and push it forward. I like to see this getting in during the 1.9 phase.

[jimmyfrasche]

I prefer the spelled out xx names, personally: bits.TrailingZeroes(uint64(x), 32) is more cumbersome and less readable than bits.TrailingZeroes32(x), imo, and that naming scheme would work with the platform-variable-sized uintptr more easily (xx = Ptr?).

It would also make it more apparent if you, say, didn't include uint8 in the first release but added it later—suddenly there'd be a lot of new xx = 8 functions instead of a bunch of updated doc comments that add 8 to the list of valid sizes with a note in the release docs that's easy to miss.

If the spelled out names are used, I think the Hacker's delight terms should be included in the descriptions as an "also known as" so that searches (in page or via search engine) find the canonical name easily if you search for the wrong spelling.

I think math/bits is a fine place—it's math with bits.

[dsnet]

I should note that SwapBytes{16,32,64} is more consistent with functions in sync/atomic than SwapBytes(..., bitSize uint).

Although the strconv package does use the ParseInt(..., bitSize int) pattern, there is more relation between bits and atomic, than there is with strconv.

[minux]

Three reasons I don't like SwapBytes(uint64, size uint):

1. people might use it in cases where size is not compile time constant (at
   least to the current compiler),
2. it necessitate a lot of type conversions. First to convert a uint32 to
   uint64, and then to convert it back.
3. we should reserve the generic name SwapBytes for a future generic
   version of the function (when Go gets generics support).

[brtzsnr]

@griesemer Robert, please take over the proposal. I will have time to push this proposal forward in one month, but progress should not stall till then.

[griesemer]

It looks like there's a clear preference for signatures of the form:

func fffNN(x uintNN) uint

which leaves open which NN to support. Let's focus on NN=64 for the purpose of the continuing discussion. It will be straight-forward to add the remaining types as needed (incl. uintptr).

Which leads us straight back to the original proposal by @brtzsnr and the following functions (and their respective variations for different types), plus what people have suggested in the meantime:

// LeadingZeros64 returns the number of leading zero bits in x.
// The result is 64 if x == 0.
func LeadingZeros64(x uint64) uint

// TrailingZeros64 returns the number of trailing zero bits in x.
// The result is 64 if x == 0.
func TrailingZeros64(x uint64) uint

// Ones64 returns the number of bits set in x.
func Ones64(x uint64) uint

// RotateLeft64 returns the value of x rotated left by n%64 bits.
func RotateLeft64(x uint64, n uint) uint64

// RotateRight64 returns the value of x rotated right by n%64 bits.
func RotateRight64(x uint64, n uint) uint64

We may have a set of Swap functions as well. Personally I am skeptical about these: 1) I've never needed a SwapBits, and most uses of SwapBytes are due to code that is endian-aware when it shouldn't be. Comments?

// SwapBits64 reverses the order of the bits in x.
func SwapBits64(x uint64) uint64

// SwapBytes64 reverses the order of the bytes in x.
func SwapBytes64(x uint64) uint64

Then there may be a set of integer operations. They would only be in this package because some of them (e.g. Log2) may be close to other functions in this package. These functions could be elsewhere. Perhaps the package name bits needs to be adjusted. Comments?

// Log2 returns the integer binary logarithm of x.
// The result is the integer n for which 2^n <= x < 2^(n+1).
// If x == 0, the result is -1.
func Log2(x uint64) int

// Sqrt returns the integer square root of x.
// The result is the value n such that n^2 <= x < (n+1)^2.
func Sqrt(x uint64) uint64

Finally, @minux suggested operations such as AddUint32 etc. I'm going to leave those out for now because I think they are more tricky to specify correctly (and there's more variety). We can get back to them later. Let's get to some consensus on the above.

Questions:

• Any opinions about function names?
• Any opinions about the integer ops?
• Any opinions about the package name/location?

[bradfitz]

I'd prefer long functions names. Go avoids abbreviating in function names. The comments can say their nicknames ("nlz", "ntz", etc) for people searching the package that way.

[dsnet]

@griesemer, you seem to have typos in your message. The comments don't match the function signatures.

I use SwapBits in compression applications. That said, do the major architectures provide any ability to do bit reversal efficiently? I was planning on just doing in my own code:

v := bits.SwapBytes64(v)
v = (v&0xaaaaaaaaaaaaaaaa)>>1 | (v&0x5555555555555555)<<1
v = (v&0xcccccccccccccccc)>>2 | (v&0x3333333333333333)<<2
v = (v&0xf0f0f0f0f0f0f0f0)>>4 | (v&0x0f0f0f0f0f0f0f0f)<<4

[griesemer]

@bradfitz , @dsnet : Updated signatures (fixed typos). Also updated questions (people prefer explicit names of shortcuts).

[dsnet]

Unless there's native support for bit-swapping, I would vote to leave out SwapBits. It can be a little ambiguous by name alone whether bits are only swapped within each byte, or across the entire uint64.

[minux]

Why exclude something based solely on instruction availability? Reverse bit
has notable uses in FFT.

To answer your question of reverse bit instruction availability: arm has
the RBIT instruction.

[jimmyfrasche]

@griesemer As far as the type signatures of functions like

func Ones64(x uint64) uint
func RotateLeft64(x uint64, n uint) uint64

Does RotateLeftN etc take uints because that's necessary for easy intrinisifying (when possible) or just because that's the domain? If there's not a strong technical need, there's a stronger precedent for taking ints, even if negative values don't make sense. If there is a strong technical need, should they be uintN for the appropriate N for regularity?

Regardless OnesN and its ilk should return ints unless it's so these operations can be composed with other bit operations in which case they should return a uintN for the appropriate N.

[griesemer]

@jimmyfrasche Because it's the domain. The cpu doesn't care. Whether somethings is an int or a uint is irrelevant for most operations except comparisons. That said, if we make it an int, we have to explain that it is never negative (result), or that it must not be negative (argument), or specify what it's supposed to do when it's negative (argument for rotation). We might be able to get away with just one Rotate in that case which would be nice.

I'm not convinced that using int makes things easier. If properly designed, uints will flow to uints (that's the case in math/big) and no conversions are needed. But even if a conversion is needed, it's going to be free in terms of CPU cost (though not in terms of readability).

But I'm happy to hear/see convincing arguments otherwise.

[minux]

The rotate bit count should be uint (with no specific size) to match the
shift operator of the language.

The reason for not using int is that there will be ambiguity whether
RotateRight -2 bits is equal to RotateLeft 2 bits.

[griesemer]

@minux There's no ambiguity when Rotate(x, n) is defined to rotate x by n mod 64 bits: Rotate left by 10 bits is the same as rotate right by 64-10 = 54 bits, or (if we allow int arguments) by -10 bits (assuming a positive value means rotate left). -10 mod 64 = 54. Most possibly we get the effect for free even with a CPU instruction. For instance, the 32bit x86 ROL/ROR instructions already only look at the bottom 5 bits of the CL register, effectively performing mod 32 for 32 bit rotates.

[jimmyfrasche]

The only real argument is regularity with the rest of the stdlib. There are numerous places where uints make a lot of sense but ints are used instead.

Since math/big is a notable exception, I don't have a problem with this being another, but it is something to consider.

I assume @minux meant ambiguity for someone reading/debugging code rather than ambiguity in the implementation, which is a persuasive argument for it taking uint.

[as]

Should bits.SwapBits really be named with a bits suffix when the name of the package is already called bits? How about bits.Swap?

Another idea is a bits.SwapN(v uint64, n int) rather than bits.SwapBytes where n represents the number of bits to group by for the swap. When n=1 the bits are reversed, when n=8, the bytes are swapped. One benefit is that bits.SwapBytes no longer has to exist, although I've never seen a necessity for any other value of n, maybe others will disagree.

[josharian]

As specified above, LeadingZeros64, TrailingZeros64, Ones64 all LGTM.

A single Rotate64 with a signed rotate amount is appealing. Most rotates will be by a constant amount, too, so (if/when this becomes an intrinsic) there'll be no runtime cost to not having separate Right/Left functions.

I have no strong opinion about bit/byte shuffling/swapping/reversing. For reversing bits, bits.Reverse64 seems like a better name. And perhaps bits.ReverseBytes64? I find Swap64 a bit unclear. I see the appeal of having Swap64 take a group size, but what is the behavior when the group size doesn't evenly divide 64? If the only group sizes that matter are 1 and 8, it'd be simpler to just give them separate functions. I also wonder whether some kind of general bit field manipulation might be better, maybe looking at arm64 and amd64 BMI2 instructions for inspiration.

I'm not convinced that integer math functions belong in this package. They seem more like they belong in package math, where they could use bits functions in their implementation. Related, why not func Sqrt(x uint64) uint32 (instead of returning uint64)?

Though AddUint32 and friends are complicated, I hope we do revisit them eventually. Along other things, MulUint64 would provide access to HMUL, which even the super-minimalist RISC-V ISA provides as an instruction. But yes, let's get something in first; we can always expand later.

bits seems clearly like the right package name. I'm tempted to say the import path should be just bits, not math/bits, but I don't feel strongly.

[dsnet]

bits seems clearly like the right package name. I'm tempted to say the import path should be just bits, not math/bits, but I don't feel strongly.

IMO, if it were just bits, (without reading the package docs) I would expect it to be somewhat similar to package bytes. That is, in addition to functions to operate on bits, I would expect to find a Reader and Writer for reading and writing bits to/from a byte stream. Making it math/bits makes it more obvious its just a set of stateless functions.

(I'm not proposing that we add Reader/Writer for bit streams)

[mdlayher]

A single Rotate64 with a signed rotate amount is appealing. Most rotates will be by a constant amount, too, so (if/when this becomes an intrinsic) there'll be no runtime cost to not having separate Right/Left functions.

I can see how it could be convenient to have a slightly smaller package API by combining rotate left/right into a single Rotate, but then there is also the matter of effectively documenting the n parameter to indicate that:

• negative n results in a left rotate
• zero n results in no change
• positive n results in a right rotate

To me, the added mental and documentation overhead doesn't seem to justify combining the two into a single Rotate. Having an explicit RotateLeft and RotateRight where n is a uint feels more intuitive to me.

[griesemer]

@mdlayher Keep in mind that for an n-bit word rotating by k bits to the left is the same as rotating n-k bits to the right. Even if you separate this in two functions you still need to understand that rotating by k bits to the left always means rotating by (k mod n) bits (if you rotate by more than n bits, you start again). Once you do that, you can just say that the rotate function always rotates by k mod n bits and you're done. There's no need to explain the negative value or a second function. It just works out. It is actually simpler.

On top of that, hardware (eg on x86) even does this for you automatically, even for non-constant k.

[aclements]

@griesemer, a downside of Rotate is that it doesn't say which direction is positive. Does Rotate32(1, 1) equal 2 or 0x80000000? For example, if I were reading code that used that, I would expect the result to be 2, but apparently @mdlayher would expect it to be 0x80000000. On the other hand, RotateLeft and RotateRight are unambiguous names, independent of whether they take a signed or unsigned argument. (I disagree with @minux that it's ambiguous whether RotateRight by -2 is equal to RotateLeft 2. These seem obviously equivalent to me and I don't see how else you could specify them.)

[josharian]

@aclements that could be fixed by having just one function called RotateLeft64 and using negative values to rotate right. Or with docs. (FWIW, in your example, I would also expect 2, not 0x800000000.)

[aclements]

@josharian, I agree, though it seems a bit odd to have a RotateLeft without also having a RotateRight. The consistency of having a signed rotation seems potentially valuable if the rotation is computed, but for constant rotations I'd much rather read code that says "rotate right by two bits" than "rotate left by just kidding negative two bits".

The problem with fixing this with docs is that docs don't help the readability of code that calls the function.

[ianlancetaylor]

People writing code want to rotate left or rotate right. They don't want to rotate either left or right, depending. If we only provide rotate-left, then anybody who wants to rotate right has to write an expression to convert their right rotation into a left rotation. This is the kind of expression that computers can do trivially but programmers will make mistakes on. Why make programmers write it themselves?

[josharian]

I'm convinced.

[griesemer]

@aclements @ianlancetaylor Point taken. (That said, the implementation of RotateLeft/Right will probably just call one implementation of rotate.)

[btracey]

A name idea is to put the type in the package name rather than the signature name. bits64.Ones rather than bits.Ones64.

[bradfitz]

@btracey, I threw up in my mouth a little bit there. :) We don't have flag64.Int or math64.Floatfrombits or sort64.Floats or atomic64.StoreInt.

[iand]

@bradfitz golang.org/x/image/math/f64 and golang.org/x/image/math/f32 exist though

[btracey]

I hadn't thought about atomic as a precedent (not in my normal Go usage, thankfully). The other examples are different because the packages are bigger than a set of functions repeated for a number of different types.

The documentation is easier to look at (say, on godoc), when you go to bits64 and see
Ones LeadingZeros TrailingZeros

Instead of going to bits and seeing
Ones8 Ones16 Ones32 Ones64 LeadingZeros8 ...

[bradfitz]

@iand, that's also pretty gross. I guess the 32 and 64 didn't look nice to all the existing numeric suffixes for Aff, Mat, and Vec. Still, I'd say that's an exception rather than the normal Go style.

[griesemer]

There's pretty strong precedent in Go to use the pkg.foo64 naming style rather than pkg64.foo .

The package API does get n times bigger if we have n types, but the API complexity does not. A better approach to solve this might be through documentation and how the API is presented via a tool such as go doc. For instance, instead of:

// TrailingZeros16 returns the number of trailing zero bits in x.
// The result is 16 if x == 0.
func TrailingZeros16(x uint16) uint

// TrailingZeros32 returns the number of trailing zero bits in x.
// The result is 32 if x == 0.
func TrailingZeros32(x uint32) uint

// TrailingZeros64 returns the number of trailing zero bits in x.
// The result is 64 if x == 0.
func TrailingZeros64(x uint64) uint

which clearly adds mental overhead when looking at the API, we could present it as:

// TrailingZerosN returns the number of trailing zero bits in a uintN value x for N = 16, 32, 64.
// The result is N if x == 0.
func TrailingZeros16(x uint16) uint
func TrailingZeros32(x uint32) uint
func TrailingZeros64(x uint64) uint

godoc could be smart about functions that are similar in that sense and present them as a group with a single doc string. This would be helpful in other packages as well.

To summarize, I think the proposed naming scheme seems fine and in the Go tradition. The presentation issue is a separate question that can be discussed elsewhere.

[rogpeppe]

+1 on putting the bit size in the package name.

bits64.Log2 reads better than bits.Log264 (I feel Log2 does belong there - and package naming isn't a good reason for keeping it out)

In the end, it's the same API for each type "parameterised" by scalar type, so if the functions have the same name across types, the code is easier to refactor with separate packages - just change the import path (whole-word replacements are trivial with gofmt -r but custom suffix transformations are more awkward).

I agree with @griesmeyer that the bitsize suffix on the function name can be idiomatic, but I feel that's worth it only if there's non-trivial code in the package that's independent of the type.

[nerdatmath]

We could steal a play from encoding/binary, and create vars named Uint64, Uint32, ... that would have methods accepting the associated predefined types.

bits.Uint64.RightShift
bits.Uint8.Reverse
bits.Uintptr.Log2
...

[jimmyfrasche]

@griesemer how would it know how to group them? One doc string with the function name ending in N in the documentation instead of the actual name and then finding a common prefix among funcs without docstrings that matches the incongruity? How does that generalize? It seems like a complicated special case to serve very few packages.

@rogpeppe it could be bits.Log64 and the docs say it was base 2 (what else would it be in a bits package?) Though as messy as having of 8/16/32/64/ptr packages are on one level it does make them each cleaner individually. (Also it looks like your transmission got cut off midsentence.)

@nerdatmath this would be slightly different since they would have the same interface in the colloquial sense but not in the Go sense, as is the case in encoding/binary (they both implement binary.ByteOrder), so the variables would just be for namespacing and godoc wouldn't pick up any of the methods (#7823) unless the types were exported, which is messy in a different way.

I'm fine with the size suffixes, but, all in all, I would prefer the separate packages. Not enough to bother pushing it past this comment, though.

[josharian]

@nerdatmath if they are vars, then they are mutable (you could do bits.Uint64 = bits.Uint8), which would prevent the compiler from treating them as intrinsics, which was one of the motivations for (at least part of) the package.

[bradfitz]

Variables aren't really mutable if they're of an unexported type and have no state (unexported empty struct). But without a common interface the godoc (today) would be gross. Fixable though if that's the answer.

If y'all do end up going with multiple packages, though, if there's enough repetition and volume to warrant it, at least maybe name the packages like "X/bits/int64s", "X/bits/ints", "X/bits/int32s" to match "errors", "strings", "bytes". Still seems like a lot of package explosion.

[ulikunitz]

I don't think we should go the path to multiple type-specific packages, having a single package bits is simple and doesn't inflate the number of packages in the Go library.

I don't think that Ones64 and TrailingZeroes64 are good names. They don't inform that they return a count. Adding the prefix Count makes the names even longer. In my programs those functions are often embedded in larger expressions, so short function names will increase readability. Though I used the names from the book "Hacker's Delight" I suggest to follow the Intel assembler mnemonics: Popcnt64, Tzcnt64 and Lzcnt64. The names are short, follow a consistent pattern, inform that a count is returned and are already established.

Usually counts in Go are returned as ints, even when a count can never be negative. The prime example is the builtin function len, but Read, Write, Printf, etc. all return integers as well. I find the use of uint value for a count as quite surprising and suggest to return an int value.

[jimmyfrasche]

If the choice is between (to abuse notation) math/bits/int64s.Ones and math/bits.Ones64, then I'd definitely prefer a single package. It's more important to have bits in the package identifier than to partition by size. Having bits in the package identifier makes reading the code easier, which is more important than the minor inconvenience of repetition in the package's documentation.

@ulikunitz You can always do ctz := bits.TrailingZeroes64, and the like, in code that uses bits extensively. That strikes a balance between having globally self-documenting names and locally compact names for complex code. The opposite transformation, countTrailingZeroes := bits.Ctz64, is less useful since the nice global properties are already lost.

I mess with stuff at the bit level very rarely. I have to look a lot of this stuff up each time, just because it's been years since I had to think about it, so I find all the Hacker's Delight/asm-style names infuriatingly cryptic. I'd rather it just said what it did so I can spot the one I need and get back to programming.

[as]

I agree with @ulikunitz the long names are an eye sore. The first time you see bits.TrailingZeroes64, it might be self documenting. Every subsequent time, it's annoying. I can see why people would do ctz := bits.TrailingZeroes64, but I think a name that needs to be assigned to a shorter name is a bad name. There are places where Go abbreviates, for example,

init() instead of initialize(), 
func instead of function
os instead of operatingsystem
proc instead of process
chan instead of channel

Additionally, I would challenge that bits.TrailingZeroes64 is self documenting. What does it mean for a zero to be trailing? The self documentation property exists with an assumption that the user knows something about the semantics of the documentation to begin with. If not using Hacker's Delight for consistency, why not just call it ZeroesRight64 and ZeroesLeft64 to match RotateRight64 and RotateLeft64?

[jimmyfrasche]

To clarify, I didn't mean to imply that any time you use it the first thing you should do is create a short alias and you should never use the given name. I meant if you're using it repeatedly, you could alias it, if that improves the readability of the code.

For example, if I'm calling strings.HasSuffix I use the given name most of the time because I'm calling it once or twice, but, every now and then, in a one-off ETL script or the like I'll end up calling it a bunch so I'll do ends := strings.HasSuffix which is shorter and makes the code clearer. It's fine because the definition of the alias is close at hand.

Abbreviated names are fine for things that are extremely common. Plenty of non-programmers know what OS means. Anyone reading code, even if they don't know Go, is going to get that func is short for function. Channels are fundamental to Go and widely used, so chan is fine. The bits functions are never going to be extremely common.

TrailingZeroes may not be able to tell you exactly what's going on if you're unfamiliar with the concept but it gives you a much better idea of what's going on, at least roughly, than Ctz.

[griesemer]

@jimmyfrasche Regarding https://github.com/golang/go/issues/18616#issuecomment-275828661: It would be pretty easy for go/doc to recognize a contiguous sequence of functions in the same file that have names that all start with the same prefix and have a suffix that is just a sequence of numbers and/or perhaps a word that is "short" relative to the prefix. I'd combine it with the fact that only the first of these functions has a doc string and the other with matching prefix don't. I think that could work quite well in more general settings. That said, let's discuss this elsewhere to not hijack this proposal.

[mdlayher]

FYI, created #18858 to discuss the go/doc changes and keep that conversation separate from this one.

[griesemer]

@mdlayher thanks for doing that.

[griesemer]

@rogpeppe Putting the size into the package name sounds intriguing, but judging from the comments and given existing Go style, I think the preference is to put the size with the function name. With respect to Log2, I'd say, let's leave the 2 away. (Also, please repeat if there was anything else you wanted to add, your comments appears cut off mid-sentence.)

@ulikunitz I'm usually one of the first to vote for short names; especially in local context (and in global context for extremely frequently used names). But here we have a package API, and (at least in my experience) the functions will not show up pervasively in clients. For instance, math/big makes uses LeadingZeros, Log2, etc. but it's just one or two calls. I think a longer descriptive name is ok, and judging from the discussion, a majority of comments is in favor of that. If you call a function frequently, it's cheap to wrap it inside a function with short name. The additional call will be inlined away. FWIW, the Intel mnemonics are not great either, their emphasis is on "count" (cnt) and then you are left with 2 letters which need to be decrypted.

[randall77]

I agree that the 2 in Log2 isn't necessary. bits.Log implies a base of 2.

[rogpeppe]

bits.Log64 SGTM.

@griesemer My cut-off sentence was probably an artifact of clumsy editing. I just removed it.

[ulikunitz]

@griesemer I wonder whether it is worth to continue the name bike shedding. I keep it short: I had two arguments: shortness and clarity about returning a number. Package big uses nlz, not LeadingZeros, internally. I agree the number of uses for these functions is small.

[griesemer]

@ulikunitz I think the majority of feedback here is in favor for clear function names that are not shortcuts.

[bradfitz]

@ulikunitz, additionally:

Package big uses nlz, not LeadingZeros, internally.

Internal private unexported names have no influence here.

All that matters is consistency and standard feel of the public API.

Bikeshedding might be annoying but names matter when we're stuck with them forever.

[gopherbot]

CL https://golang.org/cl/36315 mentions this issue.

[griesemer]

I've uploaded https://go-review.googlesource.com/#/c/36315/ as an initial (partially tested) API (with preliminary implementation) for review (in lieu of a design document).

We're still making sure the API is correct, so please comment only on the API (bits.go) for now. For minor issues (typos, etc.) please comment on the CL. For design issues, please comment on this issue. I will keep updating the CL until we're happy with the interface.

Specifically, don't worry about the implementation. It is basic, and only partially tested. Once we're happy with the API it will be easy to expand on the implementation.

[ericlagergren]

@griesemer I'm sure you're fine, but if it's useful, I've a CLZ assembly implementation with tests https://github.com/ericlagergren/decimal/tree/ba42df4f517084ca27f8017acfaeb69629a090fb/internal/arith that you're free to steal/fiddle with/whatever.

[griesemer]

@ericlagergren Thanks for the link. Once the API has settled and we have tests in place everywhere, we can start optimizing the implementation. I'll keep this in mind. Thanks.

[mdlayher]

@griesemer, it looks like your proposed API documentation depends on go/doc being able to adequately document functions with the same prefix but an integer suffix.

Would the plan be to work on that before 1.9 as well?

[mdlayher]

18858, that is!

[griesemer]

@mdlayher That would be ideal. But it wouldn't be a showstopper since it affects "only" documentation, not the API (which must remain backward-compatible going forward).

[ulikunitz]

@griesemer @bradfitz I spend some time to rethink my position regarding the function names. An important objective of choosing names must be Readability of the code using the API.

The following code is indeed easy to understand:

n := bits.LeadingZeros64(x)

I'm still a little bit in doubt about the clarity of Ones64(x), but it is consistent with LeadingZeros and TrailingZeros. So I rest my case and support the current proposal. As an experiment I used my existing code for an experimental pure Go implementation of the package including test cases.

Repository: https://github.com/ulikunitz/bits
Documentation: https://godoc.org/github.com/ulikunitz/bits

[mundaym]

We may have a set of Swap functions as well [...] most uses of SwapBytes are due to code that is endian-aware when it shouldn't be. Comments?

I'd like to keep SwapBytes out of the API for this reason. I worry that people will start to use it in non-portable ways because it is simpler (or assumed to be faster) than binary/encoding.BigEndian.

[ericlagergren]

I'd like to keep SwapBytes out of the API for this reason. I worry that people will start to use it in non-portable ways because it is simpler (or assumed to be faster) than binary/encoding.BigEndian.

@mundaym are these routines are ever going to be intrinsified? Letting SwapBytes64 compile directly as BSWAP might outweigh people using it improperly, imo.

[dsnet]

I worry that people will start to use it in non-portable ways because it is simpler (or assumed to be faster) than binary/encoding.BigEndian

I believe use of ReverseBytesis only non-portable if used in conjunction with unsafe where you access data at the low-level in the way the machine lays them out in memory. However, use of encoding.{Little,Big}Endian.X is just as non-portable when used in that way. I look forward to ReverseBytes for use in compression and would be sad if it were not included.

[mundaym]

@ericlagergren

are these routines are ever going to be intrinsified?

Yes, the functions in encoding/binary that perform byte reversals use code patterns that are recognized by the compiler and are (or could be) optimized to single instructions (e.g. BSWAP) on platforms that support unaligned data accesses (e.g. 386, amd64, s390x, ppc64le and probably others).

Letting SwapBytes64 compile directly as BSWAP might outweigh people using it improperly, imo.

I'm inclined to disagree. There may be legitimate uses of SwapBytes in endianness-unaware code, but I suspect it will be misused more often than it is used correctly.

[aclements]

Note that runtime/internal/sys already has optimized Go, assembly, and compiler intrinsic versions of trailing zeros and byte swap, so we can reuse those implementations.

[mundaym]

@dsnet Interesting, do you have something specific in mind?

@aclements Do you know where the byte swap intrinsic is used in the runtime? I haven't found any uses outside of the tests.

[aclements]

@mundaym, AFAIK it's not used in the runtime. We don't have to be as careful with internal APIs, so I think we just added it when adding ctz because it was easy. :) (Popcount would have been a better choice.)

[griesemer]

All: Just a reminder to please concentrate on the API for now. The implementation in the CL is simply a trivial and slow implementation that allows us to actually use these functions and test them. Once we are happy with the API we can tune the implementation.

On that note: We probably should include versions for uintptr since it's not guaranteed (though likely) that it's the same size as an uint32 or uint64. (Note that uint is always either uint32 or uint64). Opinions? Leave it for later? What would be good names? (LeadingZerosPtr?).

[josharian]

We should do uintptr now, otherwise math/big can't use it. Suffix Ptr SGTM. I think we should also do uint as well, otherwise all calling code needs to write conditional code around int size to make the conversion-free call. No naming ideas.

[jimmyfrasche]

Ptr for uintptr, no suffix for uint. Ones, Ones8, Ones16, Ones32, Ones64, OnesPtr, etc.

[minux]

I might a minority here, but I'm against adding functions that take uintptr.
math/big should have used uint32/uint64 from the beginning. (In fact, I'd
just use uint64 for all architectures and leave the optimization to the
compiler.)

The problem is this:
math/big wants to use the native word size for optimal performance,
however, while close, uintptr is not the correct choice.
there is no guarantee that the size of a pointer is the same size as the
native word size.
The prime example is amd64p32, and we might also add mips64p32 and
mips64p32le later, which are much more popular for 64-bit MIPS hosts.

I certainly don't want to encourage more of such usages. uintptr is most
for pointers, not for architecture neutral integers.

One solution, however, is to introduce a type alias in the API (perhaps it
should be branded type, this is up for discussion).
type Word = uint32 // or uint64 on 64-bit architectures
// we probably also need to provide a few ideal constants for Word like
number of bits, mask, etc.

And then introduce functions without any type prefix to take Word.

In fact, I imagine that if math/bit provides the two result add, sub, mul,
div; math/big can be rewritten without any architecture specific assembly.

[josharian]

math/big exports type Word uintptr. I agree that it might have been a mistake, but I believe that compatibility requires that that remain. So if we want to use math/bits to implement math/big, which I think we do, we need uintptr APIs.

Wandering a bit off topic, but isn't the native unsigned word size just uint? In which case, having no suffix for uint seems about right.

I wouldn't want a single type, Word, to be different on different architectures. That seems like introducing lots of complexity for the caller and the docs. Sticking to existing types means you can simply use it. Having a type that varies across architectures means designing all your code around that type or having a bunch of adapters in build-tag protected files.

[griesemer]

FWIW, the implementation of math/big could still use a uint32/64 based bits API (if there was no uintptr version of the functions).

@minux I'm not against the 2-result add,sub,mul,div - but let's do that in a 2nd step. We still need assembly code if we want decent performance though. But I'm happy to be convinced otherwise by the compiler...

I've added the uint and uintptr versions to the API. Have a look at the CL and comment. I'm not too happy with the proliferation of functions, though.

@josharian The native uint may be a 32bit value even on a 64bit machine. There's no guarantee. I do realize that uintptr doesn't guarantee machine word size either; but at the time it seemed the more sensible choice, if wrong in retrospect. Perhaps we really do need a Word type.

[jimmyfrasche]

If the only legitimate need for the uintptr functions is to support math/big, maybe the implementation of math/bits could go in an internal package: only use the uintptr stuff in math/big and expose the rest.

[ericlagergren]

@jimmyfrasche, @griesemer how would that affect big.Int.Bits? i.e. will it still be zero-alloc?

[minux]

uint is also wrong. it's 32-bit on amd64p32.
Actually, math/big could have used uint instead of uintptr, but at Go 1,
int/uint are always 32-bit, which makes uintptr the only possible solution
for math/big.Word.

We're designing a new package, so I don't believe compatibility is of much
concern. math/big is using the wrong type, but that's more of a historical
accident. Let's not take the mistake further.

I don't understand why using a unified type "Word" that is always the most
efficient integer type for a given architecture is more complicated than
using uintptr. For the user code, you can treat it as a magic type that is
either 32-bit or 64-bit, depending on the architecture. If you can write
your code using uintptr (whose width is also architecture dependent) in an
architecture independent way, then I believe you can do the same with Word.
And Word are correct on all architectures.

For the proliferation of the API, I suggest we leave out functions for 8
and 16-bit types in the first pass. They're rarely used and most
architecture will only provide 32-bit and 64-bit instructions anyway.

[griesemer]

math/big defines and exports Word, but it's a) not directly compatible with uintptr (it's a different type), and b) code that properly uses Word and doesn't make assumptions about its implementations will be able with any kind of Word implementation. We can change it. I don't see why it should affect the API compatibility guarantee (haven't tried though). Anyway, let's leave this aside. We can handle that separately.

Can we simply do all the explicitly sized uint types? If we know the uint/uintptr size as a constant, we can trivially write an if-statement that calls the right sized function. That if statement will be constant-folded away, and the respective wrapper function simply calls the sized function which will be inlined.

Finally, what's the right solution regarding the Word type (independent of math/big)? Of course we could define it in math/bits but is that the right place? It's a platform-specific type. Should it be a predeclared type 'word' ? And why not?

[rsc]

Having any function signatures (or names) here that mention uintptr directly seems like a mistake. People are not supposed to do this kind of bit twiddling on Go pointers.

If there should be functions for a natural machine word type, I think those can refer to int/uint now. We didn't use uint in math/big because it was 32 bits on 64-bit systems, but we've since fixed that. And while math/big is a coherent world unto itself, where it makes sense to have its own type big.Word, this package is more a collection of pick-and-choose utility routines. Defining a new type in this context is less compelling.

I don't know whether we need int/uint variants at all. If they are commonly needed, defining them in this package makes more sense than forcing all callers to write if statements. But I don't know if they will be commonly needed.

[rsc]

To address the potential mismatch with math/big, there are at least two solutions that don't involve mentioning uintptr in the API here.

1. Define files word32.go and word64.go in math/big with build tags and uintptr-accepting wrappers that redirect appropriately (and make sure the compiler inlining does the right thing).

2. Change the definition of big.Word to uint. The exact definition is an internal implementation detail, even though it is exposed in the API. Changing it can't break any code except on amd64p32, and even there it seems very unlikely to matter outside math/big.

[griesemer]

@rsc: "We didn't use uint in math/big because it was 32 bits on 64-bit systems, but we've since fixed that. " Ah yes, I completely forgot about the reason for the choice of uintptr. The whole point of the Go uint/int types was to have integer types that reflected the natural register size of a machine. I will try changing big.Word to uint and see what happens.

[griesemer]

All: Updated https://go-review.googlesource.com/#/c/36315/ to exclude uintptr function versions per above discussion.

[griesemer]

I've tentatively updated math/big to use math/bits to see the effect (https://go-review.googlesource.com/36328).

A few comments:
1) I'm leaning towards making the results of the Leading/TrailingZeros functions uint rather than int. These results tend to be used to shift a value accordingly; and math/big evidences this. I'm also in favor of making Ones return a uint, for consistency. Counter arguments?

2) I'm not a fan of the name One, however consistent with Leading/TrailingZeros. How about Population?

3) Some people have complained that Log doesn't fit into this package. Log happens to be equivalent to the index of the msb (with -1 for x == 0). So we could call it MsbIndex (though Log seems nicer). Alternatively, we could have a Len function which is the length of an x in bits; i.e., `Log(x) == Len(x)-1).

Comments?

[ericlagergren]

I'm not a fan of the name One, however consistent with Leading/TrailingZeros. How about Population?

Why not the traditional Popcount?

Alternatively, we could have a Len function which is the length of an x in bits; i.e., `Log(x) == Len(x)-1).

Len or Length sounds like a good name and good idea.

[aclements]

1.

I'm not a fan of the name One, however consistent with Leading/
TrailingZeros. How about Population?

bits.Count?

[jimmyfrasche]

@aclements Count what?

Population may be the better name for historical reasons but it doesn't really say more than Ones if you're not familiar with the term and has the same problem is just Count: Population of what?

It's somewhat unidiomatic, even within the package, but maybe CountOnes to give it a clear, obvious name.

[aclements]

@aclements Count what?

In a package called "bits", I'm not sure what else you could be counting except set bits, but CountOnes is also fine and obviously more explicit. Adding "Ones" also parallels the "Zeros" in LeadingZeros/TrailingZeros.

[jimmyfrasche]

That's the most obvious interpretation but there's still ambiguity. It could be counting unset bits or total bits (the last interpretation would be extremely unlikely, but still a potential trap for someone reading code using bits who's unfamiliar with the concepts involved and might think the suffix-free Count is like unsafe.SizeOf)

Maybe something like AllOnes or TotalOnes to mirror Trailing/LeadingZeroes but specify that, unlike those, the position is not taken into account.

[rsc]

AllOnes sounds like it returns all the ones (in a bitmask maybe?), or maybe a word that is all ones.

CountOnes and TotalOnes seem about the same, but since this operation's most commonly known name is "population count", CountOnes seems like it would be preferable.

[griesemer]

I've uploaded a new version (https://go-review.googlesource.com/#/c/36315/) with a couple of changes:

1) I renamed Ones to PopCount: Most people were not too excited about the consistent but somewhat drab name Ones. Everybody who is going to use this package will know exactly what PopCount does: it's the name by which this function is commonly known. It's slightly inconsistent with the rest but it's meaning has become so much clearer. I'm going with Ralph Waldo Emerson on this one ("A foolish consistency is the hobgoblin of little minds...").

2) I renamed Log to Len as in bits.Len. The bit length of a number x is the number of bits it takes to represent x in binary representation (https://en.wikipedia.org/wiki/Bit-length). Seems fitting, and removes the need to have Log here which has a non-"bit-fiddly" quality. I believe this is also a win because Len(x) == Log(x) + 1 given how we had Log defined. It furthermore has the advantage that the result now is always >= 0, and it removes some +/-1 corrections in the (trivial) implementation.

Overall I'm pretty happy with this API at this point (we may want to add more functions later). The only other thing I think we might want to seriously consider is whether all results should be unsigned. As I have pointed out before, the Trailing/Leading Zero function results tend to be inputs to shift operations which must be unsigned. That only leaves Len and PopCount which arguably could return unsigned values as well.

Comments?

[rsc]

My experience with math/big has been frustration at being forced into uint mode by functions when I'm not shifting. In math/big/prime.go, I wrote

for i := int(s.bitLen()); i >= 0; i-- {

even though s.bitLen() returns int not uint, because I was unsure without looking, and was I also unsure that some future CL might not change it to return uint, thereby turning that for loop into an infinite loop. Needing to be this defensive suggests there is a problem.

Uints are much more error-prone than ints, which is why we discourage them in most APIs. I think it would be much nicer if every function in math/bits returned int and left the conversion to uint to be done in the shift expression, as is necessary in most shift expressions anyway.

(I'm not proposing a change, but I think shift requiring uint may have been a mistake in retrospect. Maybe we can fix it at some point. It would be nice if it didn't hurt our other APIs.)

[ulikunitz]

I'm in support of returning int after grepping my code for calls of the trailing zeros and popcount functions. The majority of calls are in short variable declarations and comparisons of type int. Calls in shifts require of course the uint type, but are surprisingly rare.

[griesemer]

Uploaded minor tweaks. Per +1's and comments let's leave the results of counts as int.

https://go-review.googlesource.com/36315

I left the input counts for RotateLeft/Right as uint otherwise we will need specify what happens when the value is negative or disallow it.

Finally, we might even leave away Len after all since LenN(x) == N - LeadingZerosN(x). Opinions?

If there's no significant feedback anymore at this point, I'd suggest we move forward with this API and commit an initial implementation after review. After that we can start tweaking the implementation.

I a next step we may want to discuss if and which other functions we might want to include, specifically Add/Sub/ etc. that consume 2 arguments and carry, and produce a result and carry.

[ericlagergren]

@gri thoughts on a base 10 Len function? It'd just be ((N - clz(x) + 1) * 1233) >> 12

It's less "bit hacky" than base 2 but still useful.
On Fri, Feb 10, 2017 at 5:03 PM Robert Griesemer [e-mail]
wrote:

Uploaded minor tweaks. Per +1's and comments let's leave the results of
counts as int.

https://go-review.googlesource.com/36315

I left the input counts for RotateLeft/Right as uint otherwise we will
need specify what happens when the value is negative or disallow it.

Finally, we might even leave away Len after all since LenN(x) == N -
LeadingZerosN(x). Opinions?

If there's no significant feedback anymore at this point, I'd suggest we
move forward with this API and commit an initial implementation after
review. After that we can start tweaking the implementation.

I a next step we may want to discuss if and which other functions we might
want to include, specifically Add/Sub/ etc. that consume 2 arguments and
carry, and produce a result and carry.

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/golang/go/issues/18616#issuecomment-279107013, or mute
the thread
https://github.com/notifications/unsubscribe-auth/AFnwZ_QMhMtBZ_mzQAb7XZDucXrpliSYks5rbQjCgaJpZM4Lg5zU
.

[ericlagergren]

Also. Pardon me if I'm getting out of scope of this issue but I'd be in favor of checked arithmetic. Eg AddN(x, y T) (sum T, overflow bool)

[minux]

On Fri, Feb 10, 2017 at 8:16 PM, Eric Lagergren [e-mail]
wrote:

Also. Pardon me if I'm getting out of scope of this issue but I'd be in
favor of checked arithmetic. Eg AddN(x, y T) (sum T, overflow bool)

Are you talking about signed overflow? or unsigned overflow (carry/borrow)?

Also, I prefer to return overflow/carry/borrow as type T, to simplify
multi-precision arithmetic.

[griesemer]

@ericlagergren The (base 2) Len function, while almost log2, is still in essence a bit counting function. A base 10 Len function is really a log function. There's no denying that it's useful, but it seems less appropriate for this package.

Yes, I think it would be nice to get checked arithmetic in. I just wanted to get closure on the current API first so we can make progress instead of going back and forth. It does seem most people who commented so far seem happy with it.

Regarding the Add, Sub functions: I agree with @minux that the carry should be of the same type as the argument. Also, I'm not convinced that we need anything else besides uint arguments for these functions: The point is that (in most cases) uint has the platform's natural register size, and that's the level at which these operations make the most sense.

[jimmyfrasche]

A math/checked package could be a better home for those. checked.Add is clearer than bits.Add.

[ericlagergren]

@minux I was thinking signed checked arithmetic, so overflow.

@griesemer re: base 10 Len: makes sense!

If you want I can submit a CL for checked arithmetic. I like @jimmyfrasche's idea of having it be under a separate package name.

[aclements]

Add/sub/mul may or may not belong in bits, but checked math isn't the only use for these operations. More generally, I would say these are "wide" arithmetic operations. For add/sub there's little difference between the one bit of carry/overflow result and a boolean indicator of overflow, but we would probably also want to provide add-with-carry and subtract-with-borrow to make these chainable. And for wide mul there's far more information in the additional result than overflow.

[rsc]

It's a good idea to remember the checked/wide arithmetic operations, but let's leave them for round two.

[rogpeppe]

"Everybody who is going to use this package will know exactly what PopCount does"

I've used that functionality before and somehow I wasn't familiar with the PopCount name (although I should have because I'm sure I pinched the implementation off Hacker's Delight, which uses "pop").

I know I'm to the party, but "OnesCount" seems considerably more obvious to me, and if the word "PopCount" is mentioned in the doc comment, people looking for that will find it anyway.

[josharian]

Related for checked/wide arithmetic: #6815. But yes, let's get round one in!

[seh]

@griesemer wrote:

The (base 2) Len function, while almost log2, is still in essence a bit counting function. A base 10 Len function is really a log function. There's no denying that it's useful, but it seems less appropriate for this package.

I wrote a benchmark to compare a few approaches to the "decimal digit length" problem last October, which I posted in a gist.

[rsc]

Accepted as a proposal; there will probably be minor tweaks moving forward, and that's fine.

[griesemer]

@rogpeppe: Changed PopCount to OnesCount as it also received 4 thumbs-up (like my suggestion to use PopCount). Referred to "population count" in doc string.

Per @rsc, leaving checked/wide arithmetic operations out for now.

Also per @rsc, all counting functions return int values, and for ease of use (and with an eye on #19113), use int values for rotation counts.

Left LenN functions in even though they are simply N - LeadingZerosN. But a similar symmetry exists for RotateLeft/Right and we have both.

Added slightly faster implementation for TrailingZeroes and completed tests.

At this point I believe we have a usable first implementation. Please review the code at https://go-review.googlesource.com/36315, especially the API. I like to get this submitted if we're all happy.

Next steps:

• faster implementation (primary)
• adding additional functionality (secondary)

[TuomLarsen]

We're designing a new package

@minux You mean new math/big? Is it possible to follow the process somewhere?

[griesemer]

@TuomLarsen: @minux referred to math/bits with "new package". He mentioned math/big as a case where math/bits would be used. (In the future, please be more specific with your comments so we don't have to search and guess what you are referring to - thanks).

[gopherbot]

CL https://golang.org/cl/37140 mentions this issue.

[cespare]

Will there be any compiler-assisted intrinsification happening in math/bits for Go 1.9?

[griesemer]

@cespare Depends on whether we get to it (@khr?). Independent of that, we want to have a decent platform-independent implementation. (One of the reasons we don't want to move math/big entirely over to using math/bits is that currently we have some platform-specific assembly in math/big which is faster.)

[randall77]

On my plate, at least for the archs we already do intrinsics for
(386,amd64,arm,arm64,s390x,mips, probably ppc64).

On Fri, Feb 17, 2017 at 12:54 PM, Robert Griesemer <[email protected]

wrote:

@cespare https://github.com/cespare Depends on whether we get to it (
@khr https://github.com/khr?). Independent of that, we want to have a
decent platform-independent implementation. (One of the reasons we don't
want to move math/big entirely over to using math/bits is that currently we
have some platform-specific assembly in math/big which is faster.)

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/golang/go/issues/18616#issuecomment-280763679, or mute
the thread
https://github.com/notifications/unsubscribe-auth/AGkgIIb8v1X5Cr-ljDgf8tQtT4Dg2MGiks5rdgkegaJpZM4Lg5zU
.

[zephyr]

This article about the fastest way to implement population count on x86-64 may be helpful: Hand coded assembly beats intrinsics in speed and simplicity – Dan Luu, Oct 2014

[gopherbot]

CL https://golang.org/cl/38155 mentions this issue.

[gopherbot]

CL https://golang.org/cl/38166 mentions this issue.

[gopherbot]

CL https://golang.org/cl/38311 mentions this issue.

[gopherbot]

CL https://golang.org/cl/38320 mentions this issue.

[gopherbot]

CL https://golang.org/cl/38323 mentions this issue.

[randall77]

Some more discussion:

Me:

math/bits.RotateLeft is currently defined to panic if its argument is less than zero.
I'd like to change that to define RotateLeft to do a right rotate if its arg is less than zero.

Having a base routine like this one panic seems unnecessarily harsh. I'd argue that a rotate by a negative amount is more analogous to a shift by larger than the word size (which doesn't panic) instead of a divide by zero (which does panic). Divide-by-zero really has to panic, as there is no reasonable result you would return instead. Rotates by negative amounts have a perfectly well-defined result that we can return.

I think we should keep RotateLeft and RotateRight as separate functions, even though one could now be implemented with the other. Standard usage will still be with nonnegative arguments.

If we're going to do something here, we should do it by the freeze. Once go 1.9 is out we can't change our minds.

Rob:

If you really want something like this, I'd just have one function, Rotate, that takes a positive for left and a negative for right.

Me:

The problem is
bits.Rotate(x, -5)

It isn't clear when reading this code whether we end up rotating left or right.
bits.RotateRight(5)
is a lot clearer, even if it means there are twice as many Rotate* functions in math/bits.

Michael Jones:

Signed rotate means jumps in the code, yes? Seems a pity.

Me:

No, the implementation is actually simpler with the proposed semantics. Mask out the low 6 bits (for 64-bit rotates) and it just works.

[robpike]

I prefer the single Rotate with a signed argument because it means half the number of functions and can be done very efficiently in all cases without a panic or even a conditional branch.

Rotate is a specialist function anyways, so the people who use it will surely be comfortable with being asked to remember that a positive argument shifts left and a negative argument shifts right.

[bcmills]

You could always split the difference and provide only RotateLeft with a signed argument. That gives a handy mnemonic for the direction but avoids duplicating functions.

[josharian]

@bcmills @robpike see also previous discussion of this exact topic starting at https://github.com/golang/go/issues/18616#issuecomment-275598092 and continuing for a few comments

[robpike]

@josharian I have seen the comments and still prefer my version. This can be bikeshedded forever but I am trying to get to simple to implement, simple to define, simple to understand, and simple to document. I believe a single Rotate function with a signed argument satisfies all of that except for the need to define the sign, but that left is positive should be intuitive to anyone capable of using a rotate instruction.

[aclements]

but that left is positive should be intuitive to anyone capable of using a rotate instruction.

I like to consider myself capable of using a rotate instruction and my intuition is "Geez, why doesn't this say what direction it is? It's probably left, but I'll have to look at the documentation to be sure." I agree it's intuitive that if you were going to pick a positive direction it would be left rotation, but there's a much higher threshold for something to be so obviously the right answer that it's clear at every call site what direction you're rotating without saying it.

[nathany]

As far as readability, how about something along the lines of the time.Duration API:

const RotateRight = -1

bits.Rotate(x, 5 * RotateRight)

Maybe a constant defined by bits or maybe an exercise for the reader (call site)?

[robpike]

@aclements And so you end up with two (times N types) functions with identical capability whose only difference is a sign in the argument. Now we tolerate it for Add and Sub but that's the only example I can think of.

[cznic]

On the number axis positive numbers increase to the right, so I expect a direction-defined-by-sign rotate/shift to move the bits to the right for positive numbers.

I have no problem if it's going to be the [documented] opposite, but I'd not call that intuitive.

[nathany]

@cznic bits are written right-to-left though

[griesemer]

I'm also in favor of just Rotate (https://github.com/golang/go/issues/18616#issuecomment-275016583) if we make it work in both directions.

As a counter-argument to @aclements concern about the direction: Providing a RotateLeft that works also when rotating right can also provide a false sense of security: "It says RotateLeft so surely it's not rotating right!". In other words, if it says RotateLeft it better doesn't do anything else.

Also, the use of bits.Rotate is really in specialist code only. This is not a function that is used by a large number of programmers. Users that really need it will understand the symmetry of rotations.

[cznic]

@nathany

bits are written right-to-left though

Bits are just binary digits. Digits in number in any base are written left to right - even in most, if not all, right-to-left writing systems. 123 is one-hundred-and-twenty-three, not three-hundred-and-twenty-one.

That the power of the multiplicand for the digit decreases to the right is a different thing.

Once again: I don't care about the direction, it's just that the intuitive one is a matter of personal imagination.

[rogpeppe]

I like Rotate. Least significant bit is intuitively 0 enough in my view.

[rsc]

Please keep both RotateLeft and RotateRight instead of doing something half of developers will misremember. It seems fine to handle negative numbers though.

[robpike]

99% of developers will never program a rotate instruction, so the need for unambiguous direction is weak at best. A single call is enough.

The problem that reawakened this discussion is that having both requires arguing about whether negative values are OK, and if not, what to do about them. By having only one, that whole argument falls away. It's cleaner design.

[ct1n]

I somewhat sympathize with the argument about clean design but it seems weird that you have to remove "Right" from "RotateRight", while keeping the same implementation, in order to achieve it. In practical terms the only way it seems to answer questions is by forcing people who see it to read the documentation, by way of the questions the name raises.
In the end it's a matter of unambiguous direction vs unambiguous behavior for negative values. Negative values should probably be less of a concern in the common case.

What I'm saying is that Rotate raises one question for all people, answering it indirectly through documentation.
RotateRight raises one question for very few people who can (and should) read the documentation if they care about it.

On the other hand Rotate would probably prevent people from writing if n < 0 { RotateLeft(...) } else { RotateRight(...) }.

[rsc]

@golang/proposal-review discussed this and ended up at having just one function, but naming it RotateLeft, not just Rotate, to be extra clear at call sites. Negative numbers rotate right, and documentation will make this clear.

[gopherbot]

CL https://golang.org/cl/40394 mentions this issue.

[gopherbot]

CL https://golang.org/cl/41630 mentions this issue.

[griesemer]

The original proposal plus a few extra functions have been designed and implemented at this point. We may add to this library over time, but it seems reasonably "complete" for now.

Most notably, we have not decided upon or implemented functionality to:

• test whether add/mul/etc overflow
• provide functions to implement add/mul/etc that accept an incoming carry and produce a result plus carry (or higher word)

Personally I'm not convinced those belong into a "bits" package (maybe the tests do). Functions to implement multi-precision add/sub/mul would allow a pure Go implementation of some of the math/big kernels, but I don't believe the granularity is right: What we want there is optimized kernels working on vectors, and maximum performance for those kernels. I don't believe we can achieve that with Go code depending on add/sub/mul "intrinsics" alone.

Thus, for now I like to close this issue as "done" unless there are major objections. Please speak up over the next week or so if you are against closing this.

[jimmyfrasche]

I'm in favor of adding functions along those lines.

I strongly believe that they belong in their own package, if for no other reason than to give it a name that better reflects their collective functionality.

:+1: on closing this issue and :heart: for the work done so far.

[griesemer]

Closing since there were no objections.

[dskinner]

This is a comment for future decisions regarding API, I understand this particular one is set.

Rotate is a specialist function; LTR or RTL is only relevant given the context. @aclements brought up a valid question, not a valid ever-extending point. His question could have been answered as "it's RTL, just as integers increment"; easy, right?

But instead, cleverness ensues.

What "a specialist function" means is such a simple thing, it was likely dismissed to quickly. Given a code sample, one likely already understands the rotate to occur and the direction even before encountering the line of code. Such code is usually already preceded by illustrative ascii documentation as it is.

What's mentally turbulent is not that Go could have simply chosen RTL as a standard way of interpreting bits from an API perspective, but rather, I first pulled up the changes of 1.9 and find a RotateLeft with no counterpart and the doc giving an example of a negative stride. This is a mind-numbing committee-like decision that is very unfortunate to be landing in 1.9.

I only plead to stick to context of usage for the future. All of this should have been self-evident with questions like, "why are we not providing a counterpart to RotateLeft, why are we panic'ing on negative strides or debating int vs uint for a stride"; ultimately, because I think what "a specialist function" means was simply dismissed to easily for not being clever.

Let us please avoid cleverness in our justification of APIs. It shows in this 1.9 update.

[gopherbot]

Change https://golang.org/cl/90835 mentions this issue: cmd/compile: arm64 intrinsics for math/bits.OnesCount