1 2016-10-05T00:35:51  *** Chris_Stewart_5 has quit IRC
  2 2016-10-05T00:47:01  *** Ylbam has quit IRC
  3 2016-10-05T00:53:18  *** owowo has quit IRC
  4 2016-10-05T00:54:48  *** justanotheruser has quit IRC
  5 2016-10-05T00:57:07  *** owowo has joined #bitcoin-core-dev
  6 2016-10-05T01:01:41  *** Expanse has quit IRC
  7 2016-10-05T01:05:52  *** justanotheruser has joined #bitcoin-core-dev
  8 2016-10-05T01:07:42  *** juscamarena has joined #bitcoin-core-dev
  9 2016-10-05T01:13:58  *** Expanse has joined #bitcoin-core-dev
 10 2016-10-05T01:20:41  *** juscamarena has quit IRC
 11 2016-10-05T01:28:42  *** owowo has quit IRC
 12 2016-10-05T01:34:17  *** owowo has joined #bitcoin-core-dev
 13 2016-10-05T01:42:12  *** linuxfan2718 has joined #bitcoin-core-dev
 14 2016-10-05T02:03:39  <wumpus> MSG_FILTERED_WITNESS_BLOCK defined in protocol.h is neither used in our source code nor defined in any BIP, should be in BIP144 I guess?
 15 2016-10-05T02:10:17  *** paveljanik has quit IRC
 16 2016-10-05T02:18:24  <wumpus> (looking up these numbers for documentation in protocol.h for #8880)
 17 2016-10-05T02:19:46  <luke-jr> if it's not used in code, why define it at all?
 18 2016-10-05T02:20:25  *** jtimon has quit IRC
 19 2016-10-05T02:20:36  <wumpus> I'd say to reserve the bit pattern, though this should happen in the BIP too
 20 2016-10-05T02:21:08  <luke-jr> ah, so we use the value, just via setting a bit instead of the enum key
 21 2016-10-05T02:21:46  <wumpus> that's my assumption. I haven't checked
 22 2016-10-05T02:36:29  <GitHub60> [bitcoin] EvertonMelo opened pull request #8886: Update build-unix.md (master...patch-1) https://github.com/bitcoin/bitcoin/pull/8886
 23 2016-10-05T02:49:11  *** xinxi has joined #bitcoin-core-dev
 24 2016-10-05T02:49:49  <xinxi> sipa: are you there?
 25 2016-10-05T02:50:17  <xinxi> I am wondering why Bitcoin Core does not store the blockchain in a distributed way to save space?
 26 2016-10-05T02:50:22  *** Chris_Stewart_5 has joined #bitcoin-core-dev
 27 2016-10-05T02:52:11  <wumpus> there are some ideas for adding range negotiation to the protocol, so that nodes can store different ranges of blocks
 28 2016-10-05T02:52:16  <wumpus> see e.g. last meeting notes
 29 2016-10-05T02:52:59  <wumpus> the answer to 'why' is always: because no one has designed/implemented this yet
 30 2016-10-05T02:53:14  <xinxi> So theoretically, it is possible.
 31 2016-10-05T02:53:16  <wumpus> in any case if you are short in space you can use pruning
 32 2016-10-05T02:53:26  <xinxi> And blocksize won't be a problem seriously.
 33 2016-10-05T02:53:49  <wumpus> you're confounding issues
 34 2016-10-05T02:54:21  <xinxi> Sure blocksize increase will cause other issues like network latency.
 35 2016-10-05T02:54:48  <wumpus> increasing block size is a problem for utxo set growth, for the time it takes to initially sync, for bandwidth requirements of nodes and miners, for CPU validation overhead. Storing the block chain is the least of worries really
 36 2016-10-05T02:55:06  <wumpus> anyhow move this to #bitcoin, this is off topic here
 37 2016-10-05T02:55:12  <xinxi> OK
 38 2016-10-05T02:56:04  <xinxi> Thank you.
 39 2016-10-05T02:59:50  <xinxi> Another question directly about Bitcoin's current protocol.
 40 2016-10-05T03:00:17  <xinxi> Is it possible to increase OP_RETURN's data size with a softfork?
 41 2016-10-05T03:00:35  <wumpus> this topic is about development, discussion about changing the source code, use #bitcoin for general questions
 42 2016-10-05T03:00:40  <wumpus> see topic ^^
 43 2016-10-05T03:03:05  *** bsm117532 is now known as Guest26311
 44 2016-10-05T03:07:53  <GitHub168> [bitcoin] laanwj pushed 2 new commits to master: https://github.com/bitcoin/bitcoin/compare/d7615af34e8e...f92805025d5b
 45 2016-10-05T03:07:53  <GitHub168> bitcoin/master eeeebdd MarcoFalke: [doc] Rework docs...
 46 2016-10-05T03:07:54  <GitHub168> bitcoin/master f928050 Wladimir J. van der Laan: Merge #8879: [doc] Rework docs...
 47 2016-10-05T03:08:03  <GitHub181> [bitcoin] laanwj closed pull request #8879: [doc] Rework docs (master...Mf1610-docCleanup) https://github.com/bitcoin/bitcoin/pull/8879
 48 2016-10-05T03:12:30  <wumpus> sigh... https://github.com/bitcoin/bitcoin/pull/8886#discussion_r81892323
 49 2016-10-05T03:15:20  <GitHub173> [bitcoin] fanquake opened pull request #8887: [Doc] Improve GitHub issue template (master...link-stackexchange) https://github.com/bitcoin/bitcoin/pull/8887
 50 2016-10-05T03:17:34  *** btcdrak has quit IRC
 51 2016-10-05T03:17:48  *** xinxi has quit IRC
 52 2016-10-05T03:18:24  *** xinxi has joined #bitcoin-core-dev
 53 2016-10-05T03:18:57  *** Chris_Stewart_5 has quit IRC
 54 2016-10-05T03:19:48  *** Giszmo has quit IRC
 55 2016-10-05T03:23:18  *** xinxi has quit IRC
 56 2016-10-05T03:26:05  <GitHub91> [bitcoin] theuni opened pull request #8888: CConnman: Remove global usage in wallet and some gui (master...no-global-connman) https://github.com/bitcoin/bitcoin/pull/8888
 57 2016-10-05T03:26:24  *** xinxi has joined #bitcoin-core-dev
 58 2016-10-05T03:33:22  <achow101> the values for MSG_WITNESS_BLOCK and MSG_WITNESS_TX should probably be defined in BIP144...
 59 2016-10-05T03:34:42  <wumpus> good point achow101
 60 2016-10-05T03:51:07  *** paveljanik has joined #bitcoin-core-dev
 61 2016-10-05T04:00:00  <luke-jr> wumpus: wtf @ 8886
 62 2016-10-05T04:10:50  *** molz has quit IRC
 63 2016-10-05T04:17:45  *** xinxi_ has joined #bitcoin-core-dev
 64 2016-10-05T04:20:52  *** xinxi has quit IRC
 65 2016-10-05T04:40:12  *** linuxfan2718 has quit IRC
 66 2016-10-05T04:47:24  <GitHub22> [bitcoin] luke-jr opened pull request #8889: Qt/ModalOverlay: Use theme tooltip colours (master...overlay_theme) https://github.com/bitcoin/bitcoin/pull/8889
 67 2016-10-05T04:55:28  <NicolasDorier> sipa: about PrecomputedTransactionData, I noticed you calculate it even if the Transaction has no witness https://github.com/bitcoin/bitcoin/blob/d93f0c61843f9da2a662f54ea1794ae0d263b196/src/main.cpp#L2458 I don't know if it has big impact on performance during IBT. Just dropping it here in case you overlooked it
 68 2016-10-05T04:55:44  <NicolasDorier> IBD
 69 2016-10-05T04:59:22  *** DigiByteDev has joined #bitcoin-core-dev
 70 2016-10-05T05:07:19  <GitHub117> [bitcoin] fanquake opened pull request #8890: [Doc] Update Doxygen configuration file (master...update-doxyfile-1-8-12) https://github.com/bitcoin/bitcoin/pull/8890
 71 2016-10-05T05:17:50  *** xinxi_ has quit IRC
 72 2016-10-05T05:17:54  <sipa> wumpus: i guess MSG_FILTERED_WITNESS_BLOCK is what we'd need for a bip37 extension with segwit data
 73 2016-10-05T05:18:35  <sipa> NicolasDorier: yes, i'm aware
 74 2016-10-05T05:34:21  *** Alopex has quit IRC
 75 2016-10-05T05:34:40  *** xinxi has joined #bitcoin-core-dev
 76 2016-10-05T05:35:26  *** Alopex has joined #bitcoin-core-dev
 77 2016-10-05T05:42:08  *** jl2012 has quit IRC
 78 2016-10-05T05:45:11  *** Alopex has quit IRC
 79 2016-10-05T05:46:12  *** jl2012 has joined #bitcoin-core-dev
 80 2016-10-05T05:46:16  *** Alopex has joined #bitcoin-core-dev
 81 2016-10-05T05:47:46  *** moli has joined #bitcoin-core-dev
 82 2016-10-05T05:52:53  *** molz has joined #bitcoin-core-dev
 83 2016-10-05T05:56:19  *** moli has quit IRC
 84 2016-10-05T05:58:51  *** molz has quit IRC
 85 2016-10-05T05:58:55  *** juscamarena has joined #bitcoin-core-dev
 86 2016-10-05T06:01:45  *** moli has joined #bitcoin-core-dev
 87 2016-10-05T06:13:57  *** DigiByteDev has quit IRC
 88 2016-10-05T06:20:58  *** DigiByteDev has joined #bitcoin-core-dev
 89 2016-10-05T06:35:02  *** btcdrak has joined #bitcoin-core-dev
 90 2016-10-05T06:37:58  *** BashCo has quit IRC
 91 2016-10-05T06:40:24  *** xinxi has quit IRC
 92 2016-10-05T06:44:19  *** juscamarena has quit IRC
 93 2016-10-05T06:58:39  <wumpus> sipa: makes sense
 94 2016-10-05T07:01:52  <wumpus> luke-jr: I suspect it's a very young person and someone that doesn't know English very well, and he's just trying to be helpful. But indeed, wtf
 95 2016-10-05T07:09:17  *** BashCo has joined #bitcoin-core-dev
 96 2016-10-05T07:09:39  *** rubensayshi has joined #bitcoin-core-dev
 97 2016-10-05T07:11:32  <wumpus> and indeed, in fact most of build-unix.md is about linux distros, and the only UNIX that gets mentioned separately has its own document (openbsd), but no, adding kernel versions will not clarify that in any way :)
 98 2016-10-05T07:13:25  * wumpus goes to add a section about FreeBSD to balance it out
 99 2016-10-05T07:17:06  *** MarcoFalke has joined #bitcoin-core-dev
