lkml.org 
[lkml]   [1998]   [Apr]   [26]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
SubjectRe: faster strcpy()
Date
From: Alexander Kjeldaas <astor@guardian.no>
> On Sun, Apr 26, 1998 at 05:17:46PM +0200, Pavel Machek wrote:
> > Hi!
> >
> > > > I'm not sure why Mycroft used '& ~(w)' in the above. Unless something
> > > > obvious escapes me, you can optimize the above down to 3
> > > > instructions. Both codepaths have a dependency chain of 3
> > > > instructions.
> > > >
> > > > #define word_has_nullbyte(w) ((((w) - 0x01010101) ^ (w)) & 0x80808080)
> > > >
> > >
> > > Hmm.. two things obviously escaped me:
> > >
> > > 1) The above fails horribly and detects 0x80 as a null.
> >
> > It does not matter too much: you usually want
> >
> > word_has_probably_nullbyte(), since you usually want to know where the
> > nullbyte is and copy rest byte-by-byte.
> >
>
> You're right. It occurred to me in my sleep :-)
>
> In addition to the above, word_has_probably_nullbyte should be coded as
>
> #define word_has_probably)nullbyte(w) (((w) - 0x01010101) ^ (w & 0x80808080))
>
> which is faster. And then you could have a slow find_null_byte loop
> which on a fake warning jumps back into the loop. [as a side note, you
> can't use the original word_has_nullbyte to find the byte that
> actually has a null byte since it will flag the high-order bit in the
> _two_ first bytes of 0x0100xxxx].
>
> Let's see: 2 loads, 2 subs, 2 ands, 2 xors, and 2 branches to move 8
> bytes, that's 1.25 instructions/byte. Not impressing.

On an x86, maybe. On an ARM, it's somewhat more impressive; it codes
down to:

4: ldr r3, [r0], #4
sub r14, r3, r4
bic r14, r14, r3
tst r14, r4, lsl #7
strne r3, [r1], #4
bne 4b

which is 6 instructions for the inner loop of a strcpy which copies 4 bytes
at a time - 1.5 instructions per byte.

Now, a strlen will take one instruction less in the inner loop, but then
a memcpy will shift 32 bytes per loop - and that inner loop will take
only 4 instructions. So for a n byte string, the first option takes
approx 3n/2 instructions, and the strlen+memcpy takes 5n/4 + n/8 = 11n/8.
A clear win of n/8 instructions. I'm ignoring end-effects, of course.

Where you really win on strlen+memcpy is if the strings have different
alignments. memcpy with unaligned blocks is quite hideous enough,
munging it to test for zero bytes is something that most programmers
simply can't be bothered to do.

> Once upon a time, I was interested in compilers (guess I still am) and
> it bothered me that languages often need null-terminated strings to be
> compatible with the "C"-world. So I came up with the idea that in my
> compiler, I would pad all strings to be a multiple of the word-size of
> the machine. Then I would use between 4 and 1 null-bytes to terminate
> the string. That way, I remained compatible with C, but in all the
> str* routines, I only have to check one byte to know if I had come to
> the end of the string. It doesn't use any more memory either unless
> you want to pack strings really tight, something you usually don't
> want to do to avoid alignment problems. Maybe something similar could
> be used in the Linux kernel on architectures with less-than-optimal
> support for null-terminated strings.

It may or may not bother you to know you weren't first. Sun's XDR/RPC
does exactly this. I can confirm it significantly speeds up string
operations ;-)
If people are worried about the additional 3 bytes of space required per
string, it's still a win on the ARM to only pad to even addresses.

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu

\
 
 \ /
  Last update: 2005-03-22 13:42    [W:0.955 / U:0.056 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site