--- Log opened Fri Mar 07 00:00:37 2025
00:37 -!- Holz [~Holz@user/Holz] has joined #bitcoin-core-pr-reviews
01:20 -!- greypw149508572 [~greypw@user/greypw] has joined #bitcoin-core-pr-reviews
01:24 -!- greypw149508572 [~greypw@user/greypw] has quit [Client Quit]
01:24 -!- greypw149508572 [~greypw@user/greypw] has joined #bitcoin-core-pr-reviews
03:03 -!- brunoerg [~brunoerg@2804:14d:5285:84b2::1000] has quit [Remote host closed the connection]
03:04 -!- brunoerg [~brunoerg@2804:14d:5285:84b2::1000] has joined #bitcoin-core-pr-reviews
03:04 -!- brunoerg_ [~brunoerg@2804:14d:5285:84b2::1000] has joined #bitcoin-core-pr-reviews
03:08 -!- brunoerg [~brunoerg@2804:14d:5285:84b2::1000] has quit [Ping timeout: 252 seconds]
03:11 -!- pyth [~pyth@user/pyth] has joined #bitcoin-core-pr-reviews
03:11 -!- ^Dan [~xxx@89.136.142.218] has joined #bitcoin-core-pr-reviews
03:14 -!- greypw149508572 [~greypw@user/greypw] has quit [Quit: Ping timeout (120 seconds)]
03:14 -!- greypw149508572 [~greypw@user/greypw] has joined #bitcoin-core-pr-reviews
03:23 -!- ^Dan [~xxx@89.136.142.218] has left #bitcoin-core-pr-reviews []
03:32 -!- rkrux [~rkrux@user/rkrux] has joined #bitcoin-core-pr-reviews
03:34 -!- brunoerg_ [~brunoerg@2804:14d:5285:84b2::1000] has quit [Remote host closed the connection]
03:35 -!- pyth [~pyth@user/pyth] has quit [Remote host closed the connection]
03:36 -!- brunoerg [~brunoerg@2804:14d:5285:84b2::1000] has joined #bitcoin-core-pr-reviews
03:43 -!- rkrux [~rkrux@user/rkrux] has quit [Quit: Client closed]
03:44 -!- rkrux [~rkrux@user/rkrux] has joined #bitcoin-core-pr-reviews
03:55 -!- rkrux [~rkrux@user/rkrux] has quit [Quit: Client closed]
03:58 -!- pyth [~pyth@user/pyth] has joined #bitcoin-core-pr-reviews
03:59 -!- pyth [~pyth@user/pyth] has quit [Client Quit]
04:14 -!- rkrux [~rkrux@user/rkrux] has joined #bitcoin-core-pr-reviews
04:23 -!- pyth [~pyth@user/pyth] has joined #bitcoin-core-pr-reviews
04:49 -!- rkrux [~rkrux@user/rkrux] has quit [Quit: Client closed]
05:01 -!- pyth [~pyth@user/pyth] has quit [Remote host closed the connection]
05:13 -!- rkrux [~rkrux@user/rkrux] has joined #bitcoin-core-pr-reviews
05:28 -!- rkrux [~rkrux@user/rkrux] has quit [Quit: Client closed]
05:31 -!- jon_atack [~jonatack@user/jonatack] has joined #bitcoin-core-pr-reviews
05:33 -!- rkrux [~rkrux@user/rkrux] has joined #bitcoin-core-pr-reviews
05:34 -!- jonatack [~jonatack@user/jonatack] has quit [Ping timeout: 268 seconds]
05:43 -!- rkrux [~rkrux@user/rkrux] has quit [Quit: Client closed]
05:46 -!- rkrux [~rkrux@user/rkrux] has joined #bitcoin-core-pr-reviews
05:51 -!- rkrux [~rkrux@user/rkrux] has quit [Client Quit]
06:12 -!- jon_atack [~jonatack@user/jonatack] has quit [Quit: WeeChat 4.5.2]
06:16 -!- jonatack [~jonatack@user/jonatack] has joined #bitcoin-core-pr-reviews
07:01 -!- jonatack [~jonatack@user/jonatack] has quit [Read error: Connection reset by peer]
07:04 -!- jonatack [~jonatack@user/jonatack] has joined #bitcoin-core-pr-reviews
07:06 -!- pinheadmz [~pinheadmz@hns-contributor.dev] has quit [Ping timeout: 244 seconds]
07:42 -!- pinheadmz [~pinheadmz@165.227.93.117] has joined #bitcoin-core-pr-reviews
07:51 -!- PaperSword [~Thunderbi@securemail.qrsnap.io] has quit [Quit: PaperSword]
08:05 -!- PaperSword [~Thunderbi@securemail.qrsnap.io] has joined #bitcoin-core-pr-reviews
08:07 -!- ryanofsky [russ@jumpy.yanofsky.org] has quit [Quit: ZNC 1.7.5 - https://znc.in]
08:08 -!- ryanofsky [~russ@jumpy.yanofsky.org] has joined #bitcoin-core-pr-reviews
08:16 -!- tnndbtc [~tnndbtc@user/tnndbtc] has joined #bitcoin-core-pr-reviews
08:17 < tnndbtc> sipa , would you be free so we can go through your comment in https://github.com/bitcoin/bitcoin/issues/29098#issuecomment-2706846092 ?
08:20 < sipa> tnndbtc: i'm here
08:21 < tnndbtc> Great, let me post my draft here:
08:21 < tnndbtc> Let me see if I understand your proposal correctly:
08:21 < tnndbtc> Originally, the performance degradation comes from:
08:21 < tnndbtc> ```
08:21 < tnndbtc> / fi
08:21 < tnndbtc> for (size_t i = 0; i < node.keys.size(); ++i) {
08:21 < tnndbtc>     ...
08:21 < tnndbtc>     ...
08:21 < tnndbtc>     for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + ZERO) | (std::move(sats[j - 1]) + sat));
08:21 < tnndbtc>     ...
08:21 < tnndbtc> }
08:21 < tnndbtc> ```
08:22 < sipa> tnndbtc: on IRC it's generally considered impolite to copy-paste text
08:22 < sipa> but ok!
08:22 < sipa> is it just due to the operator+ and operator| ?
08:24 < tnndbtc> sipa I see.  Sorry.  Is there another way so we can ...
08:24 < tnndbtc> Okay, the outer for loop is to go through available keys.  The problem is the inner for loop, which is to compare/sort out the optimal keys by operator |
08:25 < tnndbtc> My understanding of your proposal is that to break out when we get k available keys, is my understanding right?
08:25 < sipa> yes, it won't help for the 999-of-999 case
08:25 < sipa> but there are other options
08:27 < sipa> for example if k=n, there is no need to run this inner loop for anything other than j == sats.size() - 1
08:27 < sipa> i think
08:29 < sipa> the code currently builds an optimal witness for _every_ t-of-n, for all values of t, and then picks t=0 for dissatisfaction and t=k for satisfaction
08:30 < sipa> all other t values go unused
08:30 < sipa> based on the values of k and n, i think not all t values are always needed
08:31 < tnndbtc> Then the challenge is to have a general implementation on this logic: we still want the inner loop to do compare/sort to achieve the optimization.  Then there are cases it will take long time, example, 998 out of 999.
08:31 < tnndbtc> I see your point on other t values go unused.  Let me think...
08:32 < sipa> though, i think the real slowdown is the fact that this is quadratically much work
08:32 < sipa> oh, it may be cubic, and we can reduce it to quadratic for n-of-n
08:33 < sipa> your approach is linear, but maybe quadratic suffices
08:36 < tnndbtc> Yes, the real slowdown indeed is the quadratically much of work, when doing an additional sorting to get optimal size.
08:37 < tnndbtc> for quadratic suffice on the linear approach, do you mean the size increases quadratically?
08:39 < sipa> the amount of data produced is quadratic in size: for every t from 0 through n, a witness is produced that contains n elements
08:39 < sipa> but i think the operator+ itself does linear work on itself, so the total amount of work is cubic
08:41 < sipa> (lunch time, will be back after)
08:42 < tnndbtc> Sure, last message just in case you are still here: in future, would we have keys much bigger than 999?  If so, quadratic approach would be a potential problem.
08:47 -!- tnndbtc [~tnndbtc@user/tnndbtc] has left #bitcoin-core-pr-reviews []
08:53 < sipa> i don't think that's a big concern
08:53 < sipa> and if it is, it can always be addressed later
09:29 -!- tnndbtc [~tnndbtc@user/tnndbtc] has joined #bitcoin-core-pr-reviews
10:00 -!- grettke [~grettke@syn-184-055-133-000.res.spectrum.com] has joined #bitcoin-core-pr-reviews
10:01 -!- grettke [~grettke@syn-184-055-133-000.res.spectrum.com] has quit [Client Quit]
10:05 -!- pyth [~pyth@user/pyth] has joined #bitcoin-core-pr-reviews
10:29 -!- grettke [~grettke@syn-184-055-133-000.res.spectrum.com] has joined #bitcoin-core-pr-reviews
10:38 -!- pinheadmz [~pinheadmz@165.227.93.117] has quit [Quit: ZNC 1.7.5+deb4 - https://znc.in]
10:38 -!- pinheadmz [~pinheadmz@165.227.93.117] has joined #bitcoin-core-pr-reviews
10:47 -!- abubakarsadiq [uid602234@id-602234.hampstead.irccloud.com] has joined #bitcoin-core-pr-reviews
11:51 -!- pyth [~pyth@user/pyth] has quit [Read error: Connection reset by peer]
11:51 -!- pyth [~pyth@user/pyth] has joined #bitcoin-core-pr-reviews
11:58 -!- grettke [~grettke@syn-184-055-133-000.res.spectrum.com] has quit [Quit: grettke]
11:59 -!- grettke [~grettke@syn-184-055-133-000.res.spectrum.com] has joined #bitcoin-core-pr-reviews
12:37 -!- Talkless [~Talkless@mail.dargis.net] has joined #bitcoin-core-pr-reviews
12:51 -!- jonatack [~jonatack@user/jonatack] has quit [Read error: Connection reset by peer]
12:53 -!- jonatack [~jonatack@user/jonatack] has joined #bitcoin-core-pr-reviews
12:58 -!- jonatack [~jonatack@user/jonatack] has quit [Ping timeout: 272 seconds]
12:59 -!- jonatack [~jonatack@user/jonatack] has joined #bitcoin-core-pr-reviews
13:32 -!- brunoerg [~brunoerg@2804:14d:5285:84b2::1000] has quit [Remote host closed the connection]
14:16 -!- brunoerg [~brunoerg@2804:1600:11d:2c00:142e:56b0:3e2b:b700] has joined #bitcoin-core-pr-reviews
14:21 -!- brunoerg [~brunoerg@2804:1600:11d:2c00:142e:56b0:3e2b:b700] has quit [Ping timeout: 265 seconds]
14:22 -!- grettke [~grettke@syn-184-055-133-000.res.spectrum.com] has quit [Quit: grettke]
14:29 -!- Talkless [~Talkless@mail.dargis.net] has quit [Quit: Konversation terminated!]
14:49 -!- jonatack [~jonatack@user/jonatack] has quit [Read error: Connection reset by peer]
14:54 -!- abubakarsadiq [uid602234@id-602234.hampstead.irccloud.com] has quit [Quit: Connection closed for inactivity]
14:56 -!- jonatack [~jonatack@user/jonatack] has joined #bitcoin-core-pr-reviews
15:14 -!- grettke [~grettke@syn-184-055-133-000.res.spectrum.com] has joined #bitcoin-core-pr-reviews
15:55 -!- brunoerg [~brunoerg@2804:14d:5285:84b2::1000] has joined #bitcoin-core-pr-reviews
17:29 -!- grettke [~grettke@syn-184-055-133-000.res.spectrum.com] has quit [Quit: grettke]
17:58 -!- PaperSword1 [~Thunderbi@securemail.qrsnap.io] has joined #bitcoin-core-pr-reviews
17:59 -!- PaperSword [~Thunderbi@securemail.qrsnap.io] has quit [Ping timeout: 252 seconds]
17:59 -!- PaperSword1 is now known as PaperSword
18:20 -!- VonNaturAustreVe [~natur@user/vonnaturaustreve] has joined #bitcoin-core-pr-reviews
18:21 -!- VonNaturAustreVe [~natur@user/vonnaturaustreve] has quit [Remote host closed the connection]
18:46 -!- jonatack [~jonatack@user/jonatack] has quit [Read error: Connection reset by peer]
18:47 -!- jonatack [~jonatack@user/jonatack] has joined #bitcoin-core-pr-reviews
19:01 -!- grettke [~grettke@syn-184-055-133-000.res.spectrum.com] has joined #bitcoin-core-pr-reviews
19:15 -!- jonatack [~jonatack@user/jonatack] has quit [Ping timeout: 246 seconds]
19:16 -!- jonatack [~jonatack@user/jonatack] has joined #bitcoin-core-pr-reviews
22:14 -!- grettke [~grettke@syn-184-055-133-000.res.spectrum.com] has quit [Quit: grettke]
22:26 -!- grettke [~grettke@syn-184-055-133-000.res.spectrum.com] has joined #bitcoin-core-pr-reviews
22:35 -!- grettke [~grettke@syn-184-055-133-000.res.spectrum.com] has quit [Quit: grettke]
22:36 -!- grettke [~grettke@syn-184-055-133-000.res.spectrum.com] has joined #bitcoin-core-pr-reviews
22:37 -!- grettke [~grettke@syn-184-055-133-000.res.spectrum.com] has quit [Client Quit]
--- Log closed Sat Mar 08 00:00:38 2025