[avalanche] Use black magic for popcount.
ClosedPublic
Actions

Authored by deadalnix on Nov 29 2018, 16:25.

Details

Reviewers

jasonbcox
Fabien
Mengerian

Group Reviewers

Restricted Project

Commits

rSTAGINGc7b844fb409d: [avalanche] Use black magic for popcount.
rABCc7b844fb409d: [avalanche] Use black magic for popcount.

Summary

Or compiler intrinsic if these are supported.

The black magic algorithm is from 'Owen Anderson <resistor@mac.com>', as far as I know.

Test Plan

make check

Diff Detail

Repository

rABC Bitcoin ABC

Branch

avapopcount

Lint

Lint Passed

Unit

No Test Coverage

Build Status

Buildable 4255
Build 6575: Bitcoin ABC Buildbot (legacy)
Build 6574: arc lint + arc unit

Event Timeline

deadalnix created this revision.Nov 29 2018, 16:25

Herald added a reviewer: Restricted Project. · View Herald TranscriptNov 29 2018, 16:25

Herald added a subscriber: schancel. · View Herald Transcript

Build Bitcoin-ABC / Diffs / Bitcoin-ABC Diff Testing started.

Build Bitcoin-ABC / Diffs / Bitcoin-ABC Diff Testing passed.

Harbormaster completed remote builds in B4168: Diff 6165.Nov 29 2018, 16:36

jasonbcox requested changes to this revision.Nov 29 2018, 20:10

jasonbcox added a subscriber: jasonbcox.

jasonbcox added inline comments.

src/avalanche.cpp
17 ↗	(On Diff #6165)	Needs test(s). Something like a map of 1-byte hex values and their known countBits() results, plus concatenating these hex values together of various lengths, should do the job.
27 ↗	(On Diff #6165)	Moving this should be in a separate diff. Seems totally unrelated to the popcount change.

This revision now requires changes to proceed.Nov 29 2018, 20:10

deadalnix requested review of this revision.Nov 29 2018, 23:58

deadalnix marked 2 inline comments as done.

deadalnix added inline comments.

src/avalanche.cpp
17 ↗	(On Diff #6165)	I would rather keep that function as an internal implementation detail than expose it from the API, unless it is required. The behavior is tested via registerVote's test, and while that is not ideal, adding a unittest specifically for it wouldn't cut it either because it would check for the compiler intrinsic on pretty much all plateforms, which we assume is correct (and if it's not, there isn't much we can do about it).
27 ↗	(On Diff #6165)	In fact it is. The goal here was to reduce dependencies. The popcount code is used only here and therefore only accessible here. If popcount becomes something that is generally useful, then we'll move it into some header, but in the meantime, I'd rather have it here and static.

deadalnix added a child revision: D2160: [avalanche] Add the concept of inconclusive votes.Nov 30 2018, 15:37

magic

src/avalanche.cpp
17 ↗	(On Diff #6165)	As long as registerVote has sufficient testing, then I suppose we're good. Looking at the existing tests, I think the coverage will be enough. I'll continue to think about any new test cases.

This revision is now accepted and ready to land.Nov 30 2018, 18:56

Fabien accepted this revision.Dec 1 2018, 12:30

There is a build warning in the popcount algo

src/avalanche.cpp
23 ↗	(On Diff #6165)	avalanche.cpp:23:16: warning: suggest parentheses around ‘+’ in operand of ‘&’ [-Wparentheses] return (((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;

This revision now requires changes to proceed.Dec 1 2018, 13:58

Mengerian requested changes to this revision.Dec 2 2018, 18:49

Mengerian added a subscriber: Mengerian.

Mengerian added inline comments.

src/avalanche.cpp
17 ↗	(On Diff #6165)	Could you keep the comment in? Maybe something like: Return the number of bits set, as an integer value. Use compiler intrinsic if these are supported. Otherwise use black magic algorithm.