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

[Aaron Bentley]

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
> > worthless?
> >    
>
> 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
> side.  
>  
Okay, I see what you mean now. 
base0 -> patch1
patch1 -> patch2
patch1-> patch3
base0->patch4
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.

Aaron