Comment by msla
16 days ago
In addition to having to pick a size for the length counter and then, later, having to differentiate between lengths in bytes, codepoints, and glyphs, you can't subdivide a Pascal string using pointer arithmetic. To pass just the end of a string into a function, you have to either copy the tail of one Pascal-style string to another with a smaller size value, or your string has to be a struct with an integer and a pointer to the actual data instead of just an integer stuck on the beginning of the string. The first is a lot of copying in some cases, the second raises the specter of structs with invalid pointers. That's not to mention the potential problems that would cause with caches.
You can have a universal variable length field, for example 2 bytes for strings < 32768, then four bytes, 8 bytes etc. On the critical short string path, it costs just a single bit test. The glyph vs byte issues need to be dealt with in both formats.
The subdivision issue is a good perspective, but i would argue the performance impact of cloning substrings is dwarfed by the redundant full string reads to find length.
> You can have a universal variable length field, for example 2 bytes for strings < 32768, then four bytes, 8 bytes etc.
To hold the length of a string, I'd do something similar to unicode:
7-bits for size + 1-bit for continuation, then 15 bits for size + 1 bit for continuation, then 23-bits for size + 1 bit for continuation, etc.
Or maybe even do it exactly the same as unicode:
> On the critical short string path, it costs just a single bit test.
A few more clock cycles compared to NULL-termination, although my alternatives above require even more clock cycles.
If the hardware had instructions for sentinel values, things would be easier (Like how DOS calls used '$' termination for strings) and safer.
Load a sentinel byte into a register and have dedicated copy and compare instructions that take each two addresses (src and dst) and copies (or compares) src/dst until the terminator is reached (with copy copying the sentinel as well).
Considering that sentinel values are needed so often, and are so useful, it's surprising that this is not in any ISA. What we have now is kludgy workarounds in the HLL for this. It's hard to blame the HLL, because some workaround has to be implemented.
Personally, I would avoid UTF-8 levels of complexity because you only pay the size cost once per string. A simple 2-bytes + optional 4 bytes continuation scheme handles strings up to 140TB and increases the size of the average string by just 2 bytes (compared to 1 byte for nul termination).
So what exactly is the NUL/0 in the code below other than a sentinel value?
6 replies →
You could do 0xffff as a special case, and put another length+string/pointer to after the 255th byte.
The third option is to have a variable width length: the top most bit signals whether the next byte corresponds to the length or to the start of the string.
.. which is why you need a second type, the one dotnet calls "Span". A substring.