New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

ponies: population count #4988

Closed
gopherbot opened this Issue Mar 6, 2013 · 12 comments

Comments

Projects
None yet
6 participants
@gopherbot
Copy link

gopherbot commented Mar 6, 2013

by fuzxxl:

The Popcount (or hammington weight) is a function that determines the number of one-bits
in an integer. This function is useful for cryptographic applications and certain data
structures. As it is possible to implement this function efficiently with special
instructions (VCNT on ARM7 and POPCOUNT on amd64 since SSE 4.2), it would be nice to
have this function in the standard library.
@bradfitz

This comment has been minimized.

Copy link
Member

bradfitz commented Mar 6, 2013

Comment 1:

Labels changed: removed go1.1.

@gopherbot

This comment has been minimized.

Copy link

gopherbot commented Mar 10, 2013

Comment 2 by fuzxxl:

Somebody (Jan Mercl) wrote, than one could use a package such as
github.com/cznic/mathutil. That kind of misses the point. Of course it is easy to
implement functions like popcount and find-first-set with bit fiddling, but such an
implementation is around ten to twenty times slower than an implementation that uses a
compiler intrinsic that directly emits a single instruction when possible. This matters
in some use cases. It would be nice to have bit-fiddling functions that can be
implemented easily with special instructions in a core package.
@rsc

This comment has been minimized.

Copy link
Contributor

rsc commented Mar 12, 2013

Comment 3:

[The time for maybe has passed.]
@minux

This comment has been minimized.

Copy link
Member

minux commented May 13, 2013

Comment 4:

if you need that level of performance, you probably should just use C
or even assembly, and use cgo to interface them with Go.
@griesemer

This comment has been minimized.

Copy link
Contributor

griesemer commented May 14, 2013

Comment 5:

Popcount is a useful function to have for certain applications. It would be useful if
you could be a bit more specific: For instance, would it be sufficient to have Popcount
as a method on a big.Int? We already have core routines in assembly for math/big, and
this would be a natural fit. Or is Popcount mostly used for short (one, two-word) data?
(the big.Int Popcount would be overkill).

Owner changed to @griesemer.

Status changed to WaitingForReply.

@gopherbot

This comment has been minimized.

Copy link

gopherbot commented May 14, 2013

Comment 6 by mndrix:

I typically want to use popcount on int64 values for creating sparse arrays.  My
applications mostly run in App Engine, so C or assembly is not available.
@griesemer

This comment has been minimized.

Copy link
Contributor

griesemer commented May 14, 2013

Comment 7:

Here's a basic software implementation: http://play.golang.org/p/M2nxXCyrd7 (you will
need to run it locally as the playground times out).
"Hacker's Delight" may have some words to say about this to make it faster. Still, on a
2.8Ghz Quad-Core Intel Xeon machine with 800MHz DDR2 RAM, I get approx. 10ns for a
single 64bit pop-count computation.
10ns seems pretty good, and unless your application is doing nothing but popcount, even
making it 10x faster might not make a big difference overall.
Thus, doing this in software might be just fine for almost all purposes. It's trivial
enough that a library may not be warranted - and a custom solution is likely to be
faster because it can use the right type (sizes).
@gopherbot

This comment has been minimized.

Copy link

gopherbot commented May 16, 2013

Comment 8 by fuzxxl:

popcount is especially useful for types your machine can handle but it is also nice to
have for big.Int, especially for mathematical analysis.
Care must be taken when implementing pop count for negative number, as they have an
infinite number of one bits. Some implementations return the number of zero bits negated
for negative numbers.
@adonovan

This comment has been minimized.

Copy link

adonovan commented Jun 28, 2013

Comment 9:

FWIW, the playground code posted above contains a bug: the 1*N in a[byte(x>>(1*N))] etc
needs to be parenthesized since it * and >> have multiplicative precedence.
The lesson here: even 1-liners have bugs.  $GOROOT/src/pkg/hackers/delight FTW!
@griesemer

This comment has been minimized.

Copy link
Contributor

griesemer commented Jun 28, 2013

Comment 10:

Good point... (sigh). Here's the correct version: http://play.golang.org/p/Ex5E59A_69
It still takes approx. 9ns per operation.
@gopherbot

This comment has been minimized.

Copy link

gopherbot commented Jul 17, 2013

Comment 11 by arnehormann:

This one takes 2ns for me:
http://play.golang.org/p/U7SogJ7psJ
@rsc

This comment has been minimized.

Copy link
Contributor

rsc commented Jul 25, 2013

Comment 12:

Yes, it's true that using the hardware instruction is faster than not using it.
That said, it's unlikely the language will ever add this instruction.
The right answer is assembly. I'm sorry that answer is not available on App Engine.
It would be nice if some day it was.

Labels changed: added priority-someday, removed priority-triage.

Status changed to WorkingAsIntended.

This issue was closed.

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.