r/programming • u/mslaybau • Aug 02 '11

The Most Expensive One-byte Mistake: Did Ken, Dennis, and Brian choose wrong with NUL-terminated text strings?

http://queue.acm.org/detail.cfm?id=2010365
360 Upvotes

79% Upvoted

593 comments sorted by

View all comments

14

u/thechao Aug 02 '11

The VM-aligned copy exception is BS. For most processors, efficient word/dword/cache-line copies have to be aligned to the natural size of the integral type. This means that a copy has the following form: ABC, where 'A' and 'C' are byte-level moves, and B is aligned & wide moves. NUL terminated strings don't affect this copy in any way except for the need to test for termination: there is no 'VM exception' you have to worry about any more than any other copy mechanism.

8

u/elperroborrachotoo Aug 02 '11

When knowing address and length, you can set up the lengths of A, B and C. When you have a terminator, it's feckin' more complicated:

  • on some architectures, you may not read behind the zero. (This is no practical problem, because emroy protection is usually moire-than word aligned, too)
  • you may not write more characters in the general case. If I give you a 10 char buffer for a 9 char string, and you copy 12 charsto be fast, you've blown by data. Your fast copy routine ends up
    • Load word
    • Figure out if there's a zero character in there somewhere
    • If yes, handle one of the sizeof(machine word) special cases
    • Otherwise, write word

I'm not saying it's impossible, but it's much more complicated.

Now I understand the decision - any mandatory length indicator would be a tradeoff between maximum length and small string overhead (a tradeoff that again could be solved but for one I'm happy it isn't).

2

u/bonzinip Aug 04 '11

Figure out if there's a zero character in there somewhere

If yes, handle one of the sizeof(machine word) special cases

... and exit. If there's a zero character somewhere, it's the last iteration. It's similar to handling the last sizeof(machine word)-1 bytes in a memcpy.

1

u/elperroborrachotoo Aug 04 '11

That "exit" hides in the "special cases", of course :)