Skip to content

Provide a builtin for population counting / hamming distance #10757

Closed
@brtzsnr

Description

@brtzsnr

This feature was requested before #4988 but the bug was closed as WAI. I believe having popcnt part of standard library would benefit greatly many libraries.

For example there are two popcnt implementation in the golang tools:
https://github.com/golang/go/blob/dev.ssa/src/cmd/internal/ssa/regalloc.go#L39
https://github.com/golang/tools/blob/master/container/intsets/util.go#L22

It is also provided by several third party libraries
http://go-search.org/search?q=popcnt
http://go-search.org/search?q=popcount

These implementation are incomplete: the libraries provide assembly for one platform (amd64 in the best case), may not be not inlined (function call will dominate the benchmarks http://stackoverflow.com/questions/25471369/performance-discrepancy-in-compiled-vs-hand-written-assembly), are not well test, or are under a restrictive licence.

There is also a long standing bug #4816 which requests the POPCNT instruction on amd64. With POPCNT instruction population counting can be turned into a single instruction similarly to math.Sqrt (https://go-review.googlesource.com/#/c/8465/).

popcnt is very often used by chess, go (the game), checkers engines, all of them would benefit from a fast popcnt. #7357 provides another real word usage. Also a Go developer expressed his wish for popcnt (and other similar operations) to be provided by the standard library (https://go-review.googlesource.com/#/c/9761/1/src/cmd/internal/ssa/regalloc.go@41).

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions