12016-10-05T00:35:51  *** Chris_Stewart_5 has quit IRC
  22016-10-05T00:47:01  *** Ylbam has quit IRC
  32016-10-05T00:53:18  *** owowo has quit IRC
  42016-10-05T00:54:48  *** justanotheruser has quit IRC
  52016-10-05T00:57:07  *** owowo has joined #bitcoin-core-dev
  62016-10-05T01:01:41  *** Expanse has quit IRC
  72016-10-05T01:05:52  *** justanotheruser has joined #bitcoin-core-dev
  82016-10-05T01:07:42  *** juscamarena has joined #bitcoin-core-dev
  92016-10-05T01:13:58  *** Expanse has joined #bitcoin-core-dev
 102016-10-05T01:20:41  *** juscamarena has quit IRC
 112016-10-05T01:28:42  *** owowo has quit IRC
 122016-10-05T01:34:17  *** owowo has joined #bitcoin-core-dev
 132016-10-05T01:42:12  *** linuxfan2718 has joined #bitcoin-core-dev
 142016-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?
 152016-10-05T02:10:17  *** paveljanik has quit IRC
 162016-10-05T02:18:24  <wumpus> (looking up these numbers for documentation in protocol.h for #8880)
 172016-10-05T02:19:46  <luke-jr> if it's not used in code, why define it at all?
 182016-10-05T02:20:25  *** jtimon has quit IRC
 192016-10-05T02:20:36  <wumpus> I'd say to reserve the bit pattern, though this should happen in the BIP too
 202016-10-05T02:21:08  <luke-jr> ah, so we use the value, just via setting a bit instead of the enum key
 212016-10-05T02:21:46  <wumpus> that's my assumption. I haven't checked
 222016-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
 232016-10-05T02:49:11  *** xinxi has joined #bitcoin-core-dev
 242016-10-05T02:49:49  <xinxi> sipa: are you there?
 252016-10-05T02:50:17  <xinxi> I am wondering why Bitcoin Core does not store the blockchain in a distributed way to save space?
 262016-10-05T02:50:22  *** Chris_Stewart_5 has joined #bitcoin-core-dev
 272016-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
 282016-10-05T02:52:16  <wumpus> see e.g. last meeting notes
 292016-10-05T02:52:59  <wumpus> the answer to 'why' is always: because no one has designed/implemented this yet
 302016-10-05T02:53:14  <xinxi> So theoretically, it is possible.
 312016-10-05T02:53:16  <wumpus> in any case if you are short in space you can use pruning
 322016-10-05T02:53:26  <xinxi> And blocksize won't be a problem seriously.
 332016-10-05T02:53:49  <wumpus> you're confounding issues
 342016-10-05T02:54:21  <xinxi> Sure blocksize increase will cause other issues like network latency.
 352016-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
 362016-10-05T02:55:06  <wumpus> anyhow move this to #bitcoin, this is off topic here
 372016-10-05T02:55:12  <xinxi> OK
 382016-10-05T02:56:04  <xinxi> Thank you.
 392016-10-05T02:59:50  <xinxi> Another question directly about Bitcoin's current protocol.
 402016-10-05T03:00:17  <xinxi> Is it possible to increase OP_RETURN's data size with a softfork?
 412016-10-05T03:00:35  <wumpus> this topic is about development, discussion about changing the source code, use #bitcoin for general questions
 422016-10-05T03:00:40  <wumpus> see topic ^^
 432016-10-05T03:03:05  *** bsm117532 is now known as Guest26311
 442016-10-05T03:07:53  <GitHub168> [bitcoin] laanwj pushed 2 new commits to master: https://github.com/bitcoin/bitcoin/compare/d7615af34e8e...f92805025d5b
 452016-10-05T03:07:53  <GitHub168> bitcoin/master eeeebdd MarcoFalke: [doc] Rework docs...
 462016-10-05T03:07:54  <GitHub168> bitcoin/master f928050 Wladimir J. van der Laan: Merge #8879: [doc] Rework docs...
 472016-10-05T03:08:03  <GitHub181> [bitcoin] laanwj closed pull request #8879: [doc] Rework docs (master...Mf1610-docCleanup) https://github.com/bitcoin/bitcoin/pull/8879
 482016-10-05T03:12:30  <wumpus> sigh... https://github.com/bitcoin/bitcoin/pull/8886#discussion_r81892323
 492016-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
 502016-10-05T03:17:34  *** btcdrak has quit IRC
 512016-10-05T03:17:48  *** xinxi has quit IRC
 522016-10-05T03:18:24  *** xinxi has joined #bitcoin-core-dev
 532016-10-05T03:18:57  *** Chris_Stewart_5 has quit IRC
 542016-10-05T03:19:48  *** Giszmo has quit IRC
 552016-10-05T03:23:18  *** xinxi has quit IRC
 562016-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
 572016-10-05T03:26:24  *** xinxi has joined #bitcoin-core-dev
 582016-10-05T03:33:22  <achow101> the values for MSG_WITNESS_BLOCK and MSG_WITNESS_TX should probably be defined in BIP144...
 592016-10-05T03:34:42  <wumpus> good point achow101
 602016-10-05T03:51:07  *** paveljanik has joined #bitcoin-core-dev
 612016-10-05T04:00:00  <luke-jr> wumpus: wtf @ 8886
 622016-10-05T04:10:50  *** molz has quit IRC
 632016-10-05T04:17:45  *** xinxi_ has joined #bitcoin-core-dev
 642016-10-05T04:20:52  *** xinxi has quit IRC
 652016-10-05T04:40:12  *** linuxfan2718 has quit IRC
 662016-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
 672016-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
 682016-10-05T04:55:44  <NicolasDorier> IBD
 692016-10-05T04:59:22  *** DigiByteDev has joined #bitcoin-core-dev
 702016-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
 712016-10-05T05:17:50  *** xinxi_ has quit IRC
 722016-10-05T05:17:54  <sipa> wumpus: i guess MSG_FILTERED_WITNESS_BLOCK is what we'd need for a bip37 extension with segwit data
 732016-10-05T05:18:35  <sipa> NicolasDorier: yes, i'm aware
 742016-10-05T05:34:21  *** Alopex has quit IRC
 752016-10-05T05:34:40  *** xinxi has joined #bitcoin-core-dev
 762016-10-05T05:35:26  *** Alopex has joined #bitcoin-core-dev
 772016-10-05T05:42:08  *** jl2012 has quit IRC
 782016-10-05T05:45:11  *** Alopex has quit IRC
 792016-10-05T05:46:12  *** jl2012 has joined #bitcoin-core-dev
 802016-10-05T05:46:16  *** Alopex has joined #bitcoin-core-dev
 812016-10-05T05:47:46  *** moli has joined #bitcoin-core-dev
 822016-10-05T05:52:53  *** molz has joined #bitcoin-core-dev
 832016-10-05T05:56:19  *** moli has quit IRC
 842016-10-05T05:58:51  *** molz has quit IRC
 852016-10-05T05:58:55  *** juscamarena has joined #bitcoin-core-dev
 862016-10-05T06:01:45  *** moli has joined #bitcoin-core-dev
 872016-10-05T06:13:57  *** DigiByteDev has quit IRC
 882016-10-05T06:20:58  *** DigiByteDev has joined #bitcoin-core-dev
 892016-10-05T06:35:02  *** btcdrak has joined #bitcoin-core-dev
 902016-10-05T06:37:58  *** BashCo has quit IRC
 912016-10-05T06:40:24  *** xinxi has quit IRC
 922016-10-05T06:44:19  *** juscamarena has quit IRC
 932016-10-05T06:58:39  <wumpus> sipa: makes sense
 942016-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
 952016-10-05T07:09:17  *** BashCo has joined #bitcoin-core-dev
 962016-10-05T07:09:39  *** rubensayshi has joined #bitcoin-core-dev
 972016-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 :)
 982016-10-05T07:13:25  * wumpus goes to add a section about FreeBSD to balance it out
 992016-10-05T07:17:06  *** MarcoFalke has joined #bitcoin-core-dev
