Repository navigation
math/bits: an integer bit twiddling library #18616
Description
Previous discussions at #17373 and #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) uintRationale
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.
Activity
cespare commentedon Jan 11, 2017
@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 commentedon Jan 11, 2017
@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 commentedon Jan 11, 2017
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 thanbits.CountTrailingZeros64(x)and so forth.
griesemer commentedon Jan 11, 2017
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 commentedon Jan 11, 2017
@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 commentedon Jan 11, 2017
The last arch listed in the hardware support table is "BSWAP" -- typo?
josharian commentedon Jan 12, 2017
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 commentedon Jan 12, 2017
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
log2functions 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 commentedon Jan 13, 2017
dsnet commentedon Jan 13, 2017
@minux, fortunately, every bit twiddling function I've needed so far is exactly the ones that are in this proposal.
dr2chase commentedon Jan 13, 2017
Following Hacker's Delight has the advantage that we don't need to waste time arguing about the names.
minux commentedon Jan 13, 2017
josharian commentedon Jan 13, 2017
Relatedly, functions to check whether an add/multiply will overflow.
161 remaining items
rsc commentedon Apr 10, 2017
@golang/proposal-review discussed this and ended up at having just one function, but naming it
RotateLeft, not justRotate, to be extra clear at call sites. Negative numbers rotate right, and documentation will make this clear.math/bits: support negative rotation count and remove RotateRight
gopherbot commentedon Apr 21, 2017
CL https://golang.org/cl/40394 mentions this issue.
gopherbot commentedon Apr 25, 2017
CL https://golang.org/cl/41630 mentions this issue.
griesemer commentedon Apr 27, 2017
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:
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 commentedon Apr 27, 2017
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.
👍 on closing this issue and ❤️ for the work done so far.
griesemer commentedon May 5, 2017
Closing since there were no objections.
cmd/compile: ppc64x intrinsics for math/bits
dskinner commentedon Aug 17, 2017
This is a comment for future decisions regarding API, I understand this particular one is set.
Rotateis 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 commentedon Jan 30, 2018
Change https://golang.org/cl/90835 mentions this issue:
cmd/compile: arm64 intrinsics for math/bits.OnesCountcmd/compile: arm64 intrinsics for math/bits.OnesCount