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

Activity

robpike

robpike commented on May 8, 2015

@robpike
Contributor

Duplicate of #4988

No need for this to be in the standard library.

locked and limited conversation to collaborators on Jun 25, 2016
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

      Development

      No branches or pull requests

        Participants

        @brtzsnr@robpike@gopherbot

        Issue actions

          Provide a builtin for population counting / hamming distance · Issue #10757 · golang/go