Optimize compact reconstruction somewhat #10896
pull TheBlueMatt wants to merge 9 commits into bitcoin:master from TheBlueMatt:2017-07-faster-compact-reconstruction changing 4 files +175 −31-
TheBlueMatt commented at 5:28 pm on July 21, 2017: memberThis is some stuff I did for FIBRE a while back (that @rustyrussell cleaned up a lot, thanks!) and figured could get upstreamed. It saves some milliseconds when reconstructing, but for upstream its not all that critical.
-
in src/blockencodings.cpp:162 in b14321e967 outdated
163- if (idit != shorttxids.end()) { 164- if (!have_txn[idit->second]) { 165- txn_available[idit->second] = extra_txn[i].second; 166- have_txn[idit->second] = true; 167+ uint64_t next_shortid = 0; 168+ if (i + 1 < extra_txn.size())
gmaxwell commented at 5:37 pm on July 21, 2017:unbraced
TheBlueMatt commented at 11:32 pm on July 21, 2017:Oops, forgot to style the stuff, fixed now.in src/blockencodings.cpp:50 in b14321e967 outdated
43@@ -43,6 +44,32 @@ uint64_t CBlockHeaderAndShortTxIDs::GetShortID(const uint256& txhash) const { 44 return SipHashUint256(shorttxidk0, shorttxidk1, txhash) & 0xffffffffffffL; 45 } 46 47+namespace { 48+ struct ShortIdIndexPair { 49+ uint64_t shortid : 48; 50+ uint16_t index : 16;
arvidn commented at 11:18 pm on July 21, 2017:in order to make these packed together, you should changeuint16_t
touint64_t
. Otherwise these are two separate bitfields with different allocation units.
TheBlueMatt commented at 11:32 pm on July 21, 2017:Are you sure? There’s a static_assert on the sizeof on the next line that doesnt make compile fail?
arvidn commented at 11:38 pm on July 21, 2017:
arvidn commented at 11:39 pm on July 21, 2017:I think compilers are free to pack them still if they want to, but my recollection is that they aren’t required to
TheBlueMatt commented at 11:40 pm on July 21, 2017:Oh, funny, didnt realize it failed on 32 bit windows, but passed on 64-bit linux, did as you suggested.in src/open_hash_set.h:36 in b14321e967 outdated
31+ }; 32+ 33+private: 34+ hasher hash_instance; 35+ key_equal equal_instance; 36+ IsKeyNull null_instance;
arvidn commented at 11:25 pm on July 21, 2017:all these instances are going to occupy one byte of storage each, despite not having any state (this is because of the guarantee C++ give you that every object has a unique address). It may not matter, but one trick to make them not use any space is to derive from them, and rely on the empty base class optimization
TheBlueMatt commented at 11:44 pm on July 21, 2017:Hmm, if I’m understanding your suggestion correctly I find the current code much more readable, and the few extra bytes isnt worth a readabilitiy loss.
arvidn commented at 11:45 pm on July 21, 2017:makes sensefanquake added the label Resource usage on Jul 21, 2017TheBlueMatt force-pushed on Jul 21, 2017TheBlueMatt force-pushed on Jul 21, 2017TheBlueMatt force-pushed on Jul 22, 2017in src/blockencodings.cpp:47 in fdff23cbfa outdated
43@@ -43,6 +44,32 @@ uint64_t CBlockHeaderAndShortTxIDs::GetShortID(const uint256& txhash) const { 44 return SipHashUint256(shorttxidk0, shorttxidk1, txhash) & 0xffffffffffffL; 45 } 46 47+namespace {
meshcollider commented at 7:18 am on July 22, 2017:Nit, namespace brace on same linein src/blockencodings.cpp:72 in fdff23cbfa outdated
67+ struct ShortIdIndexPairIsNull { 68+ bool operator()(const ShortIdIndexPair& elem) const { 69+ return elem.shortid == 0 && elem.index == 0; 70+ } 71+ }; 72+};
meshcollider commented at 7:19 am on July 22, 2017:Semicolon, and should have end of namespace comment according to style guidein src/open_hash_set.h:11 in fdff23cbfa outdated
6+#include <stdio.h> 7+ 8+/** Implements an open hash set. 9+ */ 10+template<class Key, class IsKeyNull, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>> 11+class open_hash_set {
meshcollider commented at 7:24 am on July 22, 2017:Nit, bracein src/open_hash_set.h:19 in fdff23cbfa outdated
14+ typedef Key value_type; 15+ typedef size_t size_type; 16+ typedef Hash hasher; 17+ typedef KeyEqual key_equal; 18+ 19+ class iterator {
meshcollider commented at 7:25 am on July 22, 2017:Bracemeshcollider commented at 7:26 am on July 22, 2017: contributorA few more style nits, also all the function braces tooin src/open_hash_set.h:6 in fdff23cbfa outdated
0@@ -0,0 +1,107 @@ 1+#ifndef OPEN_HASH_MAP_H 2+#define OPEN_HASH_MAP_H 3+ 4+#include <utility> 5+ 6+#include <stdio.h>
promag commented at 10:25 am on July 25, 2017:Remove.in src/open_hash_set.h:5 in fdff23cbfa outdated
0@@ -0,0 +1,107 @@ 1+#ifndef OPEN_HASH_MAP_H 2+#define OPEN_HASH_MAP_H 3+ 4+#include <utility>
promag commented at 10:25 am on July 25, 2017:Use these instead:
0#include <functional> 1#include <vector>
TheBlueMatt commented at 6:17 pm on August 3, 2017:Need utility for pair.promag commented at 10:30 am on July 25, 2017: memberIs this going forward? I mean, according to @TheBlueMatt, the benefits aren’t that much and requires to maintainopen_hash_set
.TheBlueMatt commented at 7:02 pm on July 25, 2017: member@promag definitely not for 15, so lets wait to see what people think when the focus is back on other stuff.TheBlueMatt force-pushed on Aug 3, 2017TheBlueMatt force-pushed on May 4, 2018TheBlueMatt force-pushed on May 4, 2018TheBlueMatt force-pushed on May 4, 2018Add an implementation of an open hash set bd28872defUse open_hash_set in blockencodings f54ce22caaopen_hash_set: use a smaller (and power of two) hash table.
This makes performance a little worse, due to more hash collisions, depending on how sparse we make it. Since we're going to switch to linear chaining, we can afford slightly more collisions, sowe drop to 4x. 50% full (2x oversize): Total insert hashes = 1977, total find hashes = 87224 25% full (4x oversize): Total insert hashes = 1749, total find hashes = 63927 12.5% full (8x oversize, equivalent to original): Total insert hashes = 1639, total find hashes = 56644 Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
open_hash_set: use a linear hash scan.
No more jumping around the table, and just use the lower bits as hash. Total insert hashes = 1762, total find hashes = 65245 Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
open_hash_set: make scan_max a constant.
For a given density, the chances of more than N collisions is indendent of hash table size. We chose 1/4 density, so we can assert that the chances of 20 collisions is 1 in 2^40. FECHeaderRTTTest1550,288,0.003517217934132,0.003554463386536,0.003529562718338,9538257,9639290,9571711
open_hash_set: don't bother counting scan_max in find().
The caller aborts when an insert fails (as expected), so don't need to check here, nor the extra equal_instance() check. #Benchmark,count,min,max,average,min_cycles,max_cycles,average_cycles FECHeaderRTTTest1550,320,0.003286004066467,0.003375306725502,0.003304844349623,8911484,9153595,8962469 Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
open_hash_set: make find_fast() that uses a const table.
I cheated here, and just returned a damn pointer. Similar gains might be made from creating a const_iterator, but end() is not NULL, so it's a more expensive comparison in the caller. #Benchmark,count,min,max,average,min_cycles,max_cycles,average_cycles FECHeaderRTTTest1550,320,0.003265343606472,0.003385126590729,0.003300794214010,8855479,9180430,8951641 Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
Return early in PartiallyDownloadedBlock if we got full-prefill af1be03a43Dont alloc twice in block header deserialize cfe5377da7TheBlueMatt force-pushed on May 4, 2018DrahtBot commented at 11:23 am on July 14, 2018: memberDrahtBot added the label Needs rebase on Jul 14, 2018DrahtBot commented at 11:20 pm on November 8, 2018: memberDrahtBot added the label Up for grabs on Nov 8, 2018DrahtBot closed this on Nov 8, 2018
laanwj removed the label Needs rebase on Oct 24, 2019DrahtBot locked this on Dec 16, 2021
github-metadata-mirror
This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2024-10-31 03:12 UTC
This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me