Optimize compact reconstruction somewhat

TheBlueMatt commented at 5:28 pm on July 21, 2017: member

This 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 change uint16_t to uint64_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:

https://travis-ci.org/bitcoin/bitcoin/jobs/256256286#L2508

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 sense

fanquake added the label Resource usage on Jul 21, 2017

TheBlueMatt force-pushed on Jul 21, 2017

TheBlueMatt force-pushed on Jul 22, 2017

in 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 line

in 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 guide

in 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, brace

in 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:

Brace

meshcollider commented at 7:26 am on July 22, 2017: contributor

A few more style nits, also all the function braces too

in 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: member

Is this going forward? I mean, according to @TheBlueMatt, the benefits aren’t that much and requires to maintain open_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, 2017

TheBlueMatt force-pushed on May 4, 2018

Add an implementation of an open hash set bd28872def

Use open_hash_set in blockencodings f54ce22caa

open_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>

a9b97e7bf2

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>

5363403855

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

ab348136e9

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>

0199479e6d

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>

4e2e675461

Return early in PartiallyDownloadedBlock if we got full-prefill af1be03a43

Dont alloc twice in block header deserialize cfe5377da7

TheBlueMatt force-pushed on May 4, 2018

DrahtBot commented at 11:23 am on July 14, 2018: member

DrahtBot added the label Needs rebase on Jul 14, 2018

DrahtBot commented at 11:20 pm on November 8, 2018: member

DrahtBot added the label Up for grabs on Nov 8, 2018

DrahtBot closed this on Nov 8, 2018

laanwj removed the label Needs rebase on Oct 24, 2019

DrahtBot locked this on Dec 16, 2021

Optimize compact reconstruction somewhat #10896