You are viewing a plain text version of this content. The canonical link for it is here.
Posted to users@subversion.apache.org by T'aZ <ta...@punkass.com> on 2005/10/23 15:30:01 UTC
Complexity of creating a new revision.
Hi!
I'm studying the complexity of various operations in svn
i'll take creating a new tag for example
i've understood that this results in a new revision tree and in this tree there is now a node poiting to revision X of a particular path
this operation is said to take a constant time
this is were a disagree , because according to http://subversion.tigris.org/files/documents/15/17/svn-design.html#Diffy%20Storage
the vector of trees is not stored as complete copies in the repository,
it's encoded as a series of "deltas"
so when you use the FSFS or the BDB backend, you have to read/adjust O(log(n)) deltas (according to svn/trunk/notes/skip-deltas )
so this is *not* done in constant time, right ?
an other question:
since accessing a given revision number costs O(log(n))
when we have this revision, nodes poiting to a different revision tree are not accessible, svn has to go again through O(log(n)) deltas , and this, for each nodes not directly accessible ?
thanks in advance for your answers :)
--
T'aZ |Jabber:taz-007@jabber.org|GPG keyID:E051925D|http://taz.prout.be
*They that can give up essential liberty to obtain a little temporary
safety deserve neither liberty nor safety.* Benjamin Franklin 1759
*Beaucoup,vite,loin,mal.* http://www.cl.cam.ac.uk/~rja14/tcpa-faq.html
---------------------------------------------------------------------
To unsubscribe, e-mail: users-unsubscribe@subversion.tigris.org
For additional commands, e-mail: users-help@subversion.tigris.org
Re: Complexity of creating a new revision.
Posted by T'aZ <ta...@punkass.com>.
On Sun, 23 Oct 2005 16:59:48 -0400
Daniel Berlin <db...@dberlin.org> wrote:
> > yes, only a new reference must be created pointing to the data , but since this new reference adds a new revision, it must be encoded as a delta against a previous one (in the fsfs case) or some deltas must be recreated (in the bdb case)
> > no ?
>
> No.
> A copy does not actually copy anything.
> You only need to say "This new dir has the contents of <revision x, dir
> y>"
>
> No actual representation is necessary for the new dir, becuause
> <revision x, dir y>, will never change.
>
> If you go look at what fsfs does when you create a copy, you'll see that
> it is just going to create 4 lines in a revision file, specifying
> exactly this information.
you are right, i was wrong thinking that deltas were used in the
directory structure too! but since each revision contains the required
node structure , it's much simpler, and thus allow making a copy in
constant time :D
thanks a lot for your support daniel & miha :D
--
T'aZ |Jabber:taz-007@jabber.org|GPG keyID:E051925D|http://taz.prout.be
*They that can give up essential liberty to obtain a little temporary
safety deserve neither liberty nor safety.* Benjamin Franklin 1759
*Beaucoup,vite,loin,mal.* http://www.cl.cam.ac.uk/~rja14/tcpa-faq.html
---------------------------------------------------------------------
To unsubscribe, e-mail: users-unsubscribe@subversion.tigris.org
For additional commands, e-mail: users-help@subversion.tigris.org
Re: Complexity of creating a new revision.
Posted by Daniel Berlin <db...@dberlin.org>.
On Sun, 2005-10-23 at 19:34 +0200, T'aZ wrote:
> On Sun, 23 Oct 2005 18:50:57 +0200
> Miha Vitorovic <mv...@nil.si> wrote:
>
> > > the vector of trees is not stored as complete copies in the repository,
> > > it's encoded as a series of "deltas"
> > > so when you use the FSFS or the BDB backend, you have to read/adjust
> > > O(log(n)) deltas (according to svn/trunk/notes/skip-deltas )
> > > so this is *not* done in constant time, right ?
> >
> > Not as I understand it. To recreate the contents of a given revision, sure
> > you need to go through all the diffs, to get it. But to create a copy of a
> > given tree at revision X, all you need to do is "create copy of a tree at
> > revision X", that is you create a new reference to the data, without
> > actually copying or recreating that data. That will be done, when somebody
> > tries to read the contents of this copy. I guess in the context of a *nix
> > FS, this would be like a hard link to a directory.
>
> yes, only a new reference must be created pointing to the data , but since this new reference adds a new revision, it must be encoded as a delta against a previous one (in the fsfs case) or some deltas must be recreated (in the bdb case)
> no ?
No.
A copy does not actually copy anything.
You only need to say "This new dir has the contents of <revision x, dir
y>"
No actual representation is necessary for the new dir, becuause
<revision x, dir y>, will never change.
If you go look at what fsfs does when you create a copy, you'll see that
it is just going to create 4 lines in a revision file, specifying
exactly this information.
--Dan
---------------------------------------------------------------------
To unsubscribe, e-mail: users-unsubscribe@subversion.tigris.org
For additional commands, e-mail: users-help@subversion.tigris.org
Re: Complexity of creating a new revision.
Posted by T'aZ <ta...@punkass.com>.
On Sun, 23 Oct 2005 18:50:57 +0200
Miha Vitorovic <mv...@nil.si> wrote:
> > the vector of trees is not stored as complete copies in the repository,
> > it's encoded as a series of "deltas"
> > so when you use the FSFS or the BDB backend, you have to read/adjust
> > O(log(n)) deltas (according to svn/trunk/notes/skip-deltas )
> > so this is *not* done in constant time, right ?
>
> Not as I understand it. To recreate the contents of a given revision, sure
> you need to go through all the diffs, to get it. But to create a copy of a
> given tree at revision X, all you need to do is "create copy of a tree at
> revision X", that is you create a new reference to the data, without
> actually copying or recreating that data. That will be done, when somebody
> tries to read the contents of this copy. I guess in the context of a *nix
> FS, this would be like a hard link to a directory.
yes, only a new reference must be created pointing to the data , but since this new reference adds a new revision, it must be encoded as a delta against a previous one (in the fsfs case) or some deltas must be recreated (in the bdb case)
no ?
--
T'aZ |Jabber:taz-007@jabber.org|GPG keyID:E051925D|http://taz.prout.be
*They that can give up essential liberty to obtain a little temporary
safety deserve neither liberty nor safety.* Benjamin Franklin 1759
*Beaucoup,vite,loin,mal.* http://www.cl.cam.ac.uk/~rja14/tcpa-faq.html
---------------------------------------------------------------------
To unsubscribe, e-mail: users-unsubscribe@subversion.tigris.org
For additional commands, e-mail: users-help@subversion.tigris.org
Re: Complexity of creating a new revision.
Posted by Miha Vitorovic <mv...@nil.si>.
T'aZ <ta...@punkass.com> wrote on 23.10.2005 17:30:01:
> Hi!
>
> I'm studying the complexity of various operations in svn
>
> i'll take creating a new tag for example
> i've understood that this results in a new revision tree and in this
> tree there is now a node poiting to revision X of a particular path
>
> this operation is said to take a constant time
> this is were a disagree , because according to http://subversion.
> tigris.org/files/documents/15/17/svn-design.html#Diffy%20Storage
>
> the vector of trees is not stored as complete copies in the repository,
> it's encoded as a series of "deltas"
> so when you use the FSFS or the BDB backend, you have to read/adjust
> O(log(n)) deltas (according to svn/trunk/notes/skip-deltas )
> so this is *not* done in constant time, right ?
Not as I understand it. To recreate the contents of a given revision, sure
you need to go through all the diffs, to get it. But to create a copy of a
given tree at revision X, all you need to do is "create copy of a tree at
revision X", that is you create a new reference to the data, without
actually copying or recreating that data. That will be done, when somebody
tries to read the contents of this copy. I guess in the context of a *nix
FS, this would be like a hard link to a directory.
Br,
---
Miha Vitorovic
Inženir v tehničnem področju
Customer Support Engineer
NIL Data Communications, Tivolska cesta 48, 1000 Ljubljana, Slovenia
Phone +386 1 4746 500 Fax +386 1 4746 501 http://www.NIL.si
---------------------------------------------------------------------
To unsubscribe, e-mail: users-unsubscribe@subversion.tigris.org
For additional commands, e-mail: users-help@subversion.tigris.org