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