[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
Re: [tor-bugs] #13339 [Core Tor/Tor]: Prop140: Complete Consensus diffs / Merge GSoC project
#13339: Prop140: Complete Consensus diffs / Merge GSoC project
-------------------------------------------------+-------------------------
Reporter: mvdan | Owner: nickm
Type: enhancement | Status:
| assigned
Priority: High | Milestone: Tor:
| 0.3.1.x-final
Component: Core Tor/Tor | Version: Tor:
| 0.2.7
Severity: Normal | Resolution:
Keywords: gsoc, merge, tor-client, prop140, | Actual Points:
027-triaged-1-in, 028-triaged, pre028-patch, |
tor-dos, low-bandwidth, nickm- |
deferred-20160905, tor-03-unspecified-201612, |
sponsor4, TorCoreTeam201703 |
Parent ID: | Points: parent
Reviewer: | Sponsor:
| Sponsor4
-------------------------------------------------+-------------------------
Comment (by mvdan):
Hi Sebastian,
I had to re-read my own docs because I completely forgot what
calc_changes() even was :)
> According to the documentation of calc_changes() I would think that the
proper result would be unchanged, changed, unchanged, changed.
Admitting that I don't fully remember how this thing worked, I think
you're assuming too much.
For example, having [a a a a] and [a b a b], and the bits [0 1 1 0] and [0
1 0 1], what we will do is:
* change the second and third elements [a a] with [b]: [a b a]
* add a fourth element [b]: [a b a b]
The ed diff, if I recall correctly, should be something like (doing this
in my head, so could be wrong):
1,2cb
.
3ab
.
I understand you were expecting the bits to be [0 1 0 1] and [0 1 0 1].
Then, the diff would be something like:
2cb
.
4cb
.
Note that the two are valid. Yours is a bit smaller as far as bytes used,
but it's still the same number of operations.
If I remember correctly, calc_changes optimizes for number of lines
added/deleted in the diff, not for the size of the ed diff. This is
because it doesn't do an ed diff at all - it is done at a higher level, in
a func that calls it. It ended up with this result just like it could have
ended with yours - both mean four lines changed (deleted+added) in total.
In other words, the number of bits set to "1" across both bit vectors is
4.
Perhaps a way to get slightly smaller ed diffs would be to get
calc_changes to prefer the operator 'c' over 'a' and 'd'. But remember
that this operation should only be used in very small pieces of the
consensus, so I don't expect you'd be saving much at the cost of
complexity.
So TL;DR: the expected values are correct. Not the smallest ed diff nor
the one that a human would do, but one that is almost as small.
--
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/13339#comment:56>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online
_______________________________________________
tor-bugs mailing list
tor-bugs@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs