math/bits: an integer bit twiddling library

[brtzsnr]

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) 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.