Re: While we're at it

2010/4/7 Dean Anderson <[email protected]>:
> On Mon, 5 Apr 2010, Colm MacCárthaigh wrote:
(snip)
> But a complete word is brought into L2 cache to read one byte. When
> aligned the next 3 tests access L2 cache at high speed and are
> pipelined.  A conditional jump to do one test at a time would slow it
> down because the pipeline is flushed when the branch is taken.

L1 cache not L2 - and the pipeline should only be flushed if the branch
is mispredicted. Any half-decent branch prediction should know the
conditional branch back to check the next byte (JNZ in x86-speak) is
taken most of the time, so the misprediction will only occur when
breaking out of the loop to return the result.

On the original SPARC and MIPS static branch predictors, the first
three lines of DJB's unrolled routine will be "predicted" correctly for
the common case of a non-zero byte; only the loop back to the
beginning will be mis-predicted. The later refinement, assuming
that only backward branches are taken, will be correct for all except
the final byte.

>> > 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
>
> Sure. But one wants code that is fast in the most common case, and works
> in the less common case.

When parsing HTTP requests or DNS packets, I would expect nearly 75% of
the initial data to be non-word-aligned (87.5% on machines with 64 bit words).
With tinydns, the static data.cdb content already contains the length of each
object, so there shouldn't be any strlen-type calls there either.

With the simple byte by byte comparison, it doesn't really matter. I would
not be at all surprised to find the extra overhead in the "clever" word
by word version made it slower than the unrolled and branch-predicted
byte approach.

Of course, experimenting would be good - I'll see if I can find time to
round up some actual figures, at least on x86 (-64) in the next few
days. I would expect DJB did some profiling back when he first wrote
that code and that's how he ended up with the 4 line unroll; I
seem to recall he tended to check timing on SPARC and MIPS as well.
-- 
James A Sutherland
mobile +44 7977 563483; Skype jas88cam