More than you necessarily wanted to know about tor_strndup performance improvements from late-2004 [was Re: tor callgrinds]

[Nick Mathewson]

On Fri, Feb 16, 2007 at 10:12:20PM -0500, Watson Ladd wrote:
 [...]
> 2: Won't strlcpy run in time proportional to n? strncpy can't be much
> faster as both functions need to loop from 0..n, load the character and
> check if its null, and then copy it. The big difference is strncpy keeps
> on going.

You're confused about how strlcpy works when n is much smaller than
the length of the source string.  Look at the return value of strlcpy:
it's the length of the original string.  To find the length of the
original string, strlcpy basically has to walk over the whole thing.
So while the running time of strncpy(dst,src,siz) is O(siz),
strlcpy(dst,src,siz) is O(strlen(src)).  That's a big problem for
tor_strndup: its most performance-relevant use case is copying a small
portion of a much longer string, as when we're parsing router
descriptors.  In this use case, strncpy is obviously better.

This isn't one of those hypothetical armchair optimizations, by the
way: we profiled Tor before and after, and found out that the time
spent copying strings went way down after we made the change.  (I'm
afraid I don't still have the numbers; this change came in the
0.0.9pre6 develoment, was back in November of 2004.)

My apologies to everybody who already knows this stuff for wasting
your time.

brought to you by the letter "C", and by the number "3" (which is good
   for anonymity),
-- 
Nick Mathewson
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 652 bytes
Desc: not available
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20070217/226f648c/attachment.pgp>