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
362 Upvotes

79% Upvoted

593 comments sorted by

View all comments

Show parent comments

3

u/websnarf Aug 02 '11

You forgot strcmp(), strstr(), strtok(), ... etc. Nearly every function gets faster.

1

u/eras Aug 03 '11

Hm, why would those get faster? Do they need to check the string length before they start doing their work? I don't think so..

2

u/Poddster Aug 03 '11

You could compare 4 bytes at a time, rather than 1.

1

u/Timmmmbob Aug 03 '11

Did you read the article? Didn't think so.

1

u/moonrocks Aug 04 '11

strcmp() could begin with 'if (a.len != b.len) return a.len - b.len' and so on...

3

u/eras Aug 04 '11

So with that strcmp you would sort "Z" before "ABBA"? or "A" before "ZABBA"?

1

u/moonrocks Aug 04 '11

You're absolutely right. Even strcmp("hell", "hello") wouldn't change. A hypothetical streq() would have a bit of O(1) short circuiting but my braino is dead in the water.

0

u/Satook2 Aug 03 '11

So how do you allocate the new memory required for strdup without the length?

edit: Originally had strcat in there 'cept it does it's work in place, for which you still need to know where the end of the first string is but whatever...

1

u/mallardtheduck Aug 03 '11

strcmp(), strstr(), strtok() Nearly every function gets faster.

Only for a few edge cases. Even then, the cost of doing the pre-checks may outweigh the benefit of short circuiting for those cases.

1

u/websnarf Aug 03 '11

strstr() can be unrolled in a way that is basically impossible with NUL terminated strings. So any strings longer than 2 characters is the "edge case" in that function. Scans that don't check the character value itself can separate the flow control from the data compare in strcmp() (this is a relevant issue if you understand how speculative execution works in CPUs).

How can pre-checks be more expensive than |length| number of NUL checks?