Re: While we're at it

2010/4/5 Dean Anderson <[email protected]>:
>> http://www.stdlib.net/~colmmacc/2009/03/01/optimising-strlen/
>
> Your analysis of method 3 is incorrect:
>
>> Now we.re into serious unreadability territory, and by the way, the
>> above is how djb implements strlen. But we have actually gained some
>> efficiency, now for every jump operation that the loop creates, we
>> test for the 0 value 4 times. The choice of 4 times is arbitrary here,
>> but an interesting exercise would be to vary this number and test each
>> possibility.
>
> The unreadability of this is questionable.  But importantly, you also
> omit the effect of pipelining comparisons and the fact that the whole
> word will probably be in L2 cache, making it a lot faster to access.

The very next paragraph explicitly mentions pipelining, so I don't
agree with you that it has been omitted. I certainly don't call out
that the L2 cache would contain the whole word, but this seems like an
odd thing to call out. A register would contain the whole word, never
mind any of the caches. The L1 and L2 caches are both several orders
of magnitude larger than a word.

Loop-unrolling is a very separate thing from caching optimisation, and
is usually in opposition to it. Note that unrolled instructions
require storage too, and so compete for cache line space.

> Show me a memory allocator that gives back unaligned memory, and I'll
> show you how to fix that. Most of the time, we can be expect the memory
> to be word-aligned. In the rare case it isn't, it won't matter too much.

The issue is not that an allocator may return unaligned memory, but
that you may wish to count the length of a string that does not start
at the alignment boundary. For one trivial, but realistic, example;

char * string = "Hello World"; // probably a word-aligned pointer
int firstwordlength = strlen(string) - strlen(strtok(string, " "));
// second call is unaligned

-- 
Colm