Re: While we're at it

On Thu, 1 Apr 2010, Colm MacCárthaigh wrote:

> 2010/4/1 Dean Anderson <[email protected]>:
> > Clue: How many bytes fit in a word?  The start of the array is probably
> > word-aligned.  A really good compiler might even figure out that it can
> > load the word in a register and test all at once.
> 
> Sadly, not. As I said in my reply, I can find no evidence of this in
> my analysis of machine code. Note that alignment is a tricky problem,
> it would have to scroll until the tests were word-aligned. See method
> 4 in the cited post;
> 
> 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.

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.

If I get some time, I'll count the instruction cycles on a couple
processors for your example.

		--Dean


-- 
Av8 Internet   Prepared to pay a premium for better service?
www.av8.net         faster, more reliable, better service
617 256 5494