[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Gnu-arch-users] Re: RFC: arch protocol, smart server, and tla imple

From: Aaron Bentley
Subject: Re: [Gnu-arch-users] Re: RFC: arch protocol, smart server, and tla implementation prototypes
Date: Thu, 05 Feb 2004 21:23:27 -0500
User-agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.6b) Gecko/20031205 Thunderbird/0.4

Chris Gray wrote:

On 5 Feb 2004, Aaron Bentley wrote:
Chris Gray wrote:
My message was that
skiplists are a data structure that you should consider for reasons
of efficiency, simplicity, and size.
How would a skip list be used in this context?  The paper you
reference shows the user of skiplists for search, insertion and
deletion, but how does that apply to a server that must decide what
requests are worthy of creating and caching, and which are

I'm arguing against the creation of a smart server I guess.
Currently, when you commit a patch in arch, it is like you are adding
a new element to a linked list.  I'm saying that we could change the
data structure to a skiplist and keep the dumb server.  All of the
summary deltas and data structure maintenance would happen client
Okay, I see what you mean now. base0 -> patch1
patch1 -> patch2
patch1-> patch3
etc, etc.

Let's assume that some changes accumulate, (changes made to different parts of files), and some do not (changes made to the same part of the file). Therefore this approach will increase the storage space. It will store some of the differences between base0 and patch1 twice, and store some of the differences between patch1 and patch2 three times.

It will reduce the amount of data need to produce a revision, because some changes do not accumulate. Also, as the amount of change grows, hunks can be merged, reducing the overhead.

To produce deltas from previous versions, we'll need the ability to compose changesets. The alternative is to build the from-revision as necessary, which would be quite burdensome.

Committing with powers of two has similar properties, but I think power-of-two would be more predictable and verifiable.

But on the whole, I'd rather not change the commit format. Better to just make it a server optomization.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]