--- Log opened Sun Oct 25 00:00:57 2020
01:31 -!- belcher_ [~belcher@unaffiliated/belcher] has joined #utreexo
01:35 -!- belcher [~belcher@unaffiliated/belcher] has quit [Ping timeout: 260 seconds]
02:03 -!- belcher_ is now known as belcher
14:18 -!- fogof [49a23865@c-73-162-56-101.hsd1.ca.comcast.net] has joined #utreexo
14:21 < fogof> Hey, a collaborator and I have been working on a fork of the utreexo project, and we had a question about the swapping mechanism.
14:23 < fogof> It seems like each hash is put in a location in the forest file which corresponds to its location in one of the binary trees, and that when leaves are deleted, the other leaves and hashes are moved around to reorganize the tree into the perfect binary forest structure.
14:28 < fogof> My question is this: If a single leaf is deleted from a large binary tree of size 2^{n+1}, and a tree of size 2^{n} already exists, isn't it necessary to move 2^n hashes to create another tree of size 2^{n+1}? This seems inefficient to me, since it means in the worst case, a deletion operation is superlinear in the number of elements being deleted.
14:28 < fogof> Is this case just particularly rare? Or is this operation faster in hardware?
19:44 -!- fogof [49a23865@c-73-162-56-101.hsd1.ca.comcast.net] has quit [Ping timeout: 245 seconds]
19:56 < adiabat> fogof: yes, large / high up swaps are costly for the forest-on-disk implementaion, which has everything written in-order
19:56 < adiabat> there are other representations that use pointers that don't have this problem, but those can have other trade-offs
19:57 < adiabat> kcalvinalvin got some data on the distributuion of swaps here: https://github.com/mit-dci/utreexo/issues/202
20:04 < adiabat> the distribution looks like 2^-x or so, which makes sense
20:05 < adiabat> so my guess is it's not actually that costly since the large ones don't happen very often.
20:06 < adiabat> But that's most of a guess; we don't yet have great data about which parts are slowing things down.  If the large swaps are a bottleneck we can use other designs to avoid the disk read/write
20:20 < kcalvinalvin> fwiw the cowForest thing doesn't do the whole schooching thing
20:20 < kcalvinalvin> The name sucks though because it's really a redirect-on-write but rowForest makes everything more confusing
20:22 < adiabat> haha "rowForest" would be great.  could just call it height forest instead :)
20:23 < kcalvinalvin> I wish I gave better names to things
20:35 < adiabat> yeah names are annoying
20:35 < adiabat> almost as annoying as getting structs from one computer to another...
21:49 < adiabat> ... well the client gets to height 429 now.  So that's better than the 381 it was stuck on
--- Log closed Mon Oct 26 00:00:58 2020