>        strstr_imp2     90.57
>        strstr_fun2     89.64
>        C strstr        53.76

Is that C the simple C one I posted, or the libc one on sparc?

Here are my timings with yours added:

strstr_fun total = 1.135000 (5,0,19,13)
strstr_fun2 total = 1.470000 (5,0,19,13)
strstr_imp total = 1.030000 (5,0,19,13)
strstr_imp2 total = 0.965000 (5,0,19,13)
strstr_c total = 0.790000 (5,0,19,13)
strstr_libc total = 0.370000 (5,0,19,13)

Your new strstr is actually slower on x86 than your first one, but I haven't looked into why yet.  It may also be data (since my data is obviously lame garbage).  I should try Alpha Linux...

Chris