100 2016-10-05T07:18:01  *** shesek has quit IRC
101 2016-10-05T07:19:09  *** harrymm has quit IRC
102 2016-10-05T07:19:32  *** paveljanik has quit IRC
103 2016-10-05T07:19:56  *** Ylbam has joined #bitcoin-core-dev
104 2016-10-05T07:45:53  *** laurentmt has joined #bitcoin-core-dev
105 2016-10-05T07:47:06  *** laurentmt has quit IRC
106 2016-10-05T07:54:23  *** laurentmt has joined #bitcoin-core-dev
107 2016-10-05T08:13:21  *** laurentmt has quit IRC
108 2016-10-05T08:14:32  *** dcousens has joined #bitcoin-core-dev
109 2016-10-05T08:14:52  <dcousens> btcdrak: "uncompressed keys which are disallowed under segwit.", interesting,  no issue but can't find that in the BIP?
110 2016-10-05T08:16:37  <btcdrak> dcousens: because it is too late to change the consensus layer without causing delays, so it is implemented as policy for now and consider for future sf.
111 2016-10-05T08:16:56  <btcdrak> see last meetung notes
112 2016-10-05T08:17:00  <dcousens> btcdrak: ok, sweet, will do
113 2016-10-05T08:18:46  <dcousens> btcdrak: seen in notes, cheers ;)
114 2016-10-05T08:22:02  <btcdrak> I think we will make a note in the BIP bow, thanks.
115 2016-10-05T08:23:46  <wumpus> maybe, though it should be very clear that it is policy and not consensus then
116 2016-10-05T08:24:45  <gmaxwell> My suggestion is that it should state that it's policy created with the intent of making it consensus in a future softfork.
117 2016-10-05T08:30:14  <wumpus> or already create a BIP for such a future softfork, although that may be premature if it's to be combined with other things that may still come to light using this in the wild
118 2016-10-05T08:31:06  <gmaxwell> Well we can do like we did with CSV, we had three BIPs triggered on one bit.
119 2016-10-05T08:31:13  <wumpus> indeed. true.
120 2016-10-05T08:31:20  <gmaxwell> The thing I'd combine it with would be low-S enforcement.
121 2016-10-05T08:32:42  <dcousens> gmaxwell: agreed
122 2016-10-05T08:32:46  <wumpus> yes that would make sense, it's a comparable thing
123 2016-10-05T08:33:39  <gmaxwell> (low-S doesn't have the blowing up anyone's pubkey risk, though, and already IsStandard for non-segwit, so no need to warn about it.)
124 2016-10-05T08:34:34  <dcousens> btcdrak: that was uncompressed rejection only in witnesses,  or even in regular scriptSigs?
125 2016-10-05T08:35:50  <luke-jr> indeed, node policy isn't something BIPs should cover, except in the case of it being preparation for a softfork
126 2016-10-05T08:36:28  <btcdrak> dcousens: only for segwit
127 2016-10-05T08:36:30  <dcousens> or I suppose the question is targeted at the idea in general,  would it be a soft-fork to reject all uncompressed keys? Or only uncompressed keys in witness scripts
128 2016-10-05T08:36:34  <luke-jr> dcousens: only in witnesses; it'd break compatibility otherwise
129 2016-10-05T08:37:01  <dcousens> ok
130 2016-10-05T08:52:13  <gmaxwell> dcousens: I would be reasonable for a library to strongly discourage uncompressed keys in whatever ways it can do so without breaking things.
131 2016-10-05T08:53:11  <dcousens> gmaxwell: indeed,  defaults are almost all against it now anyway... but I think by the time that soft-fork came around, it'd be something I'd probably move into the "hard enough to do you have to do it manually" camp
132 2016-10-05T08:53:24  <dcousens> rather than just flick a switch
133 2016-10-05T08:55:35  <gmaxwell> we can't,  unfortunately, get rid of uncompressed keys for non-segwit, as that would confiscate coins. But for segwit we can so long as it's clearly non-kosher from the start.
134 2016-10-05T08:56:41  <dcousens> gmaxwell: hmmm, I suppose that is risky,  but I can see some actors aggrevating the issue for agendas
135 2016-10-05T08:58:15  <GitHub50> [bitcoin] fanquake opened pull request #8891: [Doc] Update bips.md for Segregated Witness (master...segwit-bips-md) https://github.com/bitcoin/bitcoin/pull/8891
136 2016-10-05T08:58:56  <gmaxwell> dcousens: changing things for existing keys is just completely impratical ... people with random uncompressed keys printed out... coins paid to them.. no idea that the keys are uncompressed.
137 2016-10-05T08:59:48  <dcousens> gmaxwell: I 100% agree its a good move,  I just wonder if its worth delaying instead of policy for a short time... probably already discussed in the meeting,  I'll look up the logs more in depth
138 2016-10-05T09:00:02  <dcousens> delaying segwit* (and then putting it in that SF)
139 2016-10-05T09:00:38  <gmaxwell> policy makes it safer.
140 2016-10-05T09:00:45  <GitHub135> [bitcoin] laanwj opened pull request #8892: doc: Add build instructions for FreeBSD (master...2016_10_freebsd_build) https://github.com/bitcoin/bitcoin/pull/8892
141 2016-10-05T09:00:59  <gmaxwell> even if its outright bard in SW some genius might still manage to send infinity coins to an invalid script
142 2016-10-05T09:01:16  <gmaxwell> with it non-standard, they could coordinate with miners to rescue them.
143 2016-10-05T09:01:19  *** harrymm has joined #bitcoin-core-dev
144 2016-10-05T09:02:00  <dcousens> gmaxwell: true, problematic from the start.  I suppose it's just one of things that might need some big bold writing and dates
145 2016-10-05T09:07:50  *** harrymm has quit IRC
146 2016-10-05T09:18:55  <wumpus> no, it's not worth delaying segwit
147 2016-10-05T09:19:30  <wumpus> there will always be some last-minutes things that could have been slightly better, don't let them delay what is a great improvement
148 2016-10-05T09:22:40  *** harrymm has joined #bitcoin-core-dev
149 2016-10-05T09:49:17  *** cdecker has joined #bitcoin-core-dev
150 2016-10-05T09:52:31  *** moli has quit IRC
151 2016-10-05T09:53:20  *** moli has joined #bitcoin-core-dev
152 2016-10-05T10:05:30  *** DigiByteDev has quit IRC
153 2016-10-05T10:36:09  *** BashCo has quit IRC
154 2016-10-05T10:36:13  <GitHub188> [bitcoin] laanwj closed pull request #8886: Add Arch Linux instructions to build-unix.md (master...patch-1) https://github.com/bitcoin/bitcoin/pull/8886
155 2016-10-05T10:37:08  *** DigiByteDev has joined #bitcoin-core-dev
156 2016-10-05T10:40:55  *** JackH_ has joined #bitcoin-core-dev
157 2016-10-05T10:42:13  *** DigiByteDev has quit IRC
158 2016-10-05T10:43:48  *** JackH has quit IRC
159 2016-10-05T10:46:55  *** DigiByteDev has joined #bitcoin-core-dev
160 2016-10-05T10:47:28  *** DigiByteDev has quit IRC
161 2016-10-05T11:07:01  *** Ylbam has quit IRC
162 2016-10-05T11:17:37  *** jannes has joined #bitcoin-core-dev
163 2016-10-05T11:25:19  *** BashCo has joined #bitcoin-core-dev
164 2016-10-05T11:46:25  <wumpus> achow101: https://github.com/bitcoin/bips/pull/457
165 2016-10-05T11:58:12  *** cryptapus has joined #bitcoin-core-dev
166 2016-10-05T11:58:12  *** cryptapus has joined #bitcoin-core-dev
167 2016-10-05T11:58:42  *** cryptapus has joined #bitcoin-core-dev
168 2016-10-05T12:00:09  *** cryptapus has quit IRC
169 2016-10-05T12:04:48  *** jtimon has joined #bitcoin-core-dev
170 2016-10-05T12:04:49  *** cryptapus has joined #bitcoin-core-dev
171 2016-10-05T12:04:50  *** cryptapus has joined #bitcoin-core-dev
172 2016-10-05T12:12:25  *** laurentmt has joined #bitcoin-core-dev
173 2016-10-05T12:19:57  *** paveljanik has joined #bitcoin-core-dev
174 2016-10-05T12:19:57  *** paveljanik has joined #bitcoin-core-dev
175 2016-10-05T12:32:36  *** laurentmt has quit IRC
176 2016-10-05T12:44:32  <GitHub79> [bitcoin] laanwj pushed 2 new commits to master: https://github.com/bitcoin/bitcoin/compare/f92805025d5b...223f4c2dd5fa
177 2016-10-05T12:44:32  <GitHub79> bitcoin/master a78e542 Luke Dashjr: Bugfix: Trivial: RPC: getblockchaininfo help: pruneheight is the lowest, not highest, block
178 2016-10-05T12:44:33  <GitHub79> bitcoin/master 223f4c2 Wladimir J. van der Laan: Merge #8884: Bugfix: Trivial: RPC: getblockchaininfo help: pruneheight is the lowest, not highest, block...
179 2016-10-05T12:44:47  <GitHub78> [bitcoin] laanwj closed pull request #8884: Bugfix: Trivial: RPC: getblockchaininfo help: pruneheight is the lowest, not highest, block (master...trivial_pruneheight_help) https://github.com/bitcoin/bitcoin/pull/8884
180 2016-10-05T12:48:14  *** droark has quit IRC
181 2016-10-05T12:57:27  *** cryptapus_ has joined #bitcoin-core-dev
182 2016-10-05T12:57:45  *** cryptapus has quit IRC
183 2016-10-05T12:59:42  *** Chris_Stewart_5 has joined #bitcoin-core-dev
184 2016-10-05T13:04:06  *** JackH_ has quit IRC
185 2016-10-05T13:05:18  *** jnewbery has joined #bitcoin-core-dev
186 2016-10-05T13:09:15  *** laurentmt has joined #bitcoin-core-dev
187 2016-10-05T13:12:00  *** cryptapus_ is now known as cryptapus
188 2016-10-05T13:12:05  *** Chris_Stewart_5 has quit IRC
189 2016-10-05T13:13:28  *** Chris_Stewart_5 has joined #bitcoin-core-dev
190 2016-10-05T13:39:37  *** waxwing has joined #bitcoin-core-dev
191 2016-10-05T13:41:18  *** Chris_Stewart_5 has quit IRC
192 2016-10-05T13:47:26  *** Guyver2 has joined #bitcoin-core-dev
193 2016-10-05T13:54:47  *** laurentmt has quit IRC
194 2016-10-05T13:55:53  *** arowser has quit IRC
195 2016-10-05T13:55:53  *** Chris_Stewart_5 has joined #bitcoin-core-dev
196 2016-10-05T13:56:29  *** arowser has joined #bitcoin-core-dev
197 2016-10-05T14:12:51  *** Chris_Stewart_5 has quit IRC
198 2016-10-05T14:16:33  *** dcousens has quit IRC
199 2016-10-05T14:28:29  *** Chris_Stewart_5 has joined #bitcoin-core-dev
200 2016-10-05T14:29:28  *** Giszmo has joined #bitcoin-core-dev
201 2016-10-05T14:37:06  *** Chris_Stewart_5 has quit IRC
202 2016-10-05T14:38:44  *** arowser has quit IRC
203 2016-10-05T14:38:45  *** BashCo has quit IRC
204 2016-10-05T14:38:45  *** moli has quit IRC
205 2016-10-05T14:38:46  *** jl2012 has quit IRC
206 2016-10-05T14:38:47  *** Expanse has quit IRC
207 2016-10-05T14:38:47  *** davec has quit IRC
208 2016-10-05T14:38:48  *** wasi has quit IRC
209 2016-10-05T14:38:48  *** Evel-Knievel has quit IRC
210 2016-10-05T14:38:48  *** achow101 has quit IRC
211 2016-10-05T14:38:48  *** musalbas has quit IRC
212 2016-10-05T14:38:49  *** sdaftuar has quit IRC
213 2016-10-05T14:38:49  *** Guest62318 has quit IRC
214 2016-10-05T14:38:49  *** aalex has quit IRC
215 2016-10-05T14:38:49  *** nsh_ has quit IRC
216 2016-10-05T14:38:50  *** Anduck has quit IRC
217 2016-10-05T14:39:11  *** Evel-Knievel has joined #bitcoin-core-dev
218 2016-10-05T14:39:12  *** arowser has joined #bitcoin-core-dev
219 2016-10-05T14:39:12  *** sdaftuar has joined #bitcoin-core-dev
220 2016-10-05T14:39:17  *** achow101 has joined #bitcoin-core-dev
221 2016-10-05T14:39:17  *** wasi has joined #bitcoin-core-dev
222 2016-10-05T14:39:22  *** BashCo has joined #bitcoin-core-dev
223 2016-10-05T14:39:24  *** Anduck has joined #bitcoin-core-dev
224 2016-10-05T14:39:28  *** stan_ has joined #bitcoin-core-dev
225 2016-10-05T14:39:57  *** moli has joined #bitcoin-core-dev
226 2016-10-05T14:40:01  *** musalbas has joined #bitcoin-core-dev
227 2016-10-05T14:41:29  *** jl2012 has joined #bitcoin-core-dev
228 2016-10-05T14:41:35  *** aalex has joined #bitcoin-core-dev
229 2016-10-05T14:45:04  *** ensign has joined #bitcoin-core-dev
230 2016-10-05T14:48:57  *** davec has joined #bitcoin-core-dev
231 2016-10-05T14:53:50  *** Expanse has joined #bitcoin-core-dev
232 2016-10-05T15:07:08  *** moli has quit IRC
233 2016-10-05T15:07:52  *** moli has joined #bitcoin-core-dev
234 2016-10-05T15:25:49  *** Sosumi has joined #bitcoin-core-dev
235 2016-10-05T15:26:59  *** droark has joined #bitcoin-core-dev
236 2016-10-05T15:27:35  *** moli has quit IRC
237 2016-10-05T15:32:44  *** moli has joined #bitcoin-core-dev
238 2016-10-05T15:35:26  *** NLNico has joined #bitcoin-core-dev
239 2016-10-05T15:37:18  *** laurentmt has joined #bitcoin-core-dev
240 2016-10-05T15:48:33  *** laurentmt has quit IRC
241 2016-10-05T15:50:13  *** Guest26311 is now known as bsm117532
242 2016-10-05T15:53:13  *** rubensayshi has quit IRC
243 2016-10-05T15:53:22  *** MarcoFalke has left #bitcoin-core-dev
244 2016-10-05T15:54:21  <Lauda> Any estimate for 0.13.1 yet?
245 2016-10-05T15:56:31  <sipa> soon.
246 2016-10-05T15:56:46  <instagibbs> Two Weeks(TM)
247 2016-10-05T15:57:23  <sipa> TW
248 2016-10-05T15:57:31  <sipa> not TM, i hope
249 2016-10-05T15:57:33  <Lauda> I dislike the word soon as it can mean anywhere between now and sometime in the distant future. :P
250 2016-10-05T15:57:45  <sipa> Lauda: that is exactly what it meams
251 2016-10-05T15:57:57  <sipa> there are very few remaining issues
252 2016-10-05T15:58:28  <achow101> Lauda: as soon as everything in the milestone is taken care of
253 2016-10-05T15:58:47  <Lauda> tl;dr: Soon.
254 2016-10-05T15:59:03  <Lauda> I've checked the milestone not long ago.
255 2016-10-05T15:59:15  <achow101> they keep adding new stuff
256 2016-10-05T16:00:36  *** moli has quit IRC
257 2016-10-05T16:04:24  *** jnewbery has quit IRC
258 2016-10-05T16:06:22  *** moli has joined #bitcoin-core-dev
259 2016-10-05T16:16:25  <cdecker> Soon is still better than 'eventually' :-)
260 2016-10-05T16:32:04  *** jnewbery has joined #bitcoin-core-dev
261 2016-10-05T16:34:36  <instagibbs> achow101, people can ask for milestone tags, may not happen tho
262 2016-10-05T16:34:44  *** Chris_Stewart_5 has joined #bitcoin-core-dev
263 2016-10-05T16:34:44  <instagibbs> a number have been pruned off already
264 2016-10-05T16:39:55  *** Chris_Stewart_5 has quit IRC
265 2016-10-05T16:44:36  *** To7 has joined #bitcoin-core-dev
266 2016-10-05T16:46:13  *** Chris_Stewart_5 has joined #bitcoin-core-dev
267 2016-10-05T16:49:12  *** xiangfu has quit IRC
268 2016-10-05T16:49:33  *** xiangfu has joined #bitcoin-core-dev
269 2016-10-05T17:06:15  *** laurentmt has joined #bitcoin-core-dev
270 2016-10-05T17:09:55  *** arowser has quit IRC
271 2016-10-05T17:10:44  *** laurentmt has quit IRC
272 2016-10-05T17:12:10  *** arowser has joined #bitcoin-core-dev
273 2016-10-05T17:16:47  *** jtimon has quit IRC
274 2016-10-05T17:19:22  *** droark has quit IRC
275 2016-10-05T17:28:25  *** droark has joined #bitcoin-core-dev
276 2016-10-05T17:31:13  *** Ylbam has joined #bitcoin-core-dev
277 2016-10-05T17:35:27  *** moli has quit IRC
278 2016-10-05T17:44:49  *** droark has quit IRC
279 2016-10-05T17:46:32  *** e4xit has quit IRC
280 2016-10-05T17:46:39  *** cryptapus_ has joined #bitcoin-core-dev
281 2016-10-05T17:46:39  *** cryptapus_ has joined #bitcoin-core-dev
282 2016-10-05T17:47:40  *** e4xit has joined #bitcoin-core-dev
283 2016-10-05T17:50:20  *** cryptapus has quit IRC
284 2016-10-05T17:50:34  *** Chris_Stewart_5 has quit IRC
285 2016-10-05T17:51:14  *** shesek has joined #bitcoin-core-dev
286 2016-10-05T17:52:46  *** Chris_Stewart_5 has joined #bitcoin-core-dev
287 2016-10-05T17:53:15  *** cryptapus_ has quit IRC
288 2016-10-05T17:54:02  *** spudowiar has joined #bitcoin-core-dev
289 2016-10-05T17:55:09  *** NLNico has quit IRC
290 2016-10-05T17:56:46  *** spudowiar has quit IRC
291 2016-10-05T17:58:59  *** cryptapus_ has joined #bitcoin-core-dev
292 2016-10-05T18:01:54  <cfields_> jonasschnelli: ping
293 2016-10-05T18:02:02  *** jouke has joined #bitcoin-core-dev
294 2016-10-05T18:14:32  *** Evel-Knievel has quit IRC
295 2016-10-05T18:15:23  *** jtimon has joined #bitcoin-core-dev
296 2016-10-05T18:21:30  *** ensign is now known as rexnsh
297 2016-10-05T18:26:13  *** cryptapus_ has quit IRC
298 2016-10-05T18:31:30  <GitHub16> [bitcoin] jnewbery opened pull request #8894: [Testing] Include fRelay in mininode version messages (master...mininode-relay-field) https://github.com/bitcoin/bitcoin/pull/8894
299 2016-10-05T18:35:41  *** wasi has quit IRC
300 2016-10-05T18:40:43  *** Chris_Stewart_5 has quit IRC
301 2016-10-05T18:47:39  *** wasi has joined #bitcoin-core-dev
302 2016-10-05T18:54:47  *** Chris_Stewart_5 has joined #bitcoin-core-dev
303 2016-10-05T19:14:18  *** Chris_Stewart_5 has quit IRC
304 2016-10-05T19:17:12  *** cryptapus has joined #bitcoin-core-dev
305 2016-10-05T19:42:19  *** jannes has quit IRC
306 2016-10-05T19:52:40  *** h1d has joined #bitcoin-core-dev
307 2016-10-05T19:54:20  *** h1d has quit IRC
308 2016-10-05T19:59:09  *** stan_ has quit IRC
309 2016-10-05T19:59:24  *** stan_ has joined #bitcoin-core-dev
310 2016-10-05T20:04:49  *** cryptapus has quit IRC
311 2016-10-05T20:35:49  *** alpalp has joined #bitcoin-core-dev
312 2016-10-05T20:44:21  *** alpalp has quit IRC
313 2016-10-05T20:44:44  *** alpalp has joined #bitcoin-core-dev
314 2016-10-05T20:53:03  *** Evel-Knievel has joined #bitcoin-core-dev
315 2016-10-05T20:54:59  *** laurentmt has joined #bitcoin-core-dev
316 2016-10-05T20:58:19  *** alpalp has quit IRC
317 2016-10-05T21:10:11  *** Chris_Stewart_5 has joined #bitcoin-core-dev
318 2016-10-05T21:19:26  *** meowzus has joined #bitcoin-core-dev
319 2016-10-05T21:26:23  *** randy-waterhouse has joined #bitcoin-core-dev
320 2016-10-05T21:26:41  *** randy-waterhouse has joined #bitcoin-core-dev
321 2016-10-05T21:28:56  *** laurentmt has quit IRC
322 2016-10-05T21:31:06  *** shesek has quit IRC
323 2016-10-05T21:32:59  *** paveljanik has quit IRC
324 2016-10-05T21:34:20  *** paveljanik has joined #bitcoin-core-dev
325 2016-10-05T21:35:30  *** jnewbery has quit IRC
326 2016-10-05T21:35:55  *** jnewbery has joined #bitcoin-core-dev
327 2016-10-05T21:36:00  *** shesek has joined #bitcoin-core-dev
328 2016-10-05T21:38:24  *** Guyver2 has quit IRC
329 2016-10-05T21:51:32  <GitHub134> [bitcoin] JeremyRubin opened pull request #8895: Better SigCache Implementation (master...cuckoocache-pull-request) https://github.com/bitcoin/bitcoin/pull/8895
330 2016-10-05T21:52:40  <jeremyrubin> \me \o/
331 2016-10-05T21:52:48  * jeremyrubin \o/
332 2016-10-05T21:53:57  <sipa> this is not \LaTeX
333 2016-10-05T21:54:34  <gmaxwell> oh good. someone implement a Cuckoo Hash Table... now we need a lossy version and can get rid of those cahe destroying huge bloom filters we're using all over the place.
334 2016-10-05T21:55:40  <jeremyrubin> sipa: latex irc plugin would be dope
335 2016-10-05T21:56:05  <sipa> jeremyrubin:
336 2016-10-05T21:56:11  <jeremyrubin> $\mu$'s eveywhere
337 2016-10-05T21:56:31  <sipa> ỉţ ẅờữľđ çëřŧẩîńļŷ șïḿpľìƒỹ ẁřîŧīňğ ťẽxŧ ŵíţĥ ĺốţš ôƒ ďīäćŗìťĩčș
338 2016-10-05T21:56:56  <jeremyrubin> gmaxwell: this is a lossy version
339 2016-10-05T21:58:27  <gmaxwell> whats lossy about it? looks like if there is a collision you ripple, like an ordinary cuckoo hash.
340 2016-10-05T21:58:43  <jeremyrubin> gmaxwell: once depth is reached, last thing touched goes bye-bye
341 2016-10-05T21:58:56  <jeremyrubin> gmaxwell: no rehashing
342 2016-10-05T21:59:32  <gmaxwell> Did you test if that optimization mattered? I think if makes a difference at all, your table is over populated and the performance will be poor.
343 2016-10-05T21:59:47  <bsm117532> https://sourceforge.net/projects/pidgin-latex/
344 2016-10-05T22:00:05  <gmaxwell> (because if it makes a difference it means you are hitting the limit often, and if you're doing that you're probably doing it for almost every insert.)
345 2016-10-05T22:00:49  *** gmaxwell is now known as gmaxwell_
346 2016-10-05T22:01:39  *** stan_ has quit IRC
347 2016-10-05T22:01:50  *** gmaxwell_ is now known as gmaxwell
348 2016-10-05T22:01:58  <jeremyrubin> gmaxwell_: I tested many many optimizations... not that one because I have a fixed size table so rehashing can't help
349 2016-10-05T22:02:12  *** timothy has quit IRC
350 2016-10-05T22:02:13  *** stan_ has joined #bitcoin-core-dev
351 2016-10-05T22:02:14  *** drizztbsd has joined #bitcoin-core-dev
352 2016-10-05T22:02:20  <jeremyrubin> gmaxwell: ^^^
353 2016-10-05T22:02:33  <gmaxwell> jeremyrubin: what you need to do if you hit the maximum then is go delete entries at random.
354 2016-10-05T22:02:45  *** drizztbsd is now known as timothy
355 2016-10-05T22:02:55  <jeremyrubin> gmaxwell: I did however test with more hashes per entry (10)
356 2016-10-05T22:03:05  <kanzure> is it correct that 8393 should be marked "needs backport" ? https://github.com/bitcoin/bitcoin/pull/8393#issuecomment-238783829
357 2016-10-05T22:03:18  <gmaxwell> If you look at a cuckoo hash number of expected accesses as a function of table fullness, you get this behavior where it's basically 2 until the table is half full and then it shoots up like a rocket.
358 2016-10-05T22:03:30  <jeremyrubin> Yeah
359 2016-10-05T22:03:41  <jeremyrubin> so fortunately insert performance isn't a large priority
360 2016-10-05T22:03:50  <sipa> with 3 hashes you can get to 90% full :)
361 2016-10-05T22:03:50  <gmaxwell> So your depth limit means that you'll never hit it until you're too full, then you'll often hit it.
362 2016-10-05T22:04:17  <jeremyrubin> and we'd rather spend the compute poking around the table looking for things that have been deleted than clear something that hasn't been deleted
363 2016-10-05T22:04:34  <jeremyrubin> So the "eager-delete" strategy is a loser
364 2016-10-05T22:04:45  <jeremyrubin> sipa: yes, but on a non-fixed memory system
365 2016-10-05T22:04:52  <sipa> ?
366 2016-10-05T22:05:04  <jeremyrubin> *non-fixed
367 2016-10-05T22:05:14  <jeremyrubin> eg, you can get to 90% before needing a re-hash
368 2016-10-05T22:05:21  <jeremyrubin> but we never increase memory size
369 2016-10-05T22:05:28  <jeremyrubin> so we always get to 100% full
370 2016-10-05T22:05:36  <jeremyrubin> it's just a matter of how fast
371 2016-10-05T22:06:18  <jeremyrubin> There are gains to be made with more hashes/other things I agree. I'm pretty excited about some of them, but this is minimal & those all add some uneeded complexity
372 2016-10-05T22:06:38  *** stan_ has quit IRC
373 2016-10-05T22:06:46  <gmaxwell> jeremyrubin: what is the depth limit you're using?
374 2016-10-05T22:06:54  <jeremyrubin> log(size)
375 2016-10-05T22:07:26  <gmaxwell> yea, so you're going to end up doing log() accesses on insert basically every time once its run long enough.
376 2016-10-05T22:07:56  <jeremyrubin> Yeah that's fine
377 2016-10-05T22:08:08  <jeremyrubin> We don't really care about insert performance (non-hot path)
378 2016-10-05T22:08:43  <jeremyrubin> And we also do care about deleting things that have been erased preferentially (rather than randomly)
379 2016-10-05T22:08:55  <jeremyrubin> so it's worth it.
380 2016-10-05T22:10:09  <sipa> jeremyrubin: i see
381 2016-10-05T22:11:03  *** droark has joined #bitcoin-core-dev
382 2016-10-05T22:14:41  <jeremyrubin> besides, log2(40mb/32bytes per entry) ~~ 21 which is not trivial, but not huge by any means
383 2016-10-05T22:15:26  <gmaxwell> it's a lot of random memory accesses.
384 2016-10-05T22:16:29  <jeremyrubin> gmaxwell: I tested designs that did less random mem accesses and it wasn't terribly better for much added complexity
385 2016-10-05T22:16:52  <jeremyrubin> gmaxwell: I'll float those later if this gets through review
386 2016-10-05T22:17:30  <jeremyrubin> gmaxwell: for instance, one can split keys to an 8-bit tag and 258-bit main value, and do initial lookups on the tags.
387 2016-10-05T22:18:06  <gmaxwell> what matters is the access, 1-64 bytes (and likely 1-128 bytes) will all end up being basically the same speed.
388 2016-10-05T22:18:22  <jeremyrubin> gmaxwell: you can also do buckets of two hashes so that k can be stored at h0(k) & ~1 and h0(k) | 1.
389 2016-10-05T22:18:32  <jeremyrubin> gmaxwell: wrong. l1/l2 matters at that size
390 2016-10-05T22:19:06  <jeremyrubin> gmaxwell: you can also do linear probing style stuff with 64 entries per bucket (and say, 2 buckets per entry allowed) and 1 byte tags
391 2016-10-05T22:19:44  <jeremyrubin> (I implemented and tested all of the above, none are a clear winner over the K.I.S.S. solution PR'd)
392 2016-10-05T22:21:55  <sipa> (h0(k) & 1, h0(k) | 1) won't result in a cuckoo style behaviour, i think
393 2016-10-05T22:22:05  <sipa> as the collisions are perfectly correlated
394 2016-10-05T22:22:11  <gmaxwell> no, it won't.
395 2016-10-05T22:22:37  <jeremyrubin> sipa: that's why you have two hashes still
396 2016-10-05T22:22:42  <jeremyrubin> sorry if that was unclear
397 2016-10-05T22:22:48  <sipa> ah, you mean in addition
398 2016-10-05T22:22:50  <sipa> right
399 2016-10-05T22:22:54  <jeremyrubin> yes
400 2016-10-05T22:23:04  <gmaxwell> but this table doesn't really make use of cuckoo style behavior once it fills.
401 2016-10-05T22:23:10  <sipa> you're turning each entry into a 2-way associativr cache
402 2016-10-05T22:23:12  <gmaxwell> it just becomes a 2-way set assc cache.
403 2016-10-05T22:23:22  <jeremyrubin> sure
404 2016-10-05T22:24:02  *** instagibbs has quit IRC
405 2016-10-05T22:24:20  <jeremyrubin> gmaxwell: more or less the same thing
406 2016-10-05T22:24:38  <sipa> what would be the effect if you greatly reduced the max iterations?
407 2016-10-05T22:24:48  <jeremyrubin> less likely to find garbage on insert
408 2016-10-05T22:24:48  <sipa> (in the otherwise kiss design)
409 2016-10-05T22:25:24  <sipa> so why bother doing 21 iterations?
410 2016-10-05T22:25:35  <gmaxwell> Well I'm saying this cuckoo table is a not one, at least once filled it's a two way set assc cache.  I think you can probably make your insert behavior stop at the first collision once you're over some fullness threshold (like 90%) and you'll see performance improve.
411 2016-10-05T22:26:18  <BlueMatt> remember: we really give 0 shits about insert performance....ATMP isnt our hot-path, and it just did sigchecks, so a bunch of lookups (even hitting memory) isnt all that bad
412 2016-10-05T22:26:18  <gmaxwell> sorry if I didn't state it clearly above: this data structure is a cucokoo hash table that turns into a 2way set assc cache once it becomes overfull
413 2016-10-05T22:26:32  <gmaxwell> BlueMatt: I'm also thinking about other places where we should use this.
414 2016-10-05T22:26:40  <BlueMatt> ahh, ok, fair enough
415 2016-10-05T22:26:44  <gmaxwell> And I care about the overall cpu usage of bitcoin, not just the block race. :)
416 2016-10-05T22:27:03  <gmaxwell> it looks like great work too, I'm not being negative, just thinking it through.
417 2016-10-05T22:27:09  <BlueMatt> ehh, doing a few more memory hits after doing ATMP checksigs isnt all that much too notice :p
418 2016-10-05T22:27:40  <jeremyrubin> sipa: Finding garbage means finding a signature you don't need again (unless reorg)
419 2016-10-05T22:27:45  <sipa> yes, in case it isn't clear, i'm just playing devil's advocate to understand
420 2016-10-05T22:28:04  <jeremyrubin> sipa: finding !garbage means you delete something maybe valuable
421 2016-10-05T22:28:23  <jeremyrubin> sipa: (yes :) )
422 2016-10-05T22:28:25  *** shesek has quit IRC
423 2016-10-05T22:28:32  <jeremyrubin> If i math'd right: (1-((5000/((float(40<<20)/(32.0+1.0/8))))))**21
424 2016-10-05T22:28:42  <gmaxwell> though I wonder if its code complexity wouldn't be reduced by dropping the cuckoo behavior entirely... thats a question that depends on how full the cache is typically.
425 2016-10-05T22:28:43  <jeremyrubin> == ~92%
426 2016-10-05T22:28:58  <jeremyrubin> should be chance of deleting with this design
427 2016-10-05T22:29:14  <jeremyrubin> gmaxwell: what is the cuckoo behavior? Eg, one hash location?
428 2016-10-05T22:29:27  <gmaxwell> jeremyrubin: no, cuckoo behavior is the rippling insertion.
429 2016-10-05T22:29:42  <jeremyrubin> gmaxwell: so not iterating at all?
430 2016-10-05T22:29:48  <gmaxwell> In a plain 2way set assc cache, you'll probe both locations on insert and if both are full you'll evict one (at random or whatever).
431 2016-10-05T22:29:54  <BlueMatt> gmaxwell: i think, here, thats motly there so that you can find entries marked deleted while rippling
432 2016-10-05T22:30:03  <BlueMatt> if you didnt have the delete flags, probably
433 2016-10-05T22:30:19  <gmaxwell> okay, I wasn't thinking about the delete flags, hows that work?
434 2016-10-05T22:30:34  <BlueMatt> its the sigcache - we used to delete things while checking sigs in blocks
435 2016-10-05T22:30:40  <BlueMatt> now they're marked for deletion in an atomic
436 2016-10-05T22:30:55  <BlueMatt> so jeremyrubin's thing goes through and treats slots as empty if they have a delete flag on insert
437 2016-10-05T22:30:56  <gmaxwell> I don't think that matters actually.
438 2016-10-05T22:31:07  <BlueMatt> this has an interesting benifit of making it so that reorgs at the tip might use sigcache
439 2016-10-05T22:31:09  <gmaxwell> When you go to insert, if either are free or marked delete, overwrite.
440 2016-10-05T22:31:22  <gmaxwell> otherwise pick one and overwrite.
441 2016-10-05T22:31:29  <gmaxwell> rippling at that point doesn't do you any good.
442 2016-10-05T22:31:40  <gmaxwell> the other entries you would delete will get deleted when something tries to insert in them.
443 2016-10-05T22:31:46  <jeremyrubin> yes it does? the next one might find a trash
444 2016-10-05T22:32:01  *** jnewbery has quit IRC
445 2016-10-05T22:32:15  <sipa> jeremyrubin: i see!
446 2016-10-05T22:32:20  <gmaxwell> I don't.
447 2016-10-05T22:32:24  <jeremyrubin> k1 and k2 sharing location X are highly unlikely to have another in common
448 2016-10-05T22:32:54  <gmaxwell> If I insert k1  and one of its locations contains trash, I'll use that location.
449 2016-10-05T22:33:06  <sipa> gmaxwell: if you iterate 21 times, you've had 21 independent chances of finding an empty/deleted position, so you don't need to evict anything potentially valua le
450 2016-10-05T22:33:10  <gmaxwell> I don't need someone to have come in front of me and taken out the trash for me, I can do it then.
451 2016-10-05T22:33:18  <jeremyrubin> eg, h1(k1) == h1(k2), unlikely h2(k1) != h2(k2)
452 2016-10-05T22:33:42  <gmaxwell> sipa: yes; thats equal to saying that cuckoo is helpful if the table is not overfull.
453 2016-10-05T22:34:15  <sipa> well, yes, but it won't be if many entries are marked deleted
454 2016-10-05T22:34:17  <gmaxwell> which it is, but if the table is normally more than 50% full, it doesn't help.
455 2016-10-05T22:34:36  <sipa> i think it can be way more than 50% full
456 2016-10-05T22:34:57  <jeremyrubin> will always go to 100% full
457 2016-10-05T22:35:00  <jeremyrubin> except after a block
458 2016-10-05T22:35:00  <gmaxwell> which is what I said above... depending on how full the table is (and by full I am counting trash as deleted), this could just be a set assc cache with no loss in performance.
459 2016-10-05T22:35:21  <sipa> if there are no deleted positions (or very few), agree
460 2016-10-05T22:35:40  <jeremyrubin> there are n_sigops(last_block) empty slots
461 2016-10-05T22:35:44  <BlueMatt> gmaxwell: by recursing you're less likely to throw out non-trash if there are delete positions available, this is esp true if you eg have blocks come in quickly in succession
462 2016-10-05T22:35:46  <gmaxwell> sipa: not just 'very few'. The benefit of cuckoo drops of exponentially after 50%.
463 2016-10-05T22:36:26  <gmaxwell> BlueMatt: not if the table is well over 50% full (deleted entries are not full in this measure).
464 2016-10-05T22:36:37  <sipa> gmaxwell: i believe that if you're 90% full, you have a very high chance that a new insert will end up with you consuming an empty position
465 2016-10-05T22:36:44  <jeremyrubin> This can be addressed by increasing hashes to 3 or 4 (or 10!)
466 2016-10-05T22:36:57  <jeremyrubin> not fact 10 just 10 excitement
467 2016-10-05T22:37:13  <BlueMatt> gmaxwell: indeed, though if you have quick blocks it means you're less full...
468 2016-10-05T22:37:14  <gmaxwell> yes, the table can run fuller if there are more probes, but with a linear slowdown for your lookup.
469 2016-10-05T22:37:37  <BlueMatt> as an aside: we could also add a few bits to indicate feerate for each entry, which would make the probing actually really matter
470 2016-10-05T22:37:53  <sipa> BlueMatt: or age
471 2016-10-05T22:37:57  <BlueMatt> or age
472 2016-10-05T22:38:02  <jeremyrubin> Yep
473 2016-10-05T22:38:04  <sipa> add generation numbers like the bloom filter cache
474 2016-10-05T22:38:07  <jeremyrubin> Yep
475 2016-10-05T22:38:09  <gmaxwell> sipa: I think you're overestimating it, when you're 90% full most entries end up in the posistion they're in because their sibling was alreaady full.
476 2016-10-05T22:38:24  <jeremyrubin> Or like.. clear them on eviction
477 2016-10-05T22:38:31  <sipa> gmaxwell: 0.9^21, no?
478 2016-10-05T22:39:32  <gmaxwell> sipa: no, because the when you consider entry X the current member is more likely to be in X because its alternate Y is full.  The sequence of tests are no longer independant.
479 2016-10-05T22:39:58  <jeremyrubin> Wait what?
480 2016-10-05T22:40:13  <gmaxwell> this is why the performance falls off so dramatically at over 50% full.
481 2016-10-05T22:40:13  <jeremyrubin> That's only true if we prefer h0 over h1?
482 2016-10-05T22:40:13  <BlueMatt> this is only true if your table is small compared to your iteration count?
483 2016-10-05T22:41:15  <jeremyrubin> Also... so what! If it's really such a big deal we can just clear 50% of things out from this one
484 2016-10-05T22:41:22  <jeremyrubin> and still be on par with existing :P
485 2016-10-05T22:41:24  <gmaxwell> BlueMatt: I'm responding to sipa saying that the odds you fail to find a free entry in 21 hops is 0.9^21
486 2016-10-05T22:41:34  <BlueMatt> gmaxwell: i mean it should be close
487 2016-10-05T22:41:41  <sipa> gmaxwell: i don't understand
488 2016-10-05T22:41:53  <sipa> gmaxwell: maybe we have different assumptions
489 2016-10-05T22:42:02  <jeremyrubin> I agree with sipa
490 2016-10-05T22:42:15  <jeremyrubin> my math was: ((1-((5000/((float(40<<20)/(32.0+1.0/8))))))**1)
491 2016-10-05T22:42:23  <jeremyrubin> oops last one should be a 21
492 2016-10-05T22:42:31  <BlueMatt> anyway, headed out, y'all figure it out and report back :P
493 2016-10-05T22:42:33  <jeremyrubin> for a block clearing 5k things
494 2016-10-05T22:43:13  <jeremyrubin> Gonna head out for some dinner; looking forward to hearing more of your thoughts.
495 2016-10-05T22:43:28  *** shesek has joined #bitcoin-core-dev
496 2016-10-05T22:44:02  *** cdecker has quit IRC
497 2016-10-05T22:45:13  <jeremyrubin> gmaxwell: if you want I have a super templated version where you can enable/disable a ton of things... but it's quite unsightly and needs some bugfixes.
498 2016-10-05T22:45:26  <gmaxwell> sipa: as a cuckoo hashtable fills, everythign initially starts out in it's h0 position. then you start getting collisions, when the table is way overfull, and you hit a collision (p=.9) then you look at that entry and go to put it in its alternate... but the reason it was in the entry you looked at was often because the alternate was already full. So the comparison you now make on the alternate
499 2016-10-05T22:45:32  <gmaxwell> if >p=.9 even though the table is only 90% full overall.
500 2016-10-05T22:48:19  <sipa> if evictions are independent from insertions (and evictions are responsible for all of the 10% empties), then i think any chain of entries up to 21 deep will have 0.9^21 chance to not have any evicted entries
501 2016-10-05T22:48:50  <sipa> you're talking about a model where there are only insertions
502 2016-10-05T22:49:49  <gmaxwell> okay, if we assume that the table is completely full, then evictions happen, then on your next insert I agree with you.
503 2016-10-05T22:50:05  <gmaxwell> but on the insert after that the performance will be worse than 0.899^21
504 2016-10-05T22:50:13  <sipa> right.
505 2016-10-05T22:51:21  <sipa> the iterations are at fullness just a search for entries that were deleted after the chain being traversed was created
506 2016-10-05T22:51:51  <sipa> and increasing the iteration count means you're willing to spend more time looking for those
507 2016-10-05T22:52:19  <sipa> i'm not convinced that making this choice depend on the table size is the best choice
508 2016-10-05T22:52:41  <sipa> but it looks simple and it works better than what we have
509 2016-10-05T22:53:17  <gmaxwell> But a 2-way set assc cache would be even simpler.
510 2016-10-05T22:54:08  <jeremyrubin> sipa: you could make the choice based on the number of sigops in the last block
511 2016-10-05T22:54:43  <jeremyrubin> eg, st (1-empty%)^iter > .50
512 2016-10-05T22:54:44  <gmaxwell> and at very full levels it will perform no worse, you give an argument which I can can buy that the complexity does improve performance, e.g. at the 90% full level. I dunno what level of fullness would be typical.
513 2016-10-05T22:56:04  <gmaxwell> if the cache has 40MB of 32 byte entries. and a single block empties 4000 and before a new block arrives 4000 are added, then the low watermark would be 99.6%
514 2016-10-05T22:56:36  <sipa> yeah, i think in optimal cases you want to artificially keep the fullness low
515 2016-10-05T22:56:42  <gmaxwell> and 21 probes would be pretty unlikely to find a deleted entry.
516 2016-10-05T22:57:19  <gmaxwell> meaning a plain 2way set assc would have performed just as well but with simpler code and 40x faster insertion.
517 2016-10-05T22:57:37  <sipa> find some function of the fullness for the maximum number of iterations
518 2016-10-05T22:57:48  <sipa> which is 1 when completely
519 2016-10-05T22:57:50  <sipa> full
520 2016-10-05T22:58:27  <sipa> jeremyrubin: can you efficiently keep track of fullness?
521 2016-10-05T22:58:40  <gmaxwell> well what you want is something that is an insertion time tolerance, and when that tolerance would not be likely to yield an improvement, you just go 1 deep.
522 2016-10-05T22:59:22  <sipa> it's a balance between chance of evicting a live entry and increasing fullness
523 2016-10-05T22:59:59  <sipa> perhaps the max iterations should be 1 already at 90%
524 2016-10-05T23:00:19  <sipa> and $TOLERANCE at 0%
525 2016-10-05T23:00:30  <sipa> and some nifty fitted function in between
526 2016-10-05T23:01:00  <gmaxwell> well the question you have is the marginal rate of return for each probe.
527 2016-10-05T23:01:41  <gmaxwell> for low full levels the tolerance exists to prevent cycles.
528 2016-10-05T23:02:08  <gmaxwell> the probably of going more than N times when you are M full, is negligible unless there is a cycle.
529 2016-10-05T23:02:37  <gmaxwell> so thats normally where the max probe count (which then triggers a resize and/or rehashing of the whole time) in an ordinary cuckoo hash.
530 2016-10-05T23:03:10  <gmaxwell> I'm sure tromp could tell us all about those probablities. :P
531 2016-10-05T23:05:56  <sipa> there is an annoyong collision in my brain's cuckoo table between john trump and donald tromp.
532 2016-10-05T23:06:51  <gmaxwell> ... just move one to its alternative location?
533 2016-10-05T23:07:16  <gmaxwell> s/whole time/whole table/
534 2016-10-05T23:08:17  <gmaxwell> In any case, unless there is something surprising about fullness going on, with our current tables, I believe that setting the max depth to 1 (turning this into a 2way set assc cache) would not hurt block validation performance.
535 2016-10-05T23:14:28  <gmaxwell> but a generation count could make it be effectively 50% free at all time, and then that argument goes out the window.
536 2016-10-05T23:15:02  *** Chris_Stewart_5 has quit IRC
537 2016-10-05T23:15:53  <jeremyrubin> you can cheaply do generations for cost of one bit
538 2016-10-05T23:16:11  <gmaxwell> it would be fine to reduce the key size by a couple bits.
539 2016-10-05T23:16:34  <jeremyrubin> hell, you can even replace marking garbage at all and just do generations
540 2016-10-05T23:16:41  <jeremyrubin> gmaxwell: yeah I built a version like that
541 2016-10-05T23:16:50  <jeremyrubin> you use the last bit/byte for flags
542 2016-10-05T23:17:10  <gmaxwell> to be honest the keys could be 16 bytes, since the hash is privately salted... but at least with the old datastructure there wouldn't have been a huge performance improvement from that.
543 2016-10-05T23:17:10  <jeremyrubin> If memory overhead is really a must
544 2016-10-05T23:17:58  <jeremyrubin> gmaxwell: agree 100%, but I thought that wasn't reviewable
545 2016-10-05T23:18:12  <gmaxwell> If we wanted the same code to work as a replacement for the bloom filter elsewhere we'd want to use the location xor trick, where other_index =  this_index^H(key)   ... this lets you use very small keys.. the original insert tries to go into index = H(bigger_key).
546 2016-10-05T23:18:41  <gmaxwell> jeremyrubin: yea, I wouldn't bother but it would be good to know what performance we were leaving on the floor, if any. If it's a lot it would be worth considering.
547 2016-10-05T23:20:21  <jeremyrubin> yeah; the nice thing is I think this patch is a nesc first step to trying out those designs; so my feeling is we should try to review this then such improvements can be measured
548 2016-10-05T23:23:08  <jeremyrubin> I didn't try a version with half sized keys FYI.. figured proposing that would be DOA
549 2016-10-05T23:23:53  <gmaxwell> it would only be an interesting proposal if it showed a big speedup, otherwise it's not worth trying to reason about the security.
550 2016-10-05T23:24:37  <jeremyrubin> Also if we're going to 128 bit may as well do md5 or something if you really want things to go faster
551 2016-10-05T23:24:49  <jeremyrubin> md5+salt should be just as secure
552 2016-10-05T23:24:54  <jeremyrubin> (iirc)
553 2016-10-05T23:25:42  <sipa> SipHash128.
554 2016-10-05T23:25:45  <sipa> me ducks
555 2016-10-05T23:26:27  <jeremyrubin> haha isn't that experimental tho
556 2016-10-05T23:27:09  <jeremyrubin> but yeah computing the hashes is a hot path thing, so if one really wants to rice this sucker would make things faster
557 2016-10-05T23:27:30  <jeremyrubin> (ComputeEntry called once per lookup)
558 2016-10-05T23:31:03  <GitHub138> [bitcoin] randy-waterhouse opened pull request #8896: Update INSTALL landing redirection notice for build instructions. (master...master) https://github.com/bitcoin/bitcoin/pull/8896
559 2016-10-05T23:31:05  <tunafizz> needs moar power al *grunt*grunt*grunt*
560 2016-10-05T23:31:30  <gmaxwell> well if you want faster, using blake2b would be the same speed as md5, and keeping the ~32 byte output I wouldn't really have much to fuss about the security.
561 2016-10-05T23:35:21  <tunafizz> needs the binford2000 hash al *grunt*grunt*grunt*
562 2016-10-05T23:35:32  *** DigiByteDev has joined #bitcoin-core-dev
563 2016-10-05T23:38:38  <sipa> gmaxwell: 3 cycles per byte, damn...
564 2016-10-05T23:48:36  *** juscamarena has joined #bitcoin-core-dev