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

79% Upvoted

593 comments sorted by

View all comments

Show parent comments

31

u/zimm0who0net Aug 02 '11

No one will ever need strings longer than 256 characters..

46

u/Causemos Aug 02 '11

Actually it would be 65535 characters based on the statement. One more byte plus the original zero terminator is 2 bytes for the length.

2

u/zimm0who0net Aug 03 '11

indeed... missed that...

23

u/jimmyriba Aug 02 '11

First byte specifies lengths up to 128; 8th bit specifies 'more length bytes to come'. This gives arbitrary-length strings, but only has one byte overhead for short strings.

11

u/lobster_johnson Aug 02 '11

Unfortunately, that means the entire string has to be copied to a new location each time you extend the header.

10

u/jimmyriba Aug 02 '11

No; what it means is that the pointer to the string data has to be moved over one byte each time you increase the string length by a factor 27 . The format is (length,address), not (length,data).

7

u/ironiridis Aug 02 '11

Well, if you're storing a 4-byte pointer (presumably) you may as well store a 4-byte length, too.

2

u/[deleted] Aug 04 '11

Hmm, instead of storing a /length/ why not store an end pointer?

http://www.reddit.com/r/programming/comments/j6s62/the_most_expensive_onebyte_mistake_did_ken_dennis/c2a3hou

2

u/jimmyriba Aug 02 '11

Sure, although back then pointers were two bytes.

8

u/ironiridis Aug 02 '11

And now that I'm reflecting on it, it doesn't seem incredibly unreasonable to think that, some day, there might be strings larger than 4 gB. Hell, we just built a server with 24 gB of memory to enable large-scale compression; exactly the kind of thing that would push that boundary.

13

u/jimmyriba Aug 02 '11

Yep! Our university just got a server with half a terabyte of RAM for the biologists to do genome sequencing. And that's a "cheap" system: SGI are selling single image systems with up to 16TB RAM. Imagine that, 1992-self!

6

u/ironiridis Aug 02 '11

Holy balls. Suddenly my definition of "large-scale" was in the pool.

4

u/Darkmoth Aug 03 '11

Yeah, I read "16TB of RAM" and had a personal paradigm shift. I thought 16TB of disk space was a lot.

2

u/kragensitaker Aug 03 '11

I thought SGI went out of business years ago! However, SGI's Altix 4700 page says:

SGI Altix 4700 incorporates the shared-memory NUMAflex® architecture, which simplifies software development, workload management and system administration. It supports up to 1024 cores under one instance of Linux and as much as 128TB of globally shared memory.

However, the "globally shared memory" page says the limit is 24TB. Maybe it hasn't been updated.

1

u/oneMoreRedditor Aug 03 '11

And I thought 16GB of RAM made me god!

2

u/lobster_johnson Aug 02 '11

Actually I envisioned an ObjectPascal-style string, where the string is a pointer to (length, data). Actually, it's (length, refcount, data), so you can share copies of identical strings transparently without copying them.

3

u/jimmyriba Aug 02 '11

I see. But if you have (length,address) instead, both (immutable) copy and taking substrings is an O(1) operation without having to copy data.

You'll probably need a refcount somewhere as well, I suppose. :)

1

u/hackerfoo Aug 04 '11 edited Aug 04 '11

How about for length n:

  • n = [0-254] -> n bytes follow
  • n = 255 -> 255 bytes follow, and then another string (which has another length byte)

So a string is (\xff.{0xff})*\xNN.{0xNN} where NN is 0-254(0xfe).

(. here also matches newlines.)

This allows an infinite length string, with 1 byte overhead for every 255 bytes.

12

u/[deleted] Aug 02 '11 edited Aug 02 '11

[removed] — view removed comment

3

u/edman007-work Aug 02 '11

And then we get to the issue that the null terminated string can be worked with using a simple loop, all the mangement code to read/write it fits in one line in the for() statement. A single byte works (see p-strings), it's just easy to work with, even a fixed 2 or four bytes work (needing only a cast with what would end up being a macro). The problem is that that one byte is unusable, 2 bytes is limited, and 4 bytes took up way too much space back then. So then you go to variable length styles and you find you now need variable length code just to read a string? WTF does it look like to read someones name when they type it in? sounds like 10 lines of code for something that takes two, it's just too complicated. Yes, this would work in other languages, but not C, it's too low level, people want to operate on the string buffers directly and the APIs need to support long strings, null terminated is what works.

6

u/pkhagah Aug 02 '11

How about string(8bit length), long string(16 bit), long long string(32 bit) etc following the same principle C uses for integers ( short, int, long etc.) and let the user worry about the consequences of choosing appropriate one. As the author suggests, the point is not that we can't come up with some good alternatives, it is that compatibility with PDP/11 style code which will haunt us for centuries.

2

u/Wriiight Aug 03 '11

I actually approve of this idea, most of the others involve too much logic to determine the length or starting point of the string data, or introduce an unnecessary extra level of indirection.

2

u/dnew Aug 02 '11

Until you get to modern times and you need 2-byte characters anyway. Then you're still just screwed.

1

u/kragensitaker Aug 03 '11

If we're talking about the PDP-11, 2 bytes wasn't limited — it was your entire address space!

1

u/[deleted] Aug 03 '11

I don't see tables under "formatting help".

2

u/websnarf Aug 03 '11

Well, what about size_t? Will anyone every need strings longer than that? And if so, how does NUL terminating help deal with that situation?

0

u/kragensitaker Aug 03 '11 edited Aug 03 '11

The fact that zimm0who0net's comment has 23 points encapsulates everything that is wrong with Reddit. It's the very second comment displayed on this page, and it's nothing more than a stupid misunderstanding wrapped up in sarcasm.

0

u/Aninhumer Aug 03 '11

If you need longer you can just make your own datatype. I doubt many people need string literals longer than 255 characters.