You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@subversion.apache.org by "Peter N. Lundblad" <pe...@famlundblad.se> on 2006/03/23 22:14:46 UTC
[PATCH] Further improve xdelta
Hi,
Continuing my little love affair, I found a pretty simple way to
significantly improve the speed of the xdelta algorithm.
This patch introduces a custom hash table instead ofusing apr_hash_t.
I choose open addressing to improve locality. I credit much of the
speedup to the fact that GCC (4.0) optimizes this algorithm quite
aggressively. In my tests with a few large binary files, the speed
increases by about 18%. I think the speedup should be lower when the
compared data streams are more similar, but I haven't tested that.
Comments?
(NOte, I'm going to leave xdelta itself after this commit, since I
don't see a point in tweaking it forever.)
Thanks,
//Peter
[[[
Optimize the xdelta algorithm by introducing a custom hash table instead
of using the general-purpose apr_hash_t.
* subversion/libsvn_delta/xdelta.c
(MATCH_BLOCKSIZE): Move earlier in the file.
(struct block): Rename from match; store the adler sum instead of the
length. Use apr_size_t for the position.
(struct blocks): New struct.
(add_block, find_block): New functions.
(init_blocks_table): Rename from init_matches_table. Init the custom
hash table.
(find_match): Use custom hash table instead of apr_hash_t.
(compute_delta): Use custom hash table. Move the check for a small
target before initializing the table.
]]]
Re: [PATCH] Further improve xdelta
Posted by Daniel Berlin <db...@dberlin.org>.
On Thu, 2006-03-23 at 14:32 -0800, Justin Erenkrantz wrote:
> On 3/23/06, Peter N. Lundblad <pe...@famlundblad.se> wrote:
> > Nope, but that's not in APR 0.9 anyway AFAICT.
>
> I would really like to avoid adding a custom data structure if we
> don't have to do so. If it means that only users with APR 1.0+ see
> the performance benefit, so be it as it means that the code stays much
> simpler. -- justin
Normally, i'd agree, but the rest of the techniques that one would use
to speed up xdelta's hashtable (which is where all the time is spent in
an algorithm like xdelta) would require a custom hash table anyway, and
it is likely that someone will eventually want to implement them.
See, for example, the hash table structure and hash used in
www.research.ibm.com/journal/rd/501/agarwal.pdf
to speed up their delta algorithm (such techniques are directly
applicable to xdelta's hash table).
--Dan
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: [PATCH] Further improve xdelta
Posted by "Peter N. Lundblad" <pe...@famlundblad.se>.
Garrett Rooney writes:
> On 3/27/06, Peter N. Lundblad <pe...@famlundblad.se> wrote:
>
> > I think the small amount of increased complexity is justified by the
> > performance win, so I'm going to commit this unless someone
> > objects.
>
> +1, I think you've done your homework with regard to the tradeoffs of
> the various solutions, and the custom hash table seems more than worth
> it in this case.
>
r19047.
Regards,
//Peter
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: [PATCH] Further improve xdelta
Posted by Garrett Rooney <ro...@electricjellyfish.net>.
On 3/27/06, Peter N. Lundblad <pe...@famlundblad.se> wrote:
> I think the small amount of increased complexity is justified by the
> performance win, so I'm going to commit this unless someone
> objects.
+1, I think you've done your homework with regard to the tradeoffs of
the various solutions, and the custom hash table seems more than worth
it in this case.
-garrett
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: [PATCH] Further improve xdelta
Posted by "Peter N. Lundblad" <pe...@famlundblad.se>.
Justin Erenkrantz writes:
> On 3/23/06, Peter N. Lundblad <pe...@famlundblad.se> wrote:
> > Nope, but that's not in APR 0.9 anyway AFAICT.
>
> I would really like to avoid adding a custom data structure if we
> don't have to do so. If it means that only users with APR 1.0+ see
> the performance benefit, so be it as it means that the code stays much
> simpler. -- justin
>
OK, folks. I've been fooling around with this some more the last days.
I tried Justin's suggestion of a custom hash function and it gave less
than half the speed improvement.
Then, I discovered an interesting fact about the adler32 checksum
algorithm (*). In my initial tests, I used big .wav files, which
turns out to be pretty "random". I decided to try some more realistic
data and used uncompressed .tar files of source code (svn 1.2.0, 1.2.3
and 1.3.0). This shows a dramatic slowdown compared with the original
code.
The problem is that the adler32 checksum doesn't make use of all bits
for small block sizes. Some tests I did indicate that the 11th to
16th bit of the checksum are not well distributed and since my first
hash function typically used the 12 low-order bits, this didn't work
out very well.
I've cured this using the following formula:
h = sum ^ (sum >> 12)
to include some higher-order bits in the mess.
The end result is that my patch gives about 15% speed improvements for
some differnt kinds of test data and Justin's suggestion gives us 5%.
(To be fair, I changed my implementation of Justin's suggestion to use
the same hash function that I changed to, but that lead to an
improvement of less than 1%.)
I think the small amount of increased complexity is justified by the
performance win, so I'm going to commit this unless someone
objects.
Thanks,
//Peter
*) I don't claim to be the first who discover this fact. See RFC 3309
for an explanation.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: [PATCH] Further improve xdelta
Posted by Garrett Rooney <ro...@electricjellyfish.net>.
On 3/24/06, Arlie Davis <ad...@stonestreetone.com> wrote:
> That seems to be an aesthetic reaction, which doesn't outweigh the real,
> measurable benefits of the performance work. I would prefer have to have
> this performance work checked in. Did you actually build both, and see a
> noticeable increase in binary size?
>
Justin's not objecting to binary size, he's objecting to additional
complexity in the code. That said, I suspect this is the kind of
place where a little extra complexity is worth it in return for the
speed gains. The xdelta code is very performance critical stuff.
-garrett
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
RE: [PATCH] Further improve xdelta
Posted by Arlie Davis <ad...@stonestreetone.com>.
That seems to be an aesthetic reaction, which doesn't outweigh the real,
measurable benefits of the performance work. I would prefer have to have
this performance work checked in. Did you actually build both, and see a
noticeable increase in binary size?
-- arlie
-----Original Message-----
From: justin.erenkrantz@gmail.com [mailto:justin.erenkrantz@gmail.com] On
Behalf Of Justin Erenkrantz
Sent: Friday, March 24, 2006 12:35 PM
To: Greg Hudson
Cc: dev@subversion.tigris.org
Subject: Re: [PATCH] Further improve xdelta
On 3/24/06, Greg Hudson <gh...@mit.edu> wrote:
> Did you look at the patch? The custom hash table is like 20 lines of
> code.
Of course, I did. So?
Code bloat should be treated with suspicion. It seems like there is enough
of an argument here - but it's mainly to do with the further optimizations
Dan mentioned - not this particular change. -- justin
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: [PATCH] Further improve xdelta
Posted by Justin Erenkrantz <ju...@erenkrantz.com>.
On 3/24/06, Greg Hudson <gh...@mit.edu> wrote:
> Did you look at the patch? The custom hash table is like 20 lines of
> code.
Of course, I did. So?
Code bloat should be treated with suspicion. It seems like there is
enough of an argument here - but it's mainly to do with the further
optimizations Dan mentioned - not this particular change. -- justin
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: [PATCH] Further improve xdelta
Posted by Greg Hudson <gh...@MIT.EDU>.
On Thu, 2006-03-23 at 14:32 -0800, Justin Erenkrantz wrote:
> I would really like to avoid adding a custom data structure if we
> don't have to do so. If it means that only users with APR 1.0+ see
> the performance benefit, so be it as it means that the code stays much
> simpler. -- justin
Did you look at the patch? The custom hash table is like 20 lines of
code.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: [PATCH] Further improve xdelta
Posted by Branko Čibej <br...@xbc.nu>.
Justin Erenkrantz wrote:
> On 3/23/06, Peter N. Lundblad <pe...@famlundblad.se> wrote:
>
>> Nope, but that's not in APR 0.9 anyway AFAICT.
>>
>
> I would really like to avoid adding a custom data structure if we
> don't have to do so. If it means that only users with APR 1.0+ see
> the performance benefit, so be it as it means that the code stays much
> simpler. -- justin
>
FWIW, we have a custom hash table in vdelta, too. Not that the cases are
strictly comparable, but IIRC the biggest win is better locality of
reference.
-- Brane
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: [PATCH] Further improve xdelta
Posted by Justin Erenkrantz <ju...@erenkrantz.com>.
On 3/23/06, Peter N. Lundblad <pe...@famlundblad.se> wrote:
> Nope, but that's not in APR 0.9 anyway AFAICT.
I would really like to avoid adding a custom data structure if we
don't have to do so. If it means that only users with APR 1.0+ see
the performance benefit, so be it as it means that the code stays much
simpler. -- justin
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: [PATCH] Further improve xdelta
Posted by "Peter N. Lundblad" <pe...@famlundblad.se>.
Justin Erenkrantz writes:
> On 3/23/06, Peter N. Lundblad <pe...@famlundblad.se> wrote:
> > This patch introduces a custom hash table instead ofusing apr_hash_t.
> > I choose open addressing to improve locality. I credit much of the
>
> Did you try doing an identity function to apr_hash_make_custom? -- justin
Nope, but that's not in APR 0.9 anyway AFAICT.
//Peter
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: [PATCH] Further improve xdelta
Posted by Justin Erenkrantz <ju...@erenkrantz.com>.
On 3/23/06, Peter N. Lundblad <pe...@famlundblad.se> wrote:
> This patch introduces a custom hash table instead ofusing apr_hash_t.
> I choose open addressing to improve locality. I credit much of the
Did you try doing an identity function to apr_hash_make_custom? -- justin
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org