Hacker News Reader

Comment by eru | Hacker News Reader

> C's null byte terminator imposes a fixed and essentially minimal size penalty regardless of the length of the string.

From an information theoretic point of view, making 1 out of 256 values of each byte unusable as the content of the string, is an overhead linear in the size of the string, not constant.

View on HN

It's even worse than that (from a practical standpoint, not a complexity theory standpoint) when you get into the realm of interpreted languages written in C. Try processing text containing null bytes in bash, for example.

Data containing null bytes is not text.

I like to think of bash / sh as just a job control system. It enables you to setup process pipelines. Everything is just processes and files (streams). Variables only serve as programs arguments. Since program arguments are also null terminated, variables containing null bytes just make no sense.

(Of course it gets dirty as soon as you feed the output of a job into a variable, for example. I think that isn't even defined by POSIX for non-text streams).

Feeding the output of a job into a variable is a common enough task. One example I worked on recently was to use the results of one find(1) command as an array of arguments to another. Perhaps this was a very ugly way of comparing two directories, but it worked.

This is why it surprised me when I realized (without having thought about it) that variables can't contain null bytes. It made my quick id3 tag parsing script a bit trickier to write, since I could no longer just use read(1P).

Null is one of many non-printing ascii and utf characters. Its existence predates its use as a string terminator. The overhead of having its own code point is totally independent of its use in C strings.

Yes, it already exists and has other uses. So when your code wants to use it, yet your language is reserving it, the overhead balloons tremendously.

Good point. We lose linearly one bit per ~177 characters that way. So zero termination does have linear cost.

1/(log2(256)-log2(255))

Assuming 8-bit char, at 1417 chars, zero terminated string overhead is 2 chars.

But you start with a constant cost of 8 bits.

For 255 characters you lose 9.4 bits which is bigger than the cost of an 8 bit size field.

For 65535 characters you lose 378 bits which is much bigger than the cost of a 16 bit size field.

On the other hand you have only one string type for arbitrarily sized strings and most strings are short.

What would really be needed to be more space efficient for short and long strings is a size field with a variable length encoding. E.g. 1 byte for string lengths up to 64, 2 bytes for string lengths up to 8k, etc.

> What would really be needed to be more space efficient for short and long strings is a size field with a variable length encoding. E.g. 1 byte for string lengths up to 64, 2 bytes for string lengths up to 8k, etc.

It's just decoding that requires pipeline busting branches. Well, I guess it's fine if you take branch mispredict for the large string case.

Maybe 1 byte with highest bit zero, 0-127, 2 bytes for 128-32767, etc?

The irony is of course now we have variable length encoding for the string size...

I think just using size_t instead makes more sense than saving a byte or two per string. Memory is cheap, but CPUs aren't getting much faster.

When size is an issue and nothing else prevents it either, just LZ4 (or similar memcpy order of magnitude speed compression) the string.

I think it depends on the use case. In embedded systems bits consume energy and therefore increase cost. The battery of a satellite is much more expensive than a Chinese coal power plant.

Yes, "size_t" should be just about right for everybody except the guys who _need_ to program in C/C++ and Assembler due to the hard requirements of their systems. Not very many people but very important systems.

If you want to go variable-width, probably best to keep it as simple as possible. 0-254 signal a short string, 255 signals that a size_t (or similar) follows. That way the overhead is never high, and you can handle the two formats with a very small number of instructions.

You'll have these duplicated compiler-inlined checks all over your binaries now, so your memory requirements might actually be higher. Start of your string data is now (almost) always unaligned, some penalty might apply. You'll potentially get pathological mispredicted branches when the string is being accessed.

That's not what he is saying. He is saying that there is an overhead in term of string length.

Example: a string with 0 character has a length of 1 (it contains NULL), a 100% overhead. A string with 1 character has a length of 2, a 50% overhead. It gets better with larger strings.

I am saying the same thing.

Strings that can't make use of 0 have to be a small constant factor longer to store the same entropy, because each byte can only store log_2 (255) ~ 7.994 bits, instead of log_2 (256) = 8 bits.

Of course, if you are storing printable ascii characters only, that doesn't matter, since you are using far less than 256 possibilities per byte, and so don't care that some of them unused onces are used for in-band signalling (https://en.wikipedia.org/wiki/In-band_signaling).

As vardump points out in another comment, that's equivalent to 1 in 177 bytes.

Reply on news.ycombinator.com