Google Summer of Code-2010
Contents
Contact Details:
Name: Pradeepkumar Gayam
Email: in3xes@gmail.com
IRC Nick: in3xes (freenode.net)
Jabber ID: in3xes [AT] gmail.com (talk.google.com)My GSoC application on bitbucket.
Journal:
2010-06-23: Study shallow clone how they are related to parent delta
2010-06-24: Revlog experiments to improve performance
2010-06-25: More experiments, fixed the issue, so that it will not differ for old revlogs, still expriments needs to be done.
2010-06-26: Study wire-proto, understand how bundle, unbundle is being done.
2010-06-27: Week end
2010-06-28: More expreiments, found the reason for the performance issue, this paste explains. Conclusion: 'The number of patches to be applied increases at starting rev of new branch'.
2010-06-29: Update blog, journal, Attened GSoC meeting,
2010-06-30: Worked through bundle/unbundle code and understand wire-proto completely
2010-07-01: Worked through bundle/unbundle code and understand wire-proto completely
2010-07-02: - (Tried to work, but, unproductive day)
2010-07-03: - (another unproductive day 
)
2010-07-04: - Week end
2010-07-05: Worked on bundle/unbundle, it works for now, have to rewrite the patches,(Ugly code)
2010-07-06: Attended GSoC meeting on IRC, finished bundle/unbundle
2010-07-07: Pull from remote and localrepo partially working
2010-07-08: Pull, push, clone working over http repo this way.
2010-07-09: Support for sshrepo added.
2010-07-10: Looked into subrepo issues, sent a patch to recursively pull subrepo, and support pull form clones.
2010-07-11 Rewrote patches, day was less productive though
2010-07-12: Rewrote patches, sent them on mailing list
2010-07-21: Setup dev-env on new computer, import everything.
2010-07-22: -
2010-07-23: Look into Discovery Plan and some DAG algorithms
2010-07-24: Look into bts, Nothing much though
2010-07-25: Week end
2010-07-26: Modify work according the changes in wireproto unification.
2010-07-27: Refine patches according to suggestions in IRC.
2010-07-28: Ponder about compatibility matrix, No final conclusion
2010-07-29: --
2010-07-30: Work on new bundle format.
2010-07-31: Work on wire-protocol stuff.
2010-08-01: Week end.
2010-08-02:Work on wire-protocol stuff. Patches half ready.
Work Progress:
Few things related revlog:
1) A script by tonfa, proof for parent delta.
2) mpm explaining how space inefficiency is caused.
3) A python script in mercurial repo to shrink revlog by sorting in topological order.
4th Week:
Earlier in this week I started working on revlog, most of the work is already done by tonfa. He shared patches. All I did was understand what he did, and rewrite those patches with minor changes.
strategy:
As mpm suggested, I have changed the way new revision is being added to existing revlog, and make corresponding changes in creating a given revision of file. The crucial step (performance affecting step) is creating a given version of file. previously to create a given version of a file first we take base revision , to that we keep adding the deltas till given revision. Earlier deltas are added in linear manner. So creating a given revision of file is simply seeking O(1) times.
Defination of base in revlog is not given anywhere. From revlog, a base is the version where we add full text of file to the revlog instead of delta.
example scenario:
We want to create a R1 revision of a file. The parents of R1 are P1 and P2. Base of R1 is B1.
Consider a situation where P2 is null, and P1 < B1. In this case I simply can't take B1 and create R1. I have first find base and parents of P1 and construct P1. The same case might repeat. where parent of P1 is < base of P1. So, first I have to find a base which is ancestor of all the parents, then create a chain of deltas from that base to construct a given revision.
Output of --profile says that, what ever the decrease in the performance is caused only by this function which used for constructing the delta chain. So, I need to find a better algorithm to construct the delta chain. The current algorithm for constructing the delta chain is.
def deltachain(self, rev):
chain = []
while self.base(rev) != rev:
chain.append(rev)
rev = self.deltaparent(rev)
chain.reverse()
return rev, chain
def deltaparent(self, rev):
if self.base(rev) == rev:
return nullrev
elif self.flags(rev) & REVLOG_PARENTDELTA_FLAGS:
return self.parentrevs(rev)[0]
else:
return rev-1
5th Week:
In the starting of the week, I stopped working on revlog for sometime to look at other part of API. I studied abit about shallow clones, and parent delta's role in it. Though I didn't study in much detail, got general idea about how things work in shallow clones. Later worked on wire protocol abit.
After some gap I again started working on revlog performance, did some exprimentation, fixed some issues (which brought back the performace when the revlog is non-parent deltad). From the results I concluded that the decrease in the performance is bacause of number of patches being applied in to construct a revision of a file. In the previous post I wrote that revlog slowed down becase of the deltachain(), and deltaparent() functions are repeated being called. Thought that is one of the reason, but not the major reason. Some important results are pasted below.
(All the experiments are done on mercurial repo, Right now, I don't have good enough computer for larger repos )
- Old revlog, Normal repo
hg perfrevlog .hg/store/00manifest.i ! wall 0.570377 comb 0.570000 user 0.560000 sys 0.010000 (best of 18) hg verify --time Time: real 11.290 secs (user 10.790+0.000 sys 0.250+0.000)
- New revlog, Normal repo
hg perfrevlog .hg/store/00manifest.i ! wall 0.646474 comb 0.650000 user 0.640000 sys 0.010000 (best of 16) hg verify --time Time: real 15.930 secs (user 15.350+0.000 sys 0.290+0.000)
Final Week
After little modification in deltachain() finally I was able to make those patches work on current repos without much affecting performance. In the end deltachain() looks like:
def deltachain(self, rev, cache):
"""return chain of revisions to construct a given revision"""
chain = []
check = False
while self.base(rev) != rev and rev != cache:
chain.append(rev)
rev = self.deltaparent(rev)
chain.reverse()
if rev == cache:
check = True
return check, rev, chainResults:
With hg1.6.2:
hg verify --time Time: real 5.660 secs (user 5.510+0.000 sys 0.160+0.000)
With patches applied:
hg verify --time Time: real 5.800 secs (user 5.690+0.000 sys 0.100+0.000)
Which means decrease in performance is less than 3%
Work Remaining:
Wire protocol part is not implemented as it requires new bundle format. In push/pull/clone if we request a changegroup of changegroupsubset it has to redelta everytime on both server and client side. To be efficient new bundle format has to used. With new bundle format we can carry flags corresponding to each delta and its deltaparent. Next thing to do is implement a new changegroup to interact with new servers. As I already worked protocol it should not take much time to implement required changes.
Discussion about new bundle format can seen here