[svn.haxx.se] · SVN Dev · SVN Users · SVN Org · TSVN Dev · TSVN Users · Subclipse Dev · Subclipse Users · this month's index

Re: [PATCH] strlen() optimizations (1)

From: David Mankin <mankin_at_ants.com>
Date: 2002-12-06 18:20:28 CET

On Thursday, December 5, 2002, at 07:33 PM, Branko ╚ibej wrote:
>> +/* Returns 1 if A is longer than B, -1 if B is longer than A, and
>> + * 0 if A and B are the same length.
>> + *
>> + * This is better than using (strlen(a) > strlen(b)) because only
>> + * O(min(len(a), len(b))) chars are examined instead of O(len(a) +
>> len(b))
>> + */
>> +int svn_cstring_strlencmp (const char* a,
>> + const char* b);
> It's a common misconception that hand-coded functions will be faster
> than what the compiler provides. Modern compilers will generate highly
> optimized inline code for string functions that uses word-length
> instructions where possible. So it's entirely possible, expecially
> taking function call overhead into account, that your functions are
> actually slower than what was being used now. You should _always_
> measure the effects of your "optimizations", even though they might
> seem oviously correct to you.

Well, thanks to Brane's comments I did some benchmarks on my strlencmp
method. I don't have svn setup so I can get realistic measurements of
the function in real life, so I tested it in isolation. I can post
more details if anyone is really interested, but here is the summary:

If min(len(a), len(b)) <= 6, my strlencmp() is always faster (by up to
150%). If min(len(a), len(b)) >= 17, two calls to strlen() is always
faster (by up to 100%). 11-12 seems to be the time when either one is
about as likely to be faster as slower. (This is on my Powerbook
G4/667MHz, Mac OS X 10.2.2, gcc -O2 version 3.1.)

I could put checks in strlencmp to call strlen() once it crosses the
short-string threshold, but since I don't know how real data fits into
these length requirements, I don't know how they change on different
architectures/compilers/C libraries, and I doubt that a even 150%
speedup in the few places where we're checking to see which string is
longer will make any noticeable difference, I withdraw my patch to add

I'll fix my other problem (thanks to Brane & C-Mike for pointing out
the problem and to C-Mike for a suggestion for repair) and resubmit.

>> Index: subversion/libsvn_ra_dav/fetch.c
>> ===================================================================
>> --- subversion/libsvn_ra_dav/fetch.c (revision 3951)
>> +++ subversion/libsvn_ra_dav/fetch.c (working copy)
>> @@ -1224,7 +1224,7 @@
>> }
>> }
>> - if (strlen(url) > strlen(bc_root))
>> + if (svn_cstring_strlencmp(url, bc_root) > 0)
>> {
>> const char *comp;
>> comp = svn_path_uri_decode(svn_path_basename(url, subpool),
> See above. -1 on committing things like this until you can prove that
> your change actually makes a measurable difference -- for the better.
> --
> Brane ╚ibej <brane_at_xbc.nu> http://www.xbc.nu/brane/

-David Mankin

To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Received on Fri Dec 6 18:22:02 2002

This is an archived mail posted to the Subversion Dev mailing list.