6 ms·

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 cos

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.

lelanthran 3mo ago
> 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: 0XXX XXXX -> length of string is in those 7 bits 1XXX XXXX XXXX XXXX -> length of string is in those 7+8 bits 11XX XXXX XXXX XXXX XXXX XXXX-> length of string is in those 6+8+8 bits ... > 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.
- rswail 3mo ago
  So what exactly is the NUL/0 in the code below other than a sentinel value? while (*d++ = *s++) ;
  - lelanthran 3mo ago
    I am not sure what this is in response to. Can you explain which point of mine you are responding to?
    - rswail 3mo ago
      > If the hardware had instructions for sentinel values, things would be easier (Like how DOS calls used '$' termination for strings) and safer. A zero is a sentinel value and is catered to by all ISAs. Why would using a "$" be any easier/safer than a NUL?
      - lelanthran 3mo ago
        > A zero is a sentinel value and is catered to by all ISAs. > Why would using a "$" be any easier/safer than a NUL? I didn't say it had to be '$'; I specifically said that the sentinel would be loaded into a register. In that case it could be anything, including zero (for the snippet you posted), or INT_MAX if the code iterated across an array of integers, etc. By having rep/mov variants that use sentinels, a lot of the HLL problems go away - Java, C#, Python, etc would all look very different today if the ISAs from the 80s included sentinal variant of memory instructions.
        rswail 3mo ago
        Except that nearly all ISAs treat zero as a special value, with a Z-flag or equivalent for the last ALU result, and conditional branches around that result. PDP-11s, 68Ks, nearly all ISAs that I know about treat zero as special. It falls naturally out of the ALU operations. So why would people writing assembler code use another value unless they had to?
        lelanthran 3mo ago
        That's my point - they didn't, and used the zero as a sentinel when designing their HLL. If, OTOH, the ISA had additional variants of those instructions that allowed usage of anything as a sentinel, HLL implementations of array would never have needed a fat pointer (length + memory).
- cornholio 3mo ago
  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).
Parodper 3mo ago
You could do 0xffff as a special case, and put another length+string/pointer to after the 255th byte.

lelanthran 3mo ago

> 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: 0XXX XXXX -> length of string is in those 7 bits 1XXX XXXX XXXX XXXX -> length of string is in those 7+8 bits 11XX XXXX XXXX XXXX XXXX XXXX-> length of string is in those 6+8+8 bits ... > 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.

rswail 3mo ago
So what exactly is the NUL/0 in the code below other than a sentinel value? while (*d++ = *s++) ;
- lelanthran 3mo ago
  I am not sure what this is in response to. Can you explain which point of mine you are responding to?
  - rswail 3mo ago
    > If the hardware had instructions for sentinel values, things would be easier (Like how DOS calls used '$' termination for strings) and safer. A zero is a sentinel value and is catered to by all ISAs. Why would using a "$" be any easier/safer than a NUL?
    - lelanthran 3mo ago
      > A zero is a sentinel value and is catered to by all ISAs. > Why would using a "$" be any easier/safer than a NUL? I didn't say it had to be '$'; I specifically said that the sentinel would be loaded into a register. In that case it could be anything, including zero (for the snippet you posted), or INT_MAX if the code iterated across an array of integers, etc. By having rep/mov variants that use sentinels, a lot of the HLL problems go away - Java, C#, Python, etc would all look very different today if the ISAs from the 80s included sentinal variant of memory instructions.
      - rswail 3mo ago
        Except that nearly all ISAs treat zero as a special value, with a Z-flag or equivalent for the last ALU result, and conditional branches around that result. PDP-11s, 68Ks, nearly all ISAs that I know about treat zero as special. It falls naturally out of the ALU operations. So why would people writing assembler code use another value unless they had to?
        lelanthran 3mo ago
        That's my point - they didn't, and used the zero as a sentinel when designing their HLL. If, OTOH, the ISA had additional variants of those instructions that allowed usage of anything as a sentinel, HLL implementations of array would never have needed a fat pointer (length + memory).
cornholio 3mo ago
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).

Parodper 3mo ago

You could do 0xffff as a special case, and put another length+string/pointer to after the 255th byte.