Re: RFC: New diff-delta.c implementation
From: Junio C Hamano <hidden>
Date: 2016-06-15 22:42:24
Nicolas Pitre [off-list ref] writes:
Well, actually I was measuring a 10% speed improvement with a quick and naive (not memory efficient) approach for pack-objects with the current algorithm. ... The idea to avoid memory pressure is to reverse the window processing such that the object to delta against is constant for the entire window instead of the current logic where the target object is constant. This way there would be only one index in memory at all time.
Your are right. The first led to the latter unexplored idea.
I expect to be offline most of the day today, and have other
things I can work on for the next few days anyway, so if you or
somebody else have an inclination and energy to reverse the
delta window, I would appreciate that.
Maybe the calling convention of diff-delta.c would become
something like this?
struct delta_index; /* opaque to the caller; implementation
* defines what's in it.
*/
/* returns a newly allocated struct delta_index.
* input "buf" pointer can be stored in the struct, but "buf"
* does not belong to diff-delta module (i.e. borrowed reference).
*/
struct delta_index *delta_index(
void *buf, /* input: from buffer */
unsigned long size, /* input: from size */
);
/* ... so free the structure and its internal data, but
* do not free the borrowed reference!
*/
void free_delta_index(struct delta_index *);
/* Take "from", an already preprocessed delta_index for the
* traditional from_buffer/from_size, and to_buf/to_size, and
* produce delta in newly allocated buffer (caller should
* free() when it is done), and return the result size in
* *delta_size. Stop early if the result would exceed max_size.
*/
void *diff_delta(
struct delta_index *from, /* input: prepared by delta_index() */
void *to_buf, /* input: destination buffer */
unsigned long to_size, /* input: destination size */
unsigned long *delta_size, /* output: result size */
unsigned long max_size /* input: do not waste cycles if
you cannot generate result
smaller than this */
);
and the calling convention would be:
struct unpacked *s, *d;
unsigned long max_size;
/* precompute the index */
struct delta_index *src = delta_index(s->data, s->entry->size);
/* do the delta */
void *delta_buf = diff_delta(src, d->data, d->entry->size,
&sz, max_size);
/* do useful thing here on delta_buf and sz */
free(delta_buf);
/* the caller can reuse *src with other *d,
* but when it is done...
*/
free_delta_index(src);