Re: [rfc] hide rs_buffers_t from public interface

On Wed, 2004-02-18 at 11:46, Martin Pool wrote:
> On 18 Feb 2004, Donovan Baarda <[email protected]> wrote:
> > In any case, flush is potentialy useful for different types of flush,
> > as used in zlib. I haven't yet hit a case with librsync where I have
> > really needed this, but I have used it a fair bit in zlib, so I can
> > imagine a need for it. I probably prefer a seperate flush method, but
> > guess a flush parameter would be more consistant.
> 
> That would be good.  I think that's fairly orthogonal to this
> discussion?

Yep... just threw it in while we were talking about API changes :-)

> > If it was implemented right, you would only need a single fixed
> > internal buffer of exactly block_len size. You don't really need data
> > to be contiguous to calculate the block sums, so you can just walk
> > over the fragment in the internal buffer, and onto the supplied input
> > buffer. When you reach the end of the input buffer, you only need to
> > copy the last non-matching block or block fragment into the internal
> > buffer for next time.
> 
> Yes.  I think this can be fixed just in scoop.c?

Yes. The current scoop.c needs to changed a fair bit. The API needs to
be changed to add get_md4sum(offset, length) and
get_rollsum(offset,length) methods that can span the internal and input
buffers, as well as a few other things. The current delta.c hardly uses
the scoop at all... the copy minimisation it attempted to do was so
broken I just forced it to copy everything to the input buffer and walk
through it directly.

I know exactly what it needs to look like in my head... will code it as
soon as I get some time.

> > By changing the API to always require a minimum of block_len
> > "lookahead" data on the input buffer, you can eliminate the input
> > buffer entirely. It then becomes the applications responsibility to
> > put the fragment left on the end of the input buffer onto the
> > beginning of the next input buffer with the extra data.
> 
> Another approach would be to make it behave well if the application
> gives us a lot of readahead, but not require it.
> 
> When the input buffer has insufficient readahead, we should *first*
> return to the application and see if it can fill out the buffer a bit
> more.  avail_in will be blocklen-1, so the application has to preserve
> this data.  If the application still doesn't give us any more, then we
> need to start accumulating data into an internal buffer.

The complexity would not be worth the minimal gain. If we need an
internal buffer at all, lets just use one.

> > bigger buffers won't help. 
> 
> Uh, I think they would avoid shuffling data around.
> 
> Imagine if we had an infinite-size buffer.  We could just always
> append to it, and never need to shuffle data back to the beginning.
> (We could, if we wanted, reset to the beginning when the buffer
> happens to be empty.)  The larger the buffer is, the more it
> approximates that case.

But even better is to avoid copying to the buffer at all... and we can
do that with the above fix to scoop.c.

The best way to avoid data shuffling is not to use a bigger buffer, but
to use a circular buffer. Remember data doesn't have to be contiguous to
calculate the checksums, which means you _can_ calculate the sums for
blocks that "wrap" past the end of the circular buffer.

That was another alternative I thought of, but if you process the data
off the input buffer directly, you never re-shuffle data on the internal
buffer anyway, so you don't need a circular buffer.

-- 
Donovan Baarda <[email protected]>
http://minkirri.apana.org.au/~abo/



-------------------------------------------------------
SF.Net is sponsored by: Speed Start Your Linux Apps Now.
Build and deploy apps & Web services for Linux with
a free DVD software kit from IBM. Click Now!
http://ads.osdn.com/?ad_id=1356&alloc_id=3438&op=click