Skip to content

Conversation

@sipa
Copy link
Member

@sipa sipa commented Apr 20, 2014

This patch moves/implements all logic (multiplication, division, GetCompact, SetCompact) that main used from CBigNum to base_uint or uint256, and replaces its call sites by equivalent uint256 operations.

The division and multiplication operations are very straightforward, but not very efficient. None of their call sites require that, though.

Together with #3965 and #4048, this will allow up to drop bignum.h entirely.

@jgarzik
Copy link
Contributor

jgarzik commented Apr 21, 2014

ACK

@laanwj
Copy link
Member

laanwj commented Apr 22, 2014

This is great!

@sipa
Copy link
Member Author

sipa commented Apr 25, 2014

Some benchmarks:

  • operator/ is up to 10 times slower than the CBigNum version (10us vs 0.8us at -O2; 4us at -O3).
  • operator* seems significantly faster (0.08us vs 0.5us), probably due to avoiding allocation overhead.

@sipa
Copy link
Member Author

sipa commented Apr 25, 2014

Added another commit that removes some duplicated code.

Also replaced the bits() implementation with a faster one, making division 10% faster.

@BitcoinPullTester
Copy link

Automatic sanity-testing: PASSED, see http://jenkins.bluematt.me/pull-tester/66d5a5364a2c06a94e650d1184e92cce2b166e2a for binaries and test log.
This test script verifies pulls every time they are updated. It, however, dies sometimes and fails to test properly. If you are waiting on a test, please check timestamps to verify that the test.log is moving at http://jenkins.bluematt.me/pull-tester/current/
Contact BlueMatt on freenode if something looks broken.

@gmaxwell
Copy link
Contributor

ACK. (reviewed the code, tested a mainnet and a testnet resync, and added some errors and checked that they were caught— I do note that triggering divide by zero in— say— block validation results in the exception being caught which surprised me momentarily).

The division can be made another 10% faster by using CLZ instead of the inner loop, but further optimizations do not need to happen now. (We call the divide in GetBlockWork, which we do for every block, and it appears to make a difference in the very early sync for me; though I consider these measurements somewhat suspect.)

@laanwj
Copy link
Member

laanwj commented May 9, 2014

Needs rebase after #3965 and #3884

@laanwj laanwj merged commit 397668e into bitcoin:master May 9, 2014
laanwj added a commit that referenced this pull request May 9, 2014
397668e Deduplicate uint* comparison operator logic (Pieter Wuille)
df9eb5e Move {Get,Set}Compact from bignum to uint256 (Pieter Wuille)
a703150 Add multiplication and division to uint160/uint256 (Pieter Wuille)
4d480c8 Exception instead of assigning 0 in case of wrong vector length (Pieter Wuille)
eb2cbd7 Deduplicate shared code between uint160 and uint256 (Pieter Wuille)
laanwj added a commit to laanwj/bitcoin that referenced this pull request May 9, 2014
After bitcoin#4076, bitcoin#3965 and bitcoin#4048 bignum.h is only used
for verifying scriptnum.
@laanwj laanwj mentioned this pull request May 9, 2014
@bitcoin bitcoin locked as resolved and limited conversation to collaborators Sep 8, 2021
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

5 participants