Google Summer of Code-2010
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
applicationon bitbucket.
Journal:
2010-06-23: Study shallow clone how they are related to parent delta,
Result : Need a deeper insight.
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.
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