--- Log opened Fri May 22 00:00:28 2020
00:35 -!- jb55 [~jb55@gateway/tor-sasl/jb55] has quit [Remote host closed the connection]
00:36 -!- jb55 [~jb55@gateway/tor-sasl/jb55] has joined #utreexo
07:57 < adiabat> swapInRow needs forestRows so it can give it to swapIfDescendant, which uses it for parentMany
07:58 < adiabat> I guess len(collapses) will usually be the same as forestRows
07:58 < adiabat> we probably don't have good testing for cases where forestRows is higher than it needs to be
07:59 < adiabat> it is kindof a pain to have numLeaves and forestRows as separate things.  it would totally be possible to get rid of forestRows
07:59 < adiabat> and just compute it on the fly from numLeaves the way pollard does it
07:59 < adiabat> I think that will be slower, which is why I put in the forestRows stuff, but actually I never measured how much slower
08:00 < adiabat> maybe there's hardly any difference, and it could be simplified to not have to deal with independed forestRows..
09:40 < kcalvinalvin> PR by a new person!
09:42 < adiabat> heh yeah cool
09:42 < adiabat> oh also just saw #126
09:43 < adiabat> hmmm should either merge or close #124... I don't actually want a mutex there though, but like... yeah that does need to be fixed
09:43 < adiabat> maybe mutex now and put a //TODO: remove this mutex...
09:43 < kcalvinalvin> That works
09:44 < ja> adiabat: i guess forestRows can be calculated with an arithmetic expression? just a few assembly instructions no? i don't think that would be measurable
09:44 < ja> but i don't know how you test performance
09:46 < ja> adiabat: even if it has to pass it to swapIfDescendent, it could just pass len(collapses)... i guess i just prefer fewer arguments because i am not convinced of the performance hit
09:46 < ja> the problem with inter-dependent arguments is that there is little checking for consistency, and that would indeed bloat the code
09:47 < adiabat> ja: for the forest right now, it can't be calculated
09:47 < adiabat> the performance hit would be due to a pretty big change in how forest would work without having an independent forestRows
09:48 < ja> ah ok, so we can't do that
09:48 < adiabat> it would potentially call reMap() more ofent
09:48 < adiabat> *often
09:48 < adiabat> well we *can*, it just needs a reMap down function
09:48 < rjected> adiabat: I can update #124 w/ a TODO for removing the mutex, it's probably a good idea to write some benchmarks for stuff so we can see actual performance change in general on a small scale, but that's out of scope for 124
09:49 < adiabat> right now just gives an error and says "row reduction not implemented", but could implement that and then keep forestRows and numLeaves in sync
09:49 < adiabat> rjected: ok sure, yeah I can merge it as a temporary thing.  The real issue is that it's duplicating hashing work, which probably doesn't slow it down *that* much
09:50 < adiabat> but still... kindof ugly to have that, it's basically a bug
09:50 < rjected> yup, I can look into the duplicate hashing
09:51 < adiabat> ja: forestRows is independent so that it can be "too high" and stay at eg. 8 when numLeaves goes from 150 to 100
09:51 < rjected> If noone else is
09:51 < adiabat> yeah I ... think I know where it is
09:51 < adiabat> dedupeSwapDirt() doesn't actually dedupe
09:52 < adiabat> within it's arguments
09:52 < rjected> oh hmm
09:52 < adiabat> it might be as simple as doing that
09:52 < ja> adiabat: hmmm is that because 2^8 = 128 and 100 is below 128?
09:52 < adiabat> ja: right, so forestRows should go down to 7
09:52 < adiabat> but instead it just stays at 8, and there's a bunch of empty space
09:52 < ja> yeah ok, i kinda get it
09:53 < adiabat> the thinking is... what if in the actual usage, you get right around a threshold, like 65535 leaves or something
09:53 < adiabat> and it goes up and down every block, and keeps calling reMap(), which is very slow
09:54 < adiabat> but I don't think it actually does that.  But maybe it's a risk.  So it does add a bit of complexity to have a separatre forestRows
09:54 < ja> it's kinda like garbage collection, no?
09:54 < adiabat> kindof, yeah, where it instead just leaves unused memory
09:54 < adiabat> to avoid collecting
09:54 < adiabat> because it knows that numLeaves will go back up pretty soon
09:55 < adiabat> so don't free the memory you'll just have to allocate again soon
09:56 < ja> i think i will understand it more once i write some more tests for my haskell impl
09:56 < adiabat> ok, sounds good.  Yeah it is one of the weirder aspects, and maybe a premature optimization
09:56 < kcalvinalvin> speaking of that, is the haskell repo open source?
09:57 < kcalvinalvin> Would be cool to look at it
09:57 < ja> yeah, it's just my fork, it's the cgo branch
09:57 < kcalvinalvin> ah ok
09:57 < adiabat> but it does feel that especially in an adversarial setting, someone could try to push numLeaves up and down over a power of 2 to harass bridge nodes
09:57 < ja> kcalvinalvin, it's pretty dumb right now, just a function for function port. just bought the optics book, would be cool if some optics could apply
10:01 < ja> adiabat: it's an interesting problem for sure, this tradeoff between minimal data usage and performance over many operations. it just irks the haskeller in me when something is not minimal . but of course i have to concede that it shouldn't be DoSable
10:08 < adiabat> ja: yeah there might be a better way that avoids the complexity, not sure
10:08 < adiabat> since there currently is forestRows, it probably makes sense to pre-allocate a lot and start at forestRows = 20 or so
10:10 < ja> i find the porting makes me understand the data dependencies. i like splitting things into pure functions since the mutable algorithms are easier to comprehend once they are segregated from the pure functions, which can be treated as black boxes, kinda
10:11 < ja> it's funny how this even carries over into go, imho. if a go function takes only slices of primitives, a reader knows that the callee can't mutate that
10:13 < ja> adiabat: but it would be a small speed up no? if i understand correctly, forestrows can only grow. so the time lost is because a batch init of a large tree is faster than a few remaps
10:14 < ja> but are those remaps so expensive?
10:33 < adiabat> yeah remap is really expensive
10:33 < adiabat> O(n) where n is numLeaves
14:06 -!- achow101 [~achow101@unaffiliated/achow101] has quit [Ping timeout: 264 seconds]
15:01 -!- achow101 [~achow101@unaffiliated/achow101] has joined #utreexo
--- Log closed Sat May 23 00:00:30 2020