You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@subversion.apache.org by Stefan Fuhrmann <st...@alice-dsl.de> on 2010/03/28 12:50:38 UTC
[PATCH] delta_files() speedup 2/3: keyword substitution
Hi devs,
this is part of the delta_files() speedup patch series:
http://svn.haxx.se/dev/archive-2010-03/0604.shtml
translate_chunk spends most of its time in a loop
looking for the next '$' or newline. The call to strchr
is excessively expensive since the 'interesting' string
is no longer than 3 chars.
It is much more efficient to use a simple lookup table
(boolean array) that tells us whether a certain char
is 'interesting' or not. Since we call it for almost every
char in the file, the initialization overhead amortizes
within the first two lines of the respective file.
Performance gain is ~9%:
s~$ time ~/1.7-928181/svn export --ignore-externals -q $REPO/trunk /dev/shm/t
real 0m3.727s
user 0m3.189s
sys 0m0.542s
~$ time ~/1.7-patched/svn export --ignore-externals -q $REPO/trunk /dev/shm/t
real 0m3.410s
user 0m2.872s
sys 0m0.537s
-- Stefan^2.
[[[
Optimize the search for 'interesting' characters that
control the keyword substitution. For details see
http:// ...
* subversion/libsvn_subr/subst.c
(translation_baton): the 'interesting' member is now
a boolean array.
(create_translation_baton): adapt initialization code
(translate_chunk): eliminate call to strchr
patch by stefanfuhrmann < at > alice-dsl.de
]]]
Re: [PATCH] delta_files() speedup 2/3: keyword substitution
Posted by Stefan Fuhrmann <st...@alice-dsl.de>.
On Monday 29 March 2010 23:38:04 you wrote:
> > From: Philip Martin [mailto:philip.martin@wandisco.com]
> > Julian Foad <ju...@wandisco.com> writes:
> > >> * subversion/libsvn_subr/subst.c
> > >> (translation_baton): the 'interesting' member is now
> > >> a boolean array.
> > >> (create_translation_baton): adapt initialization code
> > >> (translate_chunk): eliminate call to strchr
> > >>
> > >> patch by stefanfuhrmann < at > alice-dsl.de
> > >> ]]]
> > >
> > > This patch looks lovely, from the point of view of a read-through
> > > review.
> >
> > Agreed.
> >
> > To get rid of the initialization we could use 4 static constant arrays
> > (we could even partially overlap them to save memory), but that's
> > probably not a significant improvement.
>
> I'm not sure how all this compares to just three byte compares, but with a
> only a few kb first level cache in most current x86 processors it might be
> even more optimal to just do the comparison in code.
>
> But I think any solution that avoids calling the locale dependent strchr()
> function will help here and the details between the table and in-code
> variants are probably not measurable.
Since the lookup array is very small (1/4KB), it fits easily into L1.
In fact, the initialization puts it there more efficiently than an
initial load from RAM could ever be. And it should take no more
than 50 clock ticks on contemporary processors, i.e. a typical
L3 latency.
Therefore, using a 3 or 4 pre-calculated tables will increase code
complexity and potentially be slower. That slowdown would hardly
be measurable, though.
Using 3 (additional) compares has two problems. First, it would
result in up to 5 jump operations closely together. That overloads
the branch prediction logic causing pipeline stalls (no more than
3 in any instruction decoder window). More importantly, we had
to decide dynamically, what tests to perform ('$', '\r\n' or both).
That would definitely be slower than the 2..3 cycles per iteration
achieved by the original patch.
-- Stefan^2.
Re: [PATCH] delta_files() speedup 2/3: keyword substitution
Posted by Stefan Fuhrmann <st...@alice-dsl.de>.
On Tuesday 30 March 2010 15:14:02 you wrote:
> "Bert Huijben" <be...@qqmail.nl> writes:
> > But I think any solution that avoids calling the locale dependent
> > strchr() function will help here and the details between the table and
> > in-code variants are probably not measurable.
>
> Agreed. I've committed the patch in r929125, and the delta patch in
> r929124. I'm not planning to apply the write buffering patch.
Thanks!
-- Stefan^2.
Re: [PATCH] delta_files() speedup 2/3: keyword substitution
Posted by Philip Martin <ph...@wandisco.com>.
"Bert Huijben" <be...@qqmail.nl> writes:
> But I think any solution that avoids calling the locale dependent strchr()
> function will help here and the details between the table and in-code
> variants are probably not measurable.
Agreed. I've committed the patch in r929125, and the delta patch in
r929124. I'm not planning to apply the write buffering patch.
--
Philip
RE: [PATCH] delta_files() speedup 2/3: keyword substitution
Posted by Bert Huijben <be...@qqmail.nl>.
> -----Original Message-----
> From: Philip Martin [mailto:philip.martin@wandisco.com]
> Sent: maandag 29 maart 2010 18:20
> To: Julian Foad
> Cc: Stefan Fuhrmann; dev@subversion.apache.org
> Subject: Re: [PATCH] delta_files() speedup 2/3: keyword substitution
>
> Julian Foad <ju...@wandisco.com> writes:
>
> >> * subversion/libsvn_subr/subst.c
> >> (translation_baton): the 'interesting' member is now
> >> a boolean array.
> >> (create_translation_baton): adapt initialization code
> >> (translate_chunk): eliminate call to strchr
> >>
> >> patch by stefanfuhrmann < at > alice-dsl.de
> >> ]]]
> >
> > This patch looks lovely, from the point of view of a read-through
> > review.
>
> Agreed.
>
> To get rid of the initialization we could use 4 static constant arrays
> (we could even partially overlap them to save memory), but that's
> probably not a significant improvement.
I'm not sure how all this compares to just three byte compares, but with a
only a few kb first level cache in most current x86 processors it might be
even more optimal to just do the comparison in code.
But I think any solution that avoids calling the locale dependent strchr()
function will help here and the details between the table and in-code
variants are probably not measurable.
Bert
Re: [PATCH] delta_files() speedup 2/3: keyword substitution
Posted by Philip Martin <ph...@wandisco.com>.
Julian Foad <ju...@wandisco.com> writes:
>> * subversion/libsvn_subr/subst.c
>> (translation_baton): the 'interesting' member is now
>> a boolean array.
>> (create_translation_baton): adapt initialization code
>> (translate_chunk): eliminate call to strchr
>>
>> patch by stefanfuhrmann < at > alice-dsl.de
>> ]]]
>
> This patch looks lovely, from the point of view of a read-through
> review.
Agreed.
To get rid of the initialization we could use 4 static constant arrays
(we could even partially overlap them to save memory), but that's
probably not a significant improvement.
--
Philip
Re: [PATCH] delta_files() speedup 2/3: keyword substitution
Posted by Julian Foad <ju...@wandisco.com>.
On Sun, 2010-03-28, Stefan Fuhrmann wrote:
> Hi devs,
>
> this is part of the delta_files() speedup patch series:
> http://svn.haxx.se/dev/archive-2010-03/0604.shtml
>
> translate_chunk spends most of its time in a loop
> looking for the next '$' or newline. The call to strchr
> is excessively expensive since the 'interesting' string
> is no longer than 3 chars.
>
> It is much more efficient to use a simple lookup table
> (boolean array) that tells us whether a certain char
> is 'interesting' or not. Since we call it for almost every
> char in the file, the initialization overhead amortizes
> within the first two lines of the respective file.
>
> Performance gain is ~9%:
>
> s~$ time ~/1.7-928181/svn export --ignore-externals -q $REPO/trunk /dev/shm/t
> real 0m3.727s
> user 0m3.189s
> sys 0m0.542s
>
> ~$ time ~/1.7-patched/svn export --ignore-externals -q $REPO/trunk /dev/shm/t
> real 0m3.410s
> user 0m2.872s
> sys 0m0.537s
>
> -- Stefan^2.
>
> [[[
> Optimize the search for 'interesting' characters that
> control the keyword substitution. For details see
> http:// ...
>
> * subversion/libsvn_subr/subst.c
> (translation_baton): the 'interesting' member is now
> a boolean array.
> (create_translation_baton): adapt initialization code
> (translate_chunk): eliminate call to strchr
>
> patch by stefanfuhrmann < at > alice-dsl.de
> ]]]
This patch looks lovely, from the point of view of a read-through
review.
- Julian