< sipa> jeremyrubin: specifically, in a ranked index you can count how many set/index elements have a certain property, and then pick a uniformly random one in O(log n) time
< sipa> in an ordered index those are O(n) in the number of matching elements
< jeremyrubin> Gotcha. So some cached property or ordered predicate, you can see how many things satisfy in O(log(N)) and then pick in O(1) time from that?
< sipa> picking is still O(log n) in the size of the index in a ranked_index
< sipa> and counting too
< jeremyrubin> sipa: interesting. So every query is log(n) for that, (e.g., n queries cost n log n not n)
< sipa> indeed
< sipa> well, no
< sipa> say n is the total index size and m is the number of matching elements
< jeremyrubin> was just going to ask
< sipa> then finding the number of matching elements is O(log n)
< sipa> picking one of them randomly is O(log m)
< sipa> hmm, in theory - not sure that's implemented though
< sipa> it may be O(log n) still
< bitcoin-git> [bitcoin] fanquake pushed 2 commits to master: https://github.com/bitcoin/bitcoin/compare/553bb3fc3d95...e2f6866cca3e
< bitcoin-git> bitcoin/master 050e2ee Wladimir J. van der Laan: test: Remove const to work around compiler error on xenial
< jeremyrubin> Interesting
< bitcoin-git> bitcoin/master e2f6866 fanquake: Merge #18975: test: Remove const to work around compiler error on xenial
< jeremyrubin> Because there are algorithms where you pick your rank M so that log(m) is small
< bitcoin-git> [bitcoin] fanquake merged pull request #18975: test: Remove const to work around compiler error on xenial (master...2020_05_xenial_compile_issue) https://github.com/bitcoin/bitcoin/pull/18975
< jeremyrubin> But the interesting point is you only see a benefit on repeated queries if you're making a few queries to it
< jeremyrubin> Otherwise you may as well do O(n) to make a new filter, then have O(1) uniform drawing
< sipa> i don't understand
< sipa> you cannot pick an element in O(1) time in a tree structure
< sipa> you need something like a vector for that
< jeremyrubin> No you're missing what I'm saying
< jeremyrubin> new filter == make a vector that is the filtered things to match predicate
< sipa> ok, but that's O(m)
< jeremyrubin> Depending on the underlying container, O(m) or O(n)
< jeremyrubin> O(n) if the property isn't already sorted
< sipa> (no need for a new vector though; you can just do repeated iterator operations, which is always O(m))
< jeremyrubin> Nope!
< sipa> picking a random element doesn't require an order
< jeremyrubin> The vector lets you index in O(1)
< jeremyrubin> WHich if you're drawing multiple times
< jeremyrubin> is a speedup.
< sipa> yes but constructing is at least O(m)
< sipa> ah
< jeremyrubin> That's why I asked :)
< sipa> i only need to pick a random one once
< sipa> the next time a random element gets picked, the set may have changex
< jeremyrubin> gotcha.
< jeremyrubin> So kinda "pick random thing newer than last reconnect"
< jeremyrubin> *disconnect
< jeremyrubin> sipa: do you query the property in different ways?
< jeremyrubin> Or is it just one query
< jeremyrubin> E.g., top 15% known statically?
< jeremyrubin> Or is it some per-node %
< jeremyrubin> also if you have code happy to just look at that
< sipa> jeremyrubin: i'm stl considering several other approaches
< sipa> will show code when i have something to show
< sipa> jeremyrubin: and no, it's not a percentage, it's just to be able to pick uniformly random elements
< jeremyrubin> over the whole range?
< jeremyrubin> ah is it also picking uniformly over the range of values? Not just their indexes?
< sipa> within a subset with some property, which has an index over it
< sipa> so you find the first index entry with that property, and the last
< sipa> compute the rank of both
< sipa> subtract them to count them
< sipa> pick a uniformly random entry in that range
< sipa> and then use nth to map that rank to the index entry
< fanquake> Looking for opinions on just removing the remaining fuzz job for the 0.20 branch. It's not going to pass in Travis without even more backporting: https://github.com/bitcoin/bitcoin/pull/18973#issuecomment-629050088
< fanquake> I think having the fuzzers / valgrind /*san etc just running on master is ok
< luke-jr> without knowing the detail, I'm not sure I'm comfortable with forgoing the valgrind/*san stuff.. if those don't pass, surely we ought to fix them?
< fanquake> The issues are fixed in master, but unless you want to start backporting even more to 0.20.0, like #18413, they are always going to fail on that branch
< gribble> https://github.com/bitcoin/bitcoin/issues/18413 | script: prevent UB when computing abs value for num opcode serialize by pierreN · Pull Request #18413 · bitcoin/bitcoin · GitHub
< wumpus> fanquake: I think I'd prefer disabling the particular tests that fail for now, instead of disabling fuzzing on the 0.20 branch wholesale
< wumpus> I disabled valgrind and s390x to be on the same basis as master at least
< wumpus> but I do think some of the fuzz testing on the release branch is good, I mean it could uncover e.g. faulty backports
< bitcoin-git> [bitcoin] hebasto opened pull request #18980: build: Decouple clientversion.cpp from the git repo (master...0515-decouple) https://github.com/bitcoin/bitcoin/pull/18980
< fanquake> wumpus: ok. I’ll revert the last backport abd disable the scriptnum_ops fuzz test. Will see if anything else fails
< bitcoin-git> [bitcoin] fanquake closed pull request #15706: build: Check QT library version (master...check-qt-version) https://github.com/bitcoin/bitcoin/pull/15706
< bitcoin-git> [bitcoin] kallewoof opened pull request #18981: doc: add note about preferring issues over TODO source code comments (master...202005-no-todo) https://github.com/bitcoin/bitcoin/pull/18981
< jonasschnelli> would it make sense to support BIP39 mnemonics in descriptors?
< jonasschnelli> it could work very much the same as xpriv
< bitcoin-git> [bitcoin] MarcoFalke pushed 16 commits to 0.20: https://github.com/bitcoin/bitcoin/compare/aa7c6858e6e4...17bdf2afaee0
< bitcoin-git> bitcoin/0.20 315ae14 João Barbosa: gui: Fix itemWalletAddress leak when not tree mode
< bitcoin-git> bitcoin/0.20 fb82173 Amiti Uttarwar: [net processing] ignore tx GETDATA from blocks-only peers
< bitcoin-git> bitcoin/0.20 1e73d72 Amiti Uttarwar: [net processing] ignore unknown INV types in GETDATA messages
< bitcoin-git> [bitcoin] MarcoFalke merged pull request #18973: [0.20] Final backports for rc2 (0.20...0_20_0rc2_final_backports) https://github.com/bitcoin/bitcoin/pull/18973
< MarcoFalke> ship it? 🤔
< MarcoFalke> The only things left is a shutdown bug (not a regression, doesn't have a fix anyway) and the wallet fix, which is tagged "waiting for author"
< MarcoFalke> the wallet bug is not a regression either, right?
< wumpus> yep
< wumpus> doing last minute things for rc2 now
< bitcoin-git> [bitcoin] laanwj pushed 2 commits to 0.20: https://github.com/bitcoin/bitcoin/compare/17bdf2afaee0...6f7f94a27687
< bitcoin-git> bitcoin/0.20 0793eca Wladimir J. van der Laan: qt: Pre-rc2 translations update
< bitcoin-git> bitcoin/0.20 6f7f94a Wladimir J. van der Laan: build: Bump RC to rc2
< bitcoin-git> [bitcoin] laanwj pushed tag v0.20.0rc2: https://github.com/bitcoin/bitcoin/compare/v0.20.0rc2
< wumpus> woohoooo!!!
< fanquake> 🚀
< fanquake> We made it
< wumpus> about time hehe
< wumpus> thanks for all your help
< MarcoFalke> 🚢
< jonasschnelli> Nice!
< bitcoin-git> [bitcoin] MarcoFalke pushed 3 commits to master: https://github.com/bitcoin/bitcoin/compare/e2f6866cca3e...951870807ea2
< bitcoin-git> bitcoin/master fa0e5b8 MarcoFalke: Add templated GetRandomDuration<>
< bitcoin-git> bitcoin/master 0000ea3 MarcoFalke: test: Add test for GetRandMillis and GetRandMicros
< bitcoin-git> bitcoin/master 9518708 MarcoFalke: Merge #18781: Add templated GetRandDuration<>
< bitcoin-git> [bitcoin] MarcoFalke merged pull request #18781: Add templated GetRandDuration<> (master...2004-randDur) https://github.com/bitcoin/bitcoin/pull/18781
< bitcoin-git> [bitcoin] ryanofsky opened pull request #18982: wallet: Minimal fix to restore conflicted transaction notifications (master...pr/cblock) https://github.com/bitcoin/bitcoin/pull/18982
< theStack> does anyone know what happened to bitcoinacks.com?
< instagibbs> theStack, pierre_rochard isn't maintaining it anymore but I think the source is all there
< theStack> instagibbs: fanquake: thanks! will try to run it locally, seems like a great project
< theStack> a pity though that there is no official site hosting this anymore, i guess almost one is running this locally, and it maybe is also a great help for new contributors
< theStack> s/one/no-one/
< jonatack> one project that is slowly beginning to have some utility is https://cli.github.com... it's not quite there yet but i'm starting to use it, for instance, to filter and list PRs by label or assignee
< jonatack> same for issues
< michaelfolkson> I wonder how much it work it would be to get bitcoinacks.com back up and maintain it. I should ask Pierre
< michaelfolkson> Did people get much use out of it?
< michaelfolkson> I don't know if the long term contributors used it as part of their decision making process for what to review or not
< michaelfolkson> For ACKs that GitHub utility tool you link to won't pick them up jonatack
< jonatack> michaelfolkson: idk how much the maintainers used it. i noticed that sometimes it didn't detect acks properly and needed updating.
< jonatack> it was helpful for seeing activity and filtering per author (and it reacted faster than github, for me), i liked it better than the github notifications
< michaelfolkson> jonatack: Really? I can't imagine it would be hard to pick up "Concept ACK" or "ACK" reliably... Maybe there is something I'm missing. People weren't following the guidance on how to communicate ACKs maybe?
< michaelfolkson> Have to be pretty militant on following the ACK communication guidance
< jonatack> michaelfolkson: i don't recall the exceptions, but you had tested ack, tACK, utACK, code review ACK, and the protocol changed a bit last june iirc, adding implementation ack and ACKing with context, the bitcoinacks code needed to keep up with the changes
< michaelfolkson> Yeah it did. But it looks like Pierre was still maintaining it up until January of this year
< wumpus> I liked bitcoinacks.com and did use it, was kind of disappointed that it went offline, but don't have time to maintain it myself either
< wumpus> even if the ACK counts weren't always exact, it was useful to see which PRs were getting attention from reviewers and could be considered for merge
< wumpus> AFAIK bitcoinacks consists of two parts, one that runs in the background and updates the database, and a web part (I happen to run the first part for x0f.org because it's also used for the x0f mastodon/twitter notifications bot), I don't know how the web part works
< bitcoin-git> [bitcoin] tarboss closed pull request #18961: gui: remove assert in walletcontroller & run setparent in gui-qt main thread (master...master) https://github.com/bitcoin/bitcoin/pull/18961
< jonatack> I wonder if it would make any sense to bring bitcoinacks, with pierre_rochard's permission of course, into https://github.com/bitcoin-core/ to see more attention
< * jonatack> (ducking if that's a bad idea)
< sipa> i never used it much, but no objection from me
< bitcoin-git> [bitcoin] dgenr8 opened pull request #18984: Remove unnecessary input blockfile SetPos (master...patch-1) https://github.com/bitcoin/bitcoin/pull/18984