{"action":"created","issue":{"url":"https://api.github.com/repos/golang/go/issues/18616","repository_url":"https://api.github.com/repos/golang/go","labels_url":"https://api.github.com/repos/golang/go/issues/18616/labels{/name}","comments_url":"https://api.github.com/repos/golang/go/issues/18616/comments","events_url":"https://api.github.com/repos/golang/go/issues/18616/events","html_url":"https://github.com/golang/go/issues/18616","id":200169025,"number":18616,"title":"proposal: math/bits: an integer bit twiddling library","user":{"login":"brtzsnr","id":57079,"avatar_url":"https://avatars.githubusercontent.com/u/57079?v=3","gravatar_id":"","url":"https://api.github.com/users/brtzsnr","html_url":"https://github.com/brtzsnr","followers_url":"https://api.github.com/users/brtzsnr/followers","following_url":"https://api.github.com/users/brtzsnr/following{/other_user}","gists_url":"https://api.github.com/users/brtzsnr/gists{/gist_id}","starred_url":"https://api.github.com/users/brtzsnr/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/brtzsnr/subscriptions","organizations_url":"https://api.github.com/users/brtzsnr/orgs","repos_url":"https://api.github.com/users/brtzsnr/repos","events_url":"https://api.github.com/users/brtzsnr/events{/privacy}","received_events_url":"https://api.github.com/users/brtzsnr/received_events","type":"User","site_admin":false},"labels":[{"id":236419512,"url":"https://api.github.com/repos/golang/go/labels/Proposal","name":"Proposal","color":"ededed","default":false}],"state":"open","locked":false,"assignee":{"login":"griesemer","id":8528975,"avatar_url":"https://avatars.githubusercontent.com/u/8528975?v=3","gravatar_id":"","url":"https://api.github.com/users/griesemer","html_url":"https://github.com/griesemer","followers_url":"https://api.github.com/users/griesemer/followers","following_url":"https://api.github.com/users/griesemer/following{/other_user}","gists_url":"https://api.github.com/users/griesemer/gists{/gist_id}","starred_url":"https://api.github.com/users/griesemer/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/griesemer/subscriptions","organizations_url":"https://api.github.com/users/griesemer/orgs","repos_url":"https://api.github.com/users/griesemer/repos","events_url":"https://api.github.com/users/griesemer/events{/privacy}","received_events_url":"https://api.github.com/users/griesemer/received_events","type":"User","site_admin":false},"assignees":[{"login":"griesemer","id":8528975,"avatar_url":"https://avatars.githubusercontent.com/u/8528975?v=3","gravatar_id":"","url":"https://api.github.com/users/griesemer","html_url":"https://github.com/griesemer","followers_url":"https://api.github.com/users/griesemer/followers","following_url":"https://api.github.com/users/griesemer/following{/other_user}","gists_url":"https://api.github.com/users/griesemer/gists{/gist_id}","starred_url":"https://api.github.com/users/griesemer/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/griesemer/subscriptions","organizations_url":"https://api.github.com/users/griesemer/orgs","repos_url":"https://api.github.com/users/griesemer/repos","events_url":"https://api.github.com/users/griesemer/events{/privacy}","received_events_url":"https://api.github.com/users/griesemer/received_events","type":"User","site_admin":false}],"milestone":{"url":"https://api.github.com/repos/golang/go/milestones/30","html_url":"https://github.com/golang/go/milestone/30","labels_url":"https://api.github.com/repos/golang/go/milestones/30/labels","id":1373555,"number":30,"title":"Proposal","description":"Proposals that are pending (not yet accepted/rejected).\r\n","creator":{"login":"rsc","id":104030,"avatar_url":"https://avatars.githubusercontent.com/u/104030?v=3","gravatar_id":"","url":"https://api.github.com/users/rsc","html_url":"https://github.com/rsc","followers_url":"https://api.github.com/users/rsc/followers","following_url":"https://api.github.com/users/rsc/following{/other_user}","gists_url":"https://api.github.com/users/rsc/gists{/gist_id}","starred_url":"https://api.github.com/users/rsc/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rsc/subscriptions","organizations_url":"https://api.github.com/users/rsc/orgs","repos_url":"https://api.github.com/users/rsc/repos","events_url":"https://api.github.com/users/rsc/events{/privacy}","received_events_url":"https://api.github.com/users/rsc/received_events","type":"User","site_admin":false},"open_issues":47,"closed_issues":106,"state":"open","created_at":"2015-10-24T01:40:49Z","updated_at":"2017-01-27T10:11:56Z","due_on":null,"closed_at":null},"comments":57,"created_at":"2017-01-11T18:18:27Z","updated_at":"2017-01-27T19:00:45Z","closed_at":null,"body":"Previous discussions at https://github.com/golang/go/issues/17373 and https://github.com/golang/go/issues/10757.\r\n\r\n## Abstract\r\n\r\nThis proposal introduces a set of API for integer bit twiddling.\r\n\r\n## Background\r\n\r\nThis proposal introduces a set of API for integer bit twiddling. For this proposal we are interested in the following functions:\r\n\r\n* ctz - count trailing zeros.\r\n* clz - count leading zeros; log\\_2.\r\n* popcnt - count population; hamming distance; integer parity.\r\n* bswap - reverses the order of bytes.\r\n\r\nThese functions were picked by surveying:\r\n\r\n* Go compiler and tools\r\n* Popular libraries\r\n* golang-nuts@ discussions list\r\n* Bit Twiddling Hacks - https://graphics.stanford.edu/~seander/bithacks.html\r\n* A curated list of awesome bitwise operations and tricks - https://github.com/keonkim/awesome-bits\r\n\r\nWe limited ourselves to these four functions because other twiddling\r\ntricks are very simple to implement using the proposed library,\r\nor already available Go constructs.\r\n\r\nWe found implementations for a subset of the selected twiddling functions\r\nin many packages including runtime, compiler and tools:\r\n\r\n| package | clz | ctz | popcnt | bswap |\r\n| --- | --- | --- | --- | --- |\r\n| math/big | X | X | | |\r\n| runtime/internal/sys | X | X | | X |\r\n| tools/container/intsets | X | | X | |\r\n| cmd/compile/internal/ssa | X | | X |  |\r\n| code.google.com/p/intmath | X | X | | |\r\n| github.com/hideo55/go-popcount | | | X (asm) | |\r\n| github.com/RoaringBitmap/roaring | | X | X (asm) | |\r\n| github.com/tHinqa/bitset | X | X | X | |\r\n| github.com/willf/bitset | X | | X (asm) | |\r\n| gopl.io/ch2/popcount | | | X | |\r\n| GCC builtins | X | X | X | X |\r\n\r\nMany other packages implement a subset of these functions:\r\n\r\n* http://go-search.org/search?q=popcount returns 58 packages.\r\n* http://go-search.org/search?q=popcnt returns 11 packages.\r\n* TODO(mosoi): Other relevant searches?\r\n\r\n\r\nSimilarly hardware providers have recognized the importance\r\nof such functions and included machine level support.\r\nWithout hardware support these operations are very expensive.\r\n\r\n| arch | clz | ctz | popcnt | bswap |\r\n| --- | --- | --- | --- | --- |\r\n| AMD64 | X | X | X | X |\r\n| ARM | X | X | ? | X|\r\n| ARM64 | X | X | ? | X|\r\n| S390X | X | X | ? | X|\r\n\r\n\r\nAll bit twiddling functions, except popcnt, are already implemented by runtime/internal/sys and receive special [support](https://github.com/golang/go/commits/master/src/runtime/internal/sys/intrinsics.go) 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.\r\n\r\n\r\n## Proposal\r\n\r\nWe 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.\r\n\r\n\r\n```golang\r\npackage bits\r\n\r\n// SwapBytes16 reverses the order of bytes in a 16-bit integer.\r\nfunc SwapBytes16(uint16) uint16\r\n// SwapBytes32 reverses the order of bytes in a 32-bit integer.\r\nfunc SwapBytes32(uint32) uint32\r\n// SwapBytes64 reverses the order of bytes in a 64-bit integer.\r\nfunc SwapBytes64(uint64) uint64\r\n\r\n// TrailingZeros32 counts the number of trailing zeros in a 32-bit integer, and if all are zero, then 32.\r\nfunc TrailingZeros32(uint32) uint\r\n// TrailingZeros64 counts the number of trailing zeros in a 64-bit integer, and if all are zero, then 64.\r\nfunc TrailingZeros64(uint64) uint\r\n\r\n// LeadingZeros32 counts the number of trailing zeros in a 32-bit integer, and if all are zero, then 32.\r\nfunc LeadingZeros32(uint32) uint\r\n// LeadingZeros64 counts the number of trailing zeros in a 64-bit integer, and if all are zero, then 64.\r\nfunc LeadingZeros64(uint64) uint\r\n\r\n// Ones32 counts the number of bits set in a 32-bit integer.\r\nfunc Ones32(uint32) uint\r\n// Ones64 counts the number of bits set in a 64-bit integer.\r\nfunc Ones64(uint64) uint\r\n```\r\n\r\n## Rationale\r\n\r\nAlternatives to this proposal are:\r\n\r\n* 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.\r\n* 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.\r\n\r\n## Compatibility\r\n\r\nThis proposal does not change or breaks any existing stdlib API and it conforms to compatibly guidelines.\r\n\r\n## Implementation\r\n\r\nSwapBytes, 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.\r\n\r\n## Open issues (if applicable)\r\n\r\nNames are hard, bike shed is in the comments.\r\n\r\nPlease 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. \r\n\r\nSo far the following functions have been proposed and are under consideration:\r\n\r\n* RotateLeft / RotateRight\r\n  * Pros: &63 is no longer need to compile a rotate with non-const argument to a single instruction on x86, x86-64..\r\n  * Cons: very short/simple to implement and inline.\r\n  * Used: crypto/ uses the constant rotate which is handled properly by the compiler.\r\n* ReverseBits\r\n  * Pros: ?\r\n  * Cons: ?\r\n  * Used: ?\r\n* Add/Sub with carry return\r\n  * Pros: Expensive otherwise\r\n  * Cons: ?\r\n  * Used: math/big\r\n\r\n\r\n## History\r\n\r\n14.Jan: Clarified the output of TrailingZeros and LeadingZeros when the argument is 0.\r\n14.Jan: Renamed methods: CountTrailingZeros -> TrailingZeros, CountLeadingZeros -> LeadingZeros, CountOnes -> Ones.\r\n13.Jan: Fixed architecture name.\r\n11.Jan: Initial proposal opened to public."},"comment":{"url":"https://api.github.com/repos/golang/go/issues/comments/275745628","html_url":"https://github.com/golang/go/issues/18616#issuecomment-275745628","issue_url":"https://api.github.com/repos/golang/go/issues/18616","id":275745628,"user":{"login":"iand","id":18375,"avatar_url":"https://avatars.githubusercontent.com/u/18375?v=3","gravatar_id":"","url":"https://api.github.com/users/iand","html_url":"https://github.com/iand","followers_url":"https://api.github.com/users/iand/followers","following_url":"https://api.github.com/users/iand/following{/other_user}","gists_url":"https://api.github.com/users/iand/gists{/gist_id}","starred_url":"https://api.github.com/users/iand/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/iand/subscriptions","organizations_url":"https://api.github.com/users/iand/orgs","repos_url":"https://api.github.com/users/iand/repos","events_url":"https://api.github.com/users/iand/events{/privacy}","received_events_url":"https://api.github.com/users/iand/received_events","type":"User","site_admin":false},"created_at":"2017-01-27T19:00:45Z","updated_at":"2017-01-27T19:00:45Z","body":"@bradfitz golang.org/x/image/math/f64 and golang.org/x/image/math/f32 exist though"}}
{"actor":{"display_login":"iand"}}