Hacker News Reader

Comment by tlrobinson | Hacker News Reader

You could use a variable-width size field similar to how UTF-8 works, but that's getting pretty complicated and inefficient.

e.x.

0xxx xxxx

10xx xxxx xxxx xxxx

110x xxxx xxxx xxxx xxxx xxxx

1110 xxxx xxxx xxxx xxxx xxxx xxxx xxxx

etc

View on HN

And re-introduces the 'magic character' you're trying to eliminate.

The magic character is in a known location, there's no need to iteratively scan for it.

The use of "magic" characters is not the problem, as I see it.

No it's not. In the first line, it's in [0], in the second line, it's in [1], in the third line, it's in [2]. You have to scan through to find where the '0' appears

True, but it's O(log N) rather than O(N) to determine length.

BTW I'm not sure if it was clear or not but those are bits in my diagram, not bytes/characters. The "x"s are the bits of the length field, not the characters of the string.

But you could just as easily set aside the first 4 bytes of a string to be the length and then it would be O(1).

But does that really matter when you're doing operations on the string that iterate over the whole string anyway? Since iterating the whole string is O(n) anyway, you're not really gaining anything.

Operations to return string length or return characters from the end of the string become far less expensive.

You also have a fair idea of a reasonable sized buffer to move in duplication operations, avoiding single character move loops.

Interestingly it was also Ken Thomson who invented UTF-8 as well.

If we could send one message back in time to Ken, Dennis, and Brian, I nominate this.

Reply on news.ycombinator.com