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
Attachment:
pgpI9eZPa2n8r.pgp
Description: PGP signature