Differences between revisions 35 and 36
Revision 35 as of 2010-06-21 20:47:54
Size: 9227
Editor: Pradeepkumar
Comment:
Revision 36 as of 2010-06-21 20:51:18
Size: 6764
Editor: Pradeepkumar
Comment:
Deletions are marked like this. Additions are marked like this.
Line 27: Line 27:
  . * Investigation about merge revision.At merge revision node has two parents, delta should be taken against first or
Line 28: Line 29:
----
/!\ '''Edit conflict - other version:'''
 . * Optimization, and investigation for better implementation(If possible).
Line 31: Line 31:
----
 . * Investigation about merge revision.At merge revision node has two parents, delta should be taken against first or
 . * Optimization, and investigation for better implementation(If possible).

----
/!\ '''Edit conflict - your version:'''

----
 . * Investigation about merge revision.At merge revision node has two parents, delta should be taken against first or
 . * Optimization, and investigation for better implementation(If possible).

----
/!\ '''End of edit conflict'''

----
Line 80: Line 65:
----
/!\ '''Edit conflict - other version:'''
Line 83: Line 66:
----
Line 85: Line 68:
 . * Optimization, and investigation for better implementation(If possible).

----
/!\ '''Edit conflict - your version:'''

----
 . * Investigation about merge revision.
 . * Optimization, and investigation for better implementation(If possible).

----
/!\ '''End of edit conflict'''

----
 . * Optimization, and investigation for better implementation(If possible)
Line 124: Line 95:
----
/!\ '''Edit conflict - other version:'''
Earlier in this week I started working on revlog, most of the work is already done by tonfa. He shared patches with me. All I did was understanding what he did, and rerwrite those patches. With minor changes I rewrote the patches.
Line 127: Line 97:
----
Earlier in this week I started working on revlog, most of the work is already done by tonfa. He shared patches with me. All I did was understanding what he did, and rerwrite those patches. With minor changes I rewrote the patches. 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. previously to create a given version of a file first we take base revision of file, to that we keep adding the deltas till given revision. Earlier it deltas are added in linear manner. So creating a given revision of file is simply seeking O(1) times. But now it is not the case. 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. By using --profile what I found is, 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 nicer algorithm to construct the delta chain. The current algorithm for constructing the delta chain is given below.

## You can even more obfuscate your email address by adding more uppercase letters followed by a leading and trailing blank.
CategoryHomepage

----
/!\ '''Edit conflict - your version:'''

----
Earlier in this week I started working on revlog, most of the work is already done by tonfa. He shared patches with me. All I did was understanding what he did, and rerwrite those patches. With minor changes I rewrote the patches. '''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. previously to create a given version of a file first we take base revision of file, to that we keep adding the deltas till given revision. Earlier it deltas are added in linear manner. So creating a given revision of file is simply seeking O(1) times. But now it is not the case.
'''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. previously to create a given version of a file first we take base revision of file, to that we keep adding the deltas till given revision. Earlier it deltas are added in linear manner. So creating a given revision of file is simply seeking O(1) times. But now it is not the case.
Line 149: Line 109:

----
/!\ '''End of edit conflict'''

----

Google Summer of Code-2010

I am interested in "Parent delta". I can also work on conversion tools. But I am mainly focusing on Parent Delta Plan.

A word about project:

Mercurial calculates diffs against previous revision rather than parent. In some cases this implementation is space inefficient, and it is more sensible to store deltas against parent. This project is about implementing Parent Delta Plan. This implementation changes the structure of revlogs, so wire protocol has to be extended to allow backward compatibility.

============================================================================

Proposal

TO DO(Tentative): Major:

  • Changes in revlog
  • Changes in wire protocol

Changes in revlog:

  • Change revlog structure, now it appends the next delta to existing data.This helps in reconstrfucting a revision at O(1) seeks. If

parent delta is implemented better compression can be achieved but, may have to compromise with number of seeks.

  • Current:Linear delta model

    • * O(1) seeks to create any revision.
  • Parent delta model
    • ** I think this can be completed quickly, tonfa shared patches for this***
    • * An intelligent algorithm to reduce number of seeks to reconstruct any revision.I think constructing revision is not straight forward as it is now. It's not going to be linear.Right now constructing a revision is simply applaying each block of data to a base till the revision required.
    • * Investigation about merge revision.At merge revision node has two parents, delta should be taken against first or
  • * Optimization, and investigation for better implementation(If possible).

Changes in wire protocol:

  • Changes in wire protocol to allow backward computability.
  • Implementation of changes according to old, new servers,client, repos.
  • Rigorous testing
  • Integrating with other's work.(Changeset discovery, Lightweight copies/renames)

About Me:

  • I am student at Indian Institute of Technology, Roorkee. I am currently pursing third year of 5 years degree, Mathematics as major. I am a Linux enthusiast. Interested in open source. I have been learning C,Python. Some of my projects can be found on github ( http://www.github.com/in3Xes ). I have never got opportunity to contribute to open source. GSoC would be stepping stone for that.

  • I am project leader in IMG ( Information Management Group, IIT Roorkee, http://www.iitr.ac.in/IMG/ ), a group which manages intranet, student databases, institute website. I have worked on PHP, Java in web development.

Contact Information:

  • Name: Pradeepkumar Gayam

    Email: in3xes@gmail.com

  • IRC Nick: in3xes (freenode.net)
  • Jabber ID: in3xes [AT] gmail.com (talk.google.com)

Schedule:

  • I would start coding well before the schedule given in the time line. My final exams will end by May-15th. I can start working rigorously shortly after exams. Till May-15th(or 24th according to time line) I will be reading code, documentation, getting used to coding style, getting ready to start coding, little experimentation etc.

Timeline

Changes in revlog structure: [Total 3 weeks]

  • Parent delta model:
    • * An intelligent algorithm to reduce number of seeks to reconstruct any revision.I think constructing revision is not straight forward as it is now. It's not going to be linear.
  • [(It can take 1 1/2 to 2 weeks to bring it to working stage, Roughly around 5th-Jun)]
  • * Investigation about merge revision.
  • * Optimization, and investigation for better implementation(If possible)
  • * Continuous parallel testing.
    • [( I would finish testing and other work nearly in 10 days, by 15th-Jun)]

Changes in wire protocol:[Total 3 to 3 1/2 weeks]

  • Changes in wire protocol to allow backward computability.
    • [(For midterm evaluation, this may not be complete, but significant part of it)]
    • * Implementation of changes according to old, new servers,client, repos.
  • Rigorous testing.
    • * [(I will start testing shortly after mid-term evaluation, i.e., around 18th-July, would take a week to complete)]
    • * Integrating with other's work. [ ( Remaining time, depending upon other students)]

Link to my GSoC application on bitbucket.org

Work Progess:

Couple for things that are related to revlog

1) A script by tonfa, proof for parent delta.

2) mpm explaining how space inefficiency is caused.

3) A python script to shrink revlog by sorting topological order in mercurial repo.

Earlier in this week I started working on revlog, most of the work is already done by tonfa. He shared patches with me. All I did was understanding what he did, and rerwrite those patches. With minor changes I rewrote the patches.

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. previously to create a given version of a file first we take base revision of file, to that we keep adding the deltas till given revision. Earlier it deltas are added in linear manner. So creating a given revision of file is simply seeking O(1) times. But now it is not the case.

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.

By using --profile what I found is, 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 nicer algorithm to construct the delta chain. The current algorithm for constructing the delta chain is given below.

CategoryHomepage

Pradeepkumar (last edited 2010-10-22 18:17:21 by mpm)