Performance improvement to strnlen().

[Lee Thomas]

Hello FreeBSD devs,

I have found a performance improvement to libc's strnlen(). 
lib/libc/string/strnlen.c is a trivial byte-by-byte implementation, 
where strlen.c has a smarter word-by-word implementation. I have 
implemented strnlen similarly to strlen. It runs about 4x as fast, at 
the cost of a binary codesize increase from 30 bytes to 221.

In writing this I needed a test, and there isn't one in 
tools/regression/lib/libc/string, so I wrote a unit test for strnlen. 
This really only makes sense for a word-by-word implementation, as it 
tests each combination of string and limit length, overread characters, 
and starting alignment.

Could someone please review these patches? I am not very experienced in 
C, and am even less experienced with FreeBSD's style guidelines, so they 
likely have a bunch of style and idiom issues. Even if one or both of 
them prove not worth committing, it would still be useful for my 
learning.

If/When these patches prove worthy of submitting, what is the next step 
after that? Should I submit a PR, or is there some other process? This 
code is quite similar to the existing strlen.c, and doesn't do anything 
fancy with e.g. endianness, but I haven't tested it for correctness or 
performance on anything other than x86...

And finally, there is some other low-hanging fruit in the other strn* 
functions. Would it be worth it for me to give those the same treatment?

Thanks,
Lee Thomas

Test platform:
	$uname -a
		FreeBSD LeeDesktop 9.1-STABLE FreeBSD 9.1-STABLE #15 r250831: Mon May 
20 17:31:28 EDT 2013
			lthomas at LeeDesktop:/usr/obj/usr/src/sys/NOSOUND  amd64
	$dmesg | grep CPU:
		CPU: Intel(R) Xeon(R) CPU           X5650  @ 2.67GHz (2666.81-MHz 
K8-class CPU)
	$clang --version
		FreeBSD clang version 3.2 (tags/RELEASE_32/final 170710) 20121221
		Target: x86_64-unknown-freebsd9.1
		Thread model: posix

My timing test was a file of 10000 strings, of uniformly random length, 
50% between 0 and 20 bytes long, and 50% between 21 and 1000 bytes long. 
Each was filled with random generated bytes in the range [1, 255]. The 
test executables run their strlen on each string in the file 1000 times, 
and a shell script ran the test programs alternately 100 times. Here are 
the clang results; gcc results are roughly the same. I will share the 
actual timing code if someone wants it, but it is pretty ugly C++ and 
shell and I don't guarantee it working :-).

Results:

x ./times_bsd_strnlen.txt
+ ./times_my_strnlen.txt
+--------------------------------------------------------------------------+
|+                                                                      
  x|
|+                                                                      
  x|
|+                                                                      
  x|
|+                                                                      
  x|
|+                                                                      
  x|
|+                                                                      
  x|
|+                                                                      
  x|
|+                                                                      
  x|
|+                                                                      
  x|
|+                                                                      
  x|
|+                                                                      
  x|
|+                                                                      
  x|
|+                                                                      
  x|
|+                                                                      
  x|
|+                                                                      
  x|
|+                                                                      
  x|
|+                                                                      
  x|
|A                                                                      
  A|
+--------------------------------------------------------------------------+
     N           Min           Max        Median           Avg        
Stddev
x 101     1.8685486     1.8693889     1.8687506     1.8687894  
0.0001484903
+ 101    0.42704683    0.42779486    0.42712813    0.42715597 
0.00010681494
Difference at 95.0% confidence
	-1.44163 +/- 3.56739e-05
	-77.1426% +/- 0.00190893%
	(Student's t, pooled s = 0.000129342)

Note: I manually shortened the histogram, as it was 100 lines long of 
exactly the same.
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: strnlen.diff
URL: <http://lists.freebsd.org/pipermail/freebsd-hackers/attachments/20130525/a8e3fc6d/attachment.ksh>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: test-strnlen.diff
URL: <http://lists.freebsd.org/pipermail/freebsd-hackers/attachments/20130525/a8e3fc6d/attachment-0001.ksh>