1002016-10-05T07:18:01  *** shesek has quit IRC
1012016-10-05T07:19:09  *** harrymm has quit IRC
1022016-10-05T07:19:32  *** paveljanik has quit IRC
1032016-10-05T07:19:56  *** Ylbam has joined #bitcoin-core-dev
1042016-10-05T07:45:53  *** laurentmt has joined #bitcoin-core-dev
1052016-10-05T07:47:06  *** laurentmt has quit IRC
1062016-10-05T07:54:23  *** laurentmt has joined #bitcoin-core-dev
1072016-10-05T08:13:21  *** laurentmt has quit IRC
1082016-10-05T08:14:32  *** dcousens has joined #bitcoin-core-dev
1092016-10-05T08:14:52  <dcousens> btcdrak: "uncompressed keys which are disallowed under segwit.", interesting,  no issue but can't find that in the BIP?
1102016-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.
1112016-10-05T08:16:56  <btcdrak> see last meetung notes
1122016-10-05T08:17:00  <dcousens> btcdrak: ok, sweet, will do
1132016-10-05T08:18:46  <dcousens> btcdrak: seen in notes, cheers ;)
1142016-10-05T08:22:02  <btcdrak> I think we will make a note in the BIP bow, thanks.
1152016-10-05T08:23:46  <wumpus> maybe, though it should be very clear that it is policy and not consensus then
1162016-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.
1172016-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
1182016-10-05T08:31:06  <gmaxwell> Well we can do like we did with CSV, we had three BIPs triggered on one bit.
1192016-10-05T08:31:13  <wumpus> indeed. true.
1202016-10-05T08:31:20  <gmaxwell> The thing I'd combine it with would be low-S enforcement.
1212016-10-05T08:32:42  <dcousens> gmaxwell: agreed
1222016-10-05T08:32:46  <wumpus> yes that would make sense, it's a comparable thing
1232016-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.)
1242016-10-05T08:34:34  <dcousens> btcdrak: that was uncompressed rejection only in witnesses,  or even in regular scriptSigs?
1252016-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
1262016-10-05T08:36:28  <btcdrak> dcousens: only for segwit
1272016-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
1282016-10-05T08:36:34  <luke-jr> dcousens: only in witnesses; it'd break compatibility otherwise
1292016-10-05T08:37:01  <dcousens> ok
1302016-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.
1312016-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
1322016-10-05T08:53:24  <dcousens> rather than just flick a switch
1332016-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.
1342016-10-05T08:56:41  <dcousens> gmaxwell: hmmm, I suppose that is risky,  but I can see some actors aggrevating the issue for agendas
1352016-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
1362016-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.
1372016-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
1382016-10-05T09:00:02  <dcousens> delaying segwit* (and then putting it in that SF)
1392016-10-05T09:00:38  <gmaxwell> policy makes it safer.
1402016-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
1412016-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
1422016-10-05T09:01:16  <gmaxwell> with it non-standard, they could coordinate with miners to rescue them.
1432016-10-05T09:01:19  *** harrymm has joined #bitcoin-core-dev
1442016-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
1452016-10-05T09:07:50  *** harrymm has quit IRC
1462016-10-05T09:18:55  <wumpus> no, it's not worth delaying segwit
1472016-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
1482016-10-05T09:22:40  *** harrymm has joined #bitcoin-core-dev
1492016-10-05T09:49:17  *** cdecker has joined #bitcoin-core-dev
1502016-10-05T09:52:31  *** moli has quit IRC
1512016-10-05T09:53:20  *** moli has joined #bitcoin-core-dev
1522016-10-05T10:05:30  *** DigiByteDev has quit IRC
1532016-10-05T10:36:09  *** BashCo has quit IRC
1542016-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
1552016-10-05T10:37:08  *** DigiByteDev has joined #bitcoin-core-dev
1562016-10-05T10:40:55  *** JackH_ has joined #bitcoin-core-dev
1572016-10-05T10:42:13  *** DigiByteDev has quit IRC
1582016-10-05T10:43:48  *** JackH has quit IRC
1592016-10-05T10:46:55  *** DigiByteDev has joined #bitcoin-core-dev
1602016-10-05T10:47:28  *** DigiByteDev has quit IRC
1612016-10-05T11:07:01  *** Ylbam has quit IRC
1622016-10-05T11:17:37  *** jannes has joined #bitcoin-core-dev
1632016-10-05T11:25:19  *** BashCo has joined #bitcoin-core-dev
1642016-10-05T11:46:25  <wumpus> achow101: https://github.com/bitcoin/bips/pull/457
1652016-10-05T11:58:12  *** cryptapus has joined #bitcoin-core-dev
1662016-10-05T11:58:12  *** cryptapus has joined #bitcoin-core-dev
1672016-10-05T11:58:42  *** cryptapus has joined #bitcoin-core-dev
1682016-10-05T12:00:09  *** cryptapus has quit IRC
1692016-10-05T12:04:48  *** jtimon has joined #bitcoin-core-dev
1702016-10-05T12:04:49  *** cryptapus has joined #bitcoin-core-dev
1712016-10-05T12:04:50  *** cryptapus has joined #bitcoin-core-dev
1722016-10-05T12:12:25  *** laurentmt has joined #bitcoin-core-dev
1732016-10-05T12:19:57  *** paveljanik has joined #bitcoin-core-dev
1742016-10-05T12:19:57  *** paveljanik has joined #bitcoin-core-dev
1752016-10-05T12:32:36  *** laurentmt has quit IRC
1762016-10-05T12:44:32  <GitHub79> [bitcoin] laanwj pushed 2 new commits to master: https://github.com/bitcoin/bitcoin/compare/f92805025d5b...223f4c2dd5fa
1772016-10-05T12:44:32  <GitHub79> bitcoin/master a78e542 Luke Dashjr: Bugfix: Trivial: RPC: getblockchaininfo help: pruneheight is the lowest, not highest, block
1782016-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...
1792016-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
1802016-10-05T12:48:14  *** droark has quit IRC
1812016-10-05T12:57:27  *** cryptapus_ has joined #bitcoin-core-dev
1822016-10-05T12:57:45  *** cryptapus has quit IRC
1832016-10-05T12:59:42  *** Chris_Stewart_5 has joined #bitcoin-core-dev
1842016-10-05T13:04:06  *** JackH_ has quit IRC
1852016-10-05T13:05:18  *** jnewbery has joined #bitcoin-core-dev
1862016-10-05T13:09:15  *** laurentmt has joined #bitcoin-core-dev
1872016-10-05T13:12:00  *** cryptapus_ is now known as cryptapus
1882016-10-05T13:12:05  *** Chris_Stewart_5 has quit IRC
1892016-10-05T13:13:28  *** Chris_Stewart_5 has joined #bitcoin-core-dev
1902016-10-05T13:39:37  *** waxwing has joined #bitcoin-core-dev
1912016-10-05T13:41:18  *** Chris_Stewart_5 has quit IRC
1922016-10-05T13:47:26  *** Guyver2 has joined #bitcoin-core-dev
1932016-10-05T13:54:47  *** laurentmt has quit IRC
1942016-10-05T13:55:53  *** arowser has quit IRC
1952016-10-05T13:55:53  *** Chris_Stewart_5 has joined #bitcoin-core-dev
1962016-10-05T13:56:29  *** arowser has joined #bitcoin-core-dev
1972016-10-05T14:12:51  *** Chris_Stewart_5 has quit IRC
1982016-10-05T14:16:33  *** dcousens has quit IRC
1992016-10-05T14:28:29  *** Chris_Stewart_5 has joined #bitcoin-core-dev
2002016-10-05T14:29:28  *** Giszmo has joined #bitcoin-core-dev
2012016-10-05T14:37:06  *** Chris_Stewart_5 has quit IRC
2022016-10-05T14:38:44  *** arowser has quit IRC
2032016-10-05T14:38:45  *** BashCo has quit IRC
2042016-10-05T14:38:45  *** moli has quit IRC
2052016-10-05T14:38:46  *** jl2012 has quit IRC
2062016-10-05T14:38:47  *** Expanse has quit IRC
2072016-10-05T14:38:47  *** davec has quit IRC
2082016-10-05T14:38:48  *** wasi has quit IRC
2092016-10-05T14:38:48  *** Evel-Knievel has quit IRC
2102016-10-05T14:38:48  *** achow101 has quit IRC
2112016-10-05T14:38:48  *** musalbas has quit IRC
2122016-10-05T14:38:49  *** sdaftuar has quit IRC
2132016-10-05T14:38:49  *** Guest62318 has quit IRC
2142016-10-05T14:38:49  *** aalex has quit IRC
2152016-10-05T14:38:49  *** nsh_ has quit IRC
2162016-10-05T14:38:50  *** Anduck has quit IRC
2172016-10-05T14:39:11  *** Evel-Knievel has joined #bitcoin-core-dev
2182016-10-05T14:39:12  *** arowser has joined #bitcoin-core-dev
2192016-10-05T14:39:12  *** sdaftuar has joined #bitcoin-core-dev
2202016-10-05T14:39:17  *** achow101 has joined #bitcoin-core-dev
2212016-10-05T14:39:17  *** wasi has joined #bitcoin-core-dev
2222016-10-05T14:39:22  *** BashCo has joined #bitcoin-core-dev
2232016-10-05T14:39:24  *** Anduck has joined #bitcoin-core-dev
2242016-10-05T14:39:28  *** stan_ has joined #bitcoin-core-dev
2252016-10-05T14:39:57  *** moli has joined #bitcoin-core-dev
2262016-10-05T14:40:01  *** musalbas has joined #bitcoin-core-dev
2272016-10-05T14:41:29  *** jl2012 has joined #bitcoin-core-dev
2282016-10-05T14:41:35  *** aalex has joined #bitcoin-core-dev
2292016-10-05T14:45:04  *** ensign has joined #bitcoin-core-dev
2302016-10-05T14:48:57  *** davec has joined #bitcoin-core-dev
2312016-10-05T14:53:50  *** Expanse has joined #bitcoin-core-dev
2322016-10-05T15:07:08  *** moli has quit IRC
2332016-10-05T15:07:52  *** moli has joined #bitcoin-core-dev
2342016-10-05T15:25:49  *** Sosumi has joined #bitcoin-core-dev
2352016-10-05T15:26:59  *** droark has joined #bitcoin-core-dev
2362016-10-05T15:27:35  *** moli has quit IRC
2372016-10-05T15:32:44  *** moli has joined #bitcoin-core-dev
2382016-10-05T15:35:26  *** NLNico has joined #bitcoin-core-dev
2392016-10-05T15:37:18  *** laurentmt has joined #bitcoin-core-dev
2402016-10-05T15:48:33  *** laurentmt has quit IRC
2412016-10-05T15:50:13  *** Guest26311 is now known as bsm117532
2422016-10-05T15:53:13  *** rubensayshi has quit IRC
2432016-10-05T15:53:22  *** MarcoFalke has left #bitcoin-core-dev
2442016-10-05T15:54:21  <Lauda> Any estimate for 0.13.1 yet?
2452016-10-05T15:56:31  <sipa> soon.
2462016-10-05T15:56:46  <instagibbs> Two Weeks(TM)
2472016-10-05T15:57:23  <sipa> TW
2482016-10-05T15:57:31  <sipa> not TM, i hope
2492016-10-05T15:57:33  <Lauda> I dislike the word soon as it can mean anywhere between now and sometime in the distant future. :P
2502016-10-05T15:57:45  <sipa> Lauda: that is exactly what it meams
2512016-10-05T15:57:57  <sipa> there are very few remaining issues
2522016-10-05T15:58:28  <achow101> Lauda: as soon as everything in the milestone is taken care of
2532016-10-05T15:58:47  <Lauda> tl;dr: Soon.
2542016-10-05T15:59:03  <Lauda> I've checked the milestone not long ago.
2552016-10-05T15:59:15  <achow101> they keep adding new stuff
2562016-10-05T16:00:36  *** moli has quit IRC
2572016-10-05T16:04:24  *** jnewbery has quit IRC
2582016-10-05T16:06:22  *** moli has joined #bitcoin-core-dev
2592016-10-05T16:16:25  <cdecker> Soon is still better than 'eventually' :-)
2602016-10-05T16:32:04  *** jnewbery has joined #bitcoin-core-dev
2612016-10-05T16:34:36  <instagibbs> achow101, people can ask for milestone tags, may not happen tho
2622016-10-05T16:34:44  *** Chris_Stewart_5 has joined #bitcoin-core-dev
2632016-10-05T16:34:44  <instagibbs> a number have been pruned off already
2642016-10-05T16:39:55  *** Chris_Stewart_5 has quit IRC
2652016-10-05T16:44:36  *** To7 has joined #bitcoin-core-dev
2662016-10-05T16:46:13  *** Chris_Stewart_5 has joined #bitcoin-core-dev
2672016-10-05T16:49:12  *** xiangfu has quit IRC
2682016-10-05T16:49:33  *** xiangfu has joined #bitcoin-core-dev
2692016-10-05T17:06:15  *** laurentmt has joined #bitcoin-core-dev
2702016-10-05T17:09:55  *** arowser has quit IRC
2712016-10-05T17:10:44  *** laurentmt has quit IRC
2722016-10-05T17:12:10  *** arowser has joined #bitcoin-core-dev
2732016-10-05T17:16:47  *** jtimon has quit IRC
2742016-10-05T17:19:22  *** droark has quit IRC
2752016-10-05T17:28:25  *** droark has joined #bitcoin-core-dev
2762016-10-05T17:31:13  *** Ylbam has joined #bitcoin-core-dev
2772016-10-05T17:35:27  *** moli has quit IRC
2782016-10-05T17:44:49  *** droark has quit IRC
2792016-10-05T17:46:32  *** e4xit has quit IRC
2802016-10-05T17:46:39  *** cryptapus_ has joined #bitcoin-core-dev
2812016-10-05T17:46:39  *** cryptapus_ has joined #bitcoin-core-dev
2822016-10-05T17:47:40  *** e4xit has joined #bitcoin-core-dev
2832016-10-05T17:50:20  *** cryptapus has quit IRC
2842016-10-05T17:50:34  *** Chris_Stewart_5 has quit IRC
2852016-10-05T17:51:14  *** shesek has joined #bitcoin-core-dev
2862016-10-05T17:52:46  *** Chris_Stewart_5 has joined #bitcoin-core-dev
2872016-10-05T17:53:15  *** cryptapus_ has quit IRC
2882016-10-05T17:54:02  *** spudowiar has joined #bitcoin-core-dev
2892016-10-05T17:55:09  *** NLNico has quit IRC
2902016-10-05T17:56:46  *** spudowiar has quit IRC
2912016-10-05T17:58:59  *** cryptapus_ has joined #bitcoin-core-dev
2922016-10-05T18:01:54  <cfields_> jonasschnelli: ping
2932016-10-05T18:02:02  *** jouke has joined #bitcoin-core-dev
2942016-10-05T18:14:32  *** Evel-Knievel has quit IRC
2952016-10-05T18:15:23  *** jtimon has joined #bitcoin-core-dev
2962016-10-05T18:21:30  *** ensign is now known as rexnsh
2972016-10-05T18:26:13  *** cryptapus_ has quit IRC
2982016-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
2992016-10-05T18:35:41  *** wasi has quit IRC
3002016-10-05T18:40:43  *** Chris_Stewart_5 has quit IRC
3012016-10-05T18:47:39  *** wasi has joined #bitcoin-core-dev
3022016-10-05T18:54:47  *** Chris_Stewart_5 has joined #bitcoin-core-dev
3032016-10-05T19:14:18  *** Chris_Stewart_5 has quit IRC
3042016-10-05T19:17:12  *** cryptapus has joined #bitcoin-core-dev
3052016-10-05T19:42:19  *** jannes has quit IRC
3062016-10-05T19:52:40  *** h1d has joined #bitcoin-core-dev
3072016-10-05T19:54:20  *** h1d has quit IRC
3082016-10-05T19:59:09  *** stan_ has quit IRC
3092016-10-05T19:59:24  *** stan_ has joined #bitcoin-core-dev
3102016-10-05T20:04:49  *** cryptapus has quit IRC
3112016-10-05T20:35:49  *** alpalp has joined #bitcoin-core-dev
3122016-10-05T20:44:21  *** alpalp has quit IRC
3132016-10-05T20:44:44  *** alpalp has joined #bitcoin-core-dev
3142016-10-05T20:53:03  *** Evel-Knievel has joined #bitcoin-core-dev
3152016-10-05T20:54:59  *** laurentmt has joined #bitcoin-core-dev
3162016-10-05T20:58:19  *** alpalp has quit IRC
3172016-10-05T21:10:11  *** Chris_Stewart_5 has joined #bitcoin-core-dev
3182016-10-05T21:19:26  *** meowzus has joined #bitcoin-core-dev
3192016-10-05T21:26:23  *** randy-waterhouse has joined #bitcoin-core-dev
3202016-10-05T21:26:41  *** randy-waterhouse has joined #bitcoin-core-dev
3212016-10-05T21:28:56  *** laurentmt has quit IRC
3222016-10-05T21:31:06  *** shesek has quit IRC
3232016-10-05T21:32:59  *** paveljanik has quit IRC
3242016-10-05T21:34:20  *** paveljanik has joined #bitcoin-core-dev
3252016-10-05T21:35:30  *** jnewbery has quit IRC
3262016-10-05T21:35:55  *** jnewbery has joined #bitcoin-core-dev
3272016-10-05T21:36:00  *** shesek has joined #bitcoin-core-dev
3282016-10-05T21:38:24  *** Guyver2 has quit IRC
3292016-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
3302016-10-05T21:52:40  <jeremyrubin> \me \o/
3312016-10-05T21:52:48  * jeremyrubin \o/
3322016-10-05T21:53:57  <sipa> this is not \LaTeX
3332016-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.
3342016-10-05T21:55:40  <jeremyrubin> sipa: latex irc plugin would be dope
3352016-10-05T21:56:05  <sipa> jeremyrubin:
3362016-10-05T21:56:11  <jeremyrubin> $\mu$'s eveywhere
3372016-10-05T21:56:31  <sipa> ỉţ ẅờữľđ çëřŧẩîńļŷ șïḿpľìƒỹ ẁřîŧīňğ ťẽxŧ ŵíţĥ ĺốţš ôƒ ďīäćŗìťĩčș
3382016-10-05T21:56:56  <jeremyrubin> gmaxwell: this is a lossy version
3392016-10-05T21:58:27  <gmaxwell> whats lossy about it? looks like if there is a collision you ripple, like an ordinary cuckoo hash.
3402016-10-05T21:58:43  <jeremyrubin> gmaxwell: once depth is reached, last thing touched goes bye-bye
3412016-10-05T21:58:56  <jeremyrubin> gmaxwell: no rehashing
3422016-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.
3432016-10-05T21:59:47  <bsm117532> https://sourceforge.net/projects/pidgin-latex/
3442016-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.)
3452016-10-05T22:00:49  *** gmaxwell is now known as gmaxwell_
3462016-10-05T22:01:39  *** stan_ has quit IRC
3472016-10-05T22:01:50  *** gmaxwell_ is now known as gmaxwell
3482016-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
3492016-10-05T22:02:12  *** timothy has quit IRC
3502016-10-05T22:02:13  *** stan_ has joined #bitcoin-core-dev
3512016-10-05T22:02:14  *** drizztbsd has joined #bitcoin-core-dev
3522016-10-05T22:02:20  <jeremyrubin> gmaxwell: ^^^
3532016-10-05T22:02:33  <gmaxwell> jeremyrubin: what you need to do if you hit the maximum then is go delete entries at random.
3542016-10-05T22:02:45  *** drizztbsd is now known as timothy
3552016-10-05T22:02:55  <jeremyrubin> gmaxwell: I did however test with more hashes per entry (10)
3562016-10-05T22:03:05  <kanzure> is it correct that 8393 should be marked "needs backport" ? https://github.com/bitcoin/bitcoin/pull/8393#issuecomment-238783829
3572016-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.
3582016-10-05T22:03:30  <jeremyrubin> Yeah
3592016-10-05T22:03:41  <jeremyrubin> so fortunately insert performance isn't a large priority
3602016-10-05T22:03:50  <sipa> with 3 hashes you can get to 90% full :)
3612016-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.
3622016-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
3632016-10-05T22:04:34  <jeremyrubin> So the "eager-delete" strategy is a loser
3642016-10-05T22:04:45  <jeremyrubin> sipa: yes, but on a non-fixed memory system
3652016-10-05T22:04:52  <sipa> ?
3662016-10-05T22:05:04  <jeremyrubin> *non-fixed
3672016-10-05T22:05:14  <jeremyrubin> eg, you can get to 90% before needing a re-hash
3682016-10-05T22:05:21  <jeremyrubin> but we never increase memory size
3692016-10-05T22:05:28  <jeremyrubin> so we always get to 100% full
3702016-10-05T22:05:36  <jeremyrubin> it's just a matter of how fast
3712016-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
3722016-10-05T22:06:38  *** stan_ has quit IRC
3732016-10-05T22:06:46  <gmaxwell> jeremyrubin: what is the depth limit you're using?
3742016-10-05T22:06:54  <jeremyrubin> log(size)
3752016-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.
3762016-10-05T22:07:56  <jeremyrubin> Yeah that's fine
3772016-10-05T22:08:08  <jeremyrubin> We don't really care about insert performance (non-hot path)
3782016-10-05T22:08:43  <jeremyrubin> And we also do care about deleting things that have been erased preferentially (rather than randomly)
3792016-10-05T22:08:55  <jeremyrubin> so it's worth it.
3802016-10-05T22:10:09  <sipa> jeremyrubin: i see
3812016-10-05T22:11:03  *** droark has joined #bitcoin-core-dev
3822016-10-05T22:14:41  <jeremyrubin> besides, log2(40mb/32bytes per entry) ~~ 21 which is not trivial, but not huge by any means
3832016-10-05T22:15:26  <gmaxwell> it's a lot of random memory accesses.
3842016-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
3852016-10-05T22:16:52  <jeremyrubin> gmaxwell: I'll float those later if this gets through review
3862016-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.
3872016-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.
3882016-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.
3892016-10-05T22:18:32  <jeremyrubin> gmaxwell: wrong. l1/l2 matters at that size
3902016-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
3912016-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)
3922016-10-05T22:21:55  <sipa> (h0(k) & 1, h0(k) | 1) won't result in a cuckoo style behaviour, i think
3932016-10-05T22:22:05  <sipa> as the collisions are perfectly correlated
3942016-10-05T22:22:11  <gmaxwell> no, it won't.
3952016-10-05T22:22:37  <jeremyrubin> sipa: that's why you have two hashes still
3962016-10-05T22:22:42  <jeremyrubin> sorry if that was unclear
3972016-10-05T22:22:48  <sipa> ah, you mean in addition
3982016-10-05T22:22:50  <sipa> right
3992016-10-05T22:22:54  <jeremyrubin> yes
4002016-10-05T22:23:04  <gmaxwell> but this table doesn't really make use of cuckoo style behavior once it fills.
4012016-10-05T22:23:10  <sipa> you're turning each entry into a 2-way associativr cache
4022016-10-05T22:23:12  <gmaxwell> it just becomes a 2-way set assc cache.
4032016-10-05T22:23:22  <jeremyrubin> sure
4042016-10-05T22:24:02  *** instagibbs has quit IRC
4052016-10-05T22:24:20  <jeremyrubin> gmaxwell: more or less the same thing
4062016-10-05T22:24:38  <sipa> what would be the effect if you greatly reduced the max iterations?
4072016-10-05T22:24:48  <jeremyrubin> less likely to find garbage on insert
4082016-10-05T22:24:48  <sipa> (in the otherwise kiss design)
4092016-10-05T22:25:24  <sipa> so why bother doing 21 iterations?
4102016-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.
4112016-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
4122016-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
4132016-10-05T22:26:32  <gmaxwell> BlueMatt: I'm also thinking about other places where we should use this.
4142016-10-05T22:26:40  <BlueMatt> ahh, ok, fair enough
4152016-10-05T22:26:44  <gmaxwell> And I care about the overall cpu usage of bitcoin, not just the block race. :)
4162016-10-05T22:27:03  <gmaxwell> it looks like great work too, I'm not being negative, just thinking it through.
4172016-10-05T22:27:09  <BlueMatt> ehh, doing a few more memory hits after doing ATMP checksigs isnt all that much too notice :p
4182016-10-05T22:27:40  <jeremyrubin> sipa: Finding garbage means finding a signature you don't need again (unless reorg)
4192016-10-05T22:27:45  <sipa> yes, in case it isn't clear, i'm just playing devil's advocate to understand
4202016-10-05T22:28:04  <jeremyrubin> sipa: finding !garbage means you delete something maybe valuable
4212016-10-05T22:28:23  <jeremyrubin> sipa: (yes :) )
4222016-10-05T22:28:25  *** shesek has quit IRC
4232016-10-05T22:28:32  <jeremyrubin> If i math'd right: (1-((5000/((float(40<<20)/(32.0+1.0/8))))))**21
4242016-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.
4252016-10-05T22:28:43  <jeremyrubin> == ~92%
4262016-10-05T22:28:58  <jeremyrubin> should be chance of deleting with this design
4272016-10-05T22:29:14  <jeremyrubin> gmaxwell: what is the cuckoo behavior? Eg, one hash location?
4282016-10-05T22:29:27  <gmaxwell> jeremyrubin: no, cuckoo behavior is the rippling insertion.
4292016-10-05T22:29:42  <jeremyrubin> gmaxwell: so not iterating at all?
4302016-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).
4312016-10-05T22:29:54  <BlueMatt> gmaxwell: i think, here, thats motly there so that you can find entries marked deleted while rippling
4322016-10-05T22:30:03  <BlueMatt> if you didnt have the delete flags, probably
4332016-10-05T22:30:19  <gmaxwell> okay, I wasn't thinking about the delete flags, hows that work?
4342016-10-05T22:30:34  <BlueMatt> its the sigcache - we used to delete things while checking sigs in blocks
4352016-10-05T22:30:40  <BlueMatt> now they're marked for deletion in an atomic
4362016-10-05T22:30:55  <BlueMatt> so jeremyrubin's thing goes through and treats slots as empty if they have a delete flag on insert
4372016-10-05T22:30:56  <gmaxwell> I don't think that matters actually.
4382016-10-05T22:31:07  <BlueMatt> this has an interesting benifit of making it so that reorgs at the tip might use sigcache
4392016-10-05T22:31:09  <gmaxwell> When you go to insert, if either are free or marked delete, overwrite.
4402016-10-05T22:31:22  <gmaxwell> otherwise pick one and overwrite.
4412016-10-05T22:31:29  <gmaxwell> rippling at that point doesn't do you any good.
4422016-10-05T22:31:40  <gmaxwell> the other entries you would delete will get deleted when something tries to insert in them.
4432016-10-05T22:31:46  <jeremyrubin> yes it does? the next one might find a trash
4442016-10-05T22:32:01  *** jnewbery has quit IRC
4452016-10-05T22:32:15  <sipa> jeremyrubin: i see!
4462016-10-05T22:32:20  <gmaxwell> I don't.
4472016-10-05T22:32:24  <jeremyrubin> k1 and k2 sharing location X are highly unlikely to have another in common
4482016-10-05T22:32:54  <gmaxwell> If I insert k1  and one of its locations contains trash, I'll use that location.
4492016-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
4502016-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.
4512016-10-05T22:33:18  <jeremyrubin> eg, h1(k1) == h1(k2), unlikely h2(k1) != h2(k2)
4522016-10-05T22:33:42  <gmaxwell> sipa: yes; thats equal to saying that cuckoo is helpful if the table is not overfull.
4532016-10-05T22:34:15  <sipa> well, yes, but it won't be if many entries are marked deleted
4542016-10-05T22:34:17  <gmaxwell> which it is, but if the table is normally more than 50% full, it doesn't help.
4552016-10-05T22:34:36  <sipa> i think it can be way more than 50% full
4562016-10-05T22:34:57  <jeremyrubin> will always go to 100% full
4572016-10-05T22:35:00  <jeremyrubin> except after a block
4582016-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.
4592016-10-05T22:35:21  <sipa> if there are no deleted positions (or very few), agree
4602016-10-05T22:35:40  <jeremyrubin> there are n_sigops(last_block) empty slots
4612016-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
4622016-10-05T22:35:46  <gmaxwell> sipa: not just 'very few'. The benefit of cuckoo drops of exponentially after 50%.
4632016-10-05T22:36:26  <gmaxwell> BlueMatt: not if the table is well over 50% full (deleted entries are not full in this measure).
4642016-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
4652016-10-05T22:36:44  <jeremyrubin> This can be addressed by increasing hashes to 3 or 4 (or 10!)
4662016-10-05T22:36:57  <jeremyrubin> not fact 10 just 10 excitement
4672016-10-05T22:37:13  <BlueMatt> gmaxwell: indeed, though if you have quick blocks it means you're less full...
4682016-10-05T22:37:14  <gmaxwell> yes, the table can run fuller if there are more probes, but with a linear slowdown for your lookup.
4692016-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
4702016-10-05T22:37:53  <sipa> BlueMatt: or age
4712016-10-05T22:37:57  <BlueMatt> or age
4722016-10-05T22:38:02  <jeremyrubin> Yep
4732016-10-05T22:38:04  <sipa> add generation numbers like the bloom filter cache
4742016-10-05T22:38:07  <jeremyrubin> Yep
4752016-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.
4762016-10-05T22:38:24  <jeremyrubin> Or like.. clear them on eviction
4772016-10-05T22:38:31  <sipa> gmaxwell: 0.9^21, no?
4782016-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.
4792016-10-05T22:39:58  <jeremyrubin> Wait what?
4802016-10-05T22:40:13  <gmaxwell> this is why the performance falls off so dramatically at over 50% full.
4812016-10-05T22:40:13  <jeremyrubin> That's only true if we prefer h0 over h1?
4822016-10-05T22:40:13  <BlueMatt> this is only true if your table is small compared to your iteration count?
4832016-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
4842016-10-05T22:41:22  <jeremyrubin> and still be on par with existing :P
4852016-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
4862016-10-05T22:41:34  <BlueMatt> gmaxwell: i mean it should be close
4872016-10-05T22:41:41  <sipa> gmaxwell: i don't understand
4882016-10-05T22:41:53  <sipa> gmaxwell: maybe we have different assumptions
4892016-10-05T22:42:02  <jeremyrubin> I agree with sipa
4902016-10-05T22:42:15  <jeremyrubin> my math was: ((1-((5000/((float(40<<20)/(32.0+1.0/8))))))**1)
4912016-10-05T22:42:23  <jeremyrubin> oops last one should be a 21
4922016-10-05T22:42:31  <BlueMatt> anyway, headed out, y'all figure it out and report back :P
4932016-10-05T22:42:33  <jeremyrubin> for a block clearing 5k things
4942016-10-05T22:43:13  <jeremyrubin> Gonna head out for some dinner; looking forward to hearing more of your thoughts.
4952016-10-05T22:43:28  *** shesek has joined #bitcoin-core-dev
4962016-10-05T22:44:02  *** cdecker has quit IRC
4972016-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.
4982016-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
4992016-10-05T22:45:32  <gmaxwell> if >p=.9 even though the table is only 90% full overall.
5002016-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
5012016-10-05T22:48:50  <sipa> you're talking about a model where there are only insertions
5022016-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.
5032016-10-05T22:50:05  <gmaxwell> but on the insert after that the performance will be worse than 0.899^21
5042016-10-05T22:50:13  <sipa> right.
5052016-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
5062016-10-05T22:51:51  <sipa> and increasing the iteration count means you're willing to spend more time looking for those
5072016-10-05T22:52:19  <sipa> i'm not convinced that making this choice depend on the table size is the best choice
5082016-10-05T22:52:41  <sipa> but it looks simple and it works better than what we have
5092016-10-05T22:53:17  <gmaxwell> But a 2-way set assc cache would be even simpler.
5102016-10-05T22:54:08  <jeremyrubin> sipa: you could make the choice based on the number of sigops in the last block
5112016-10-05T22:54:43  <jeremyrubin> eg, st (1-empty%)^iter > .50
5122016-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.
5132016-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%
5142016-10-05T22:56:36  <sipa> yeah, i think in optimal cases you want to artificially keep the fullness low
5152016-10-05T22:56:42  <gmaxwell> and 21 probes would be pretty unlikely to find a deleted entry.
5162016-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.
5172016-10-05T22:57:37  <sipa> find some function of the fullness for the maximum number of iterations
5182016-10-05T22:57:48  <sipa> which is 1 when completely
5192016-10-05T22:57:50  <sipa> full
5202016-10-05T22:58:27  <sipa> jeremyrubin: can you efficiently keep track of fullness?
5212016-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.
5222016-10-05T22:59:22  <sipa> it's a balance between chance of evicting a live entry and increasing fullness
5232016-10-05T22:59:59  <sipa> perhaps the max iterations should be 1 already at 90%
5242016-10-05T23:00:19  <sipa> and $TOLERANCE at 0%
5252016-10-05T23:00:30  <sipa> and some nifty fitted function in between
5262016-10-05T23:01:00  <gmaxwell> well the question you have is the marginal rate of return for each probe.
5272016-10-05T23:01:41  <gmaxwell> for low full levels the tolerance exists to prevent cycles.
5282016-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.
5292016-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.
5302016-10-05T23:03:10  <gmaxwell> I'm sure tromp could tell us all about those probablities. :P
5312016-10-05T23:05:56  <sipa> there is an annoyong collision in my brain's cuckoo table between john trump and donald tromp.
5322016-10-05T23:06:51  <gmaxwell> ... just move one to its alternative location?
5332016-10-05T23:07:16  <gmaxwell> s/whole time/whole table/
5342016-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.
5352016-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.
5362016-10-05T23:15:02  *** Chris_Stewart_5 has quit IRC
5372016-10-05T23:15:53  <jeremyrubin> you can cheaply do generations for cost of one bit
5382016-10-05T23:16:11  <gmaxwell> it would be fine to reduce the key size by a couple bits.
5392016-10-05T23:16:34  <jeremyrubin> hell, you can even replace marking garbage at all and just do generations
5402016-10-05T23:16:41  <jeremyrubin> gmaxwell: yeah I built a version like that
5412016-10-05T23:16:50  <jeremyrubin> you use the last bit/byte for flags
5422016-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.
5432016-10-05T23:17:10  <jeremyrubin> If memory overhead is really a must
5442016-10-05T23:17:58  <jeremyrubin> gmaxwell: agree 100%, but I thought that wasn't reviewable
5452016-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).
5462016-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.
5472016-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
5482016-10-05T23:23:08  <jeremyrubin> I didn't try a version with half sized keys FYI.. figured proposing that would be DOA
5492016-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.
5502016-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
5512016-10-05T23:24:49  <jeremyrubin> md5+salt should be just as secure
5522016-10-05T23:24:54  <jeremyrubin> (iirc)
5532016-10-05T23:25:42  <sipa> SipHash128.
5542016-10-05T23:25:45  <sipa> me ducks
5552016-10-05T23:26:27  <jeremyrubin> haha isn't that experimental tho
5562016-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
5572016-10-05T23:27:30  <jeremyrubin> (ComputeEntry called once per lookup)
5582016-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
5592016-10-05T23:31:05  <tunafizz> needs moar power al *grunt*grunt*grunt*
5602016-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.
5612016-10-05T23:35:21  <tunafizz> needs the binford2000 hash al *grunt*grunt*grunt*
5622016-10-05T23:35:32  *** DigiByteDev has joined #bitcoin-core-dev
5632016-10-05T23:38:38  <sipa> gmaxwell: 3 cycles per byte, damn...
5642016-10-05T23:48:36  *** juscamarena has joined #bitcoin-core-dev