5 ms·

This is a rather weird article. Of course sentinels can be faster in some very particular algorithms. That's not the core contention. The core contention is tha

This is a rather weird article. Of course sentinels can be faster in some very particular algorithms. That's not the core contention. The core contention is that sentinels in general cause more speed losses than speed gains over the entirety of the application. Importantly, many useful algorithms such as string copying, string comparison, and string concatenation can be much more efficient using a size field.

colejohnson66 6y ago
I think this is something C++ (and other later ones) got right; A size field and a sentinel’d (null-terminated) char[]. So getting the length only requires reading 4 or 8 bytes, but if you want to pass that string to a function that expects a null terminated string, just pass x.c_str().
- twic 6y ago
  It would be even better if it was terminated by 8-len%8 null bytes, as that would make blocked loops simpler.
  - deleted 6y ago
    [deleted]
- throwaway894345 6y ago
  This seems useful if you're expecting to pass your strings to a lot of C libraries, which is probably sensible for C++ (especially whatever vintage of C++ happened to introduce this string design); however, surely this is a negligible concern for most mainstream languages?
  - pengaru 6y ago
    > This seems useful if you're expecting to pass your strings to a lot of C libraries, which is probably sensible for C++ (especially whatever vintage of C++ happened to introduce this string design); however, surely this is a negligible concern for most mainstream languages? No, the system call interface of the operating system expects NUL-terminated strings as parameters all over the place, especially the filesystem APIs.
    - steveklabnik 6y ago
      Who came first, the chicken or the egg? EDIT: Okay, this is at -1, maybe I shouldn't be slightly obtuse. These questions are, in my mind, two sides of the same coin. The OS expects null terminated strings, not for some inherent reason, but because C and UNIX grew up together. There's no inherent reason you can't have an OS that does not use sentinels to demarcate strings.
      - throwaway894345 6y ago
        Probably my fault for phrasing the question ambiguously, but the parent interpreted my question as I intended it to be interpreted. Interfacing with the system libraries is a common enough case for using null-terminated strings. I'm actually a little curious how what these low-level APIs look like and how "modern" languages handle efficiently converting to null-terminated strings. Do they just copy everything while C/C++/etc would pass a straight reference? Also, what do the underlying syscall APIs look like?
        steveklabnik 6y ago
        It's all good. You are 100% right that it's still a good use-case. And yeah, in Rust we have a separate CString type that's null terminated, so you may need a copy to move between the two worlds. It just depends, if you're only reading, for example, then you can create a pointer + len where the length doesn't include the 0, and that's effectively zero cost. You got me curious about my days as a kid putting "pascal" in front of Mac System 7 stuff; I believe that it only accepted Pascal strings. I also vaguely remember people doing funny stuff like null terminating pascal strings anyway and then putting the length before the actual pointer so that you get both in one...
        colejohnson66 6y ago
        Weren’t “Pascal strings” limited in that they were only a byte though? So, your string could only be 255 bytes long (conveniently going to a nice round 256 when you add the length byte).
  - colejohnson66 6y ago
    For most people, the time difference between reading 4/8 bytes and scanning for a null terminator is negligible, but there’s the other benefit of not having to worry as much about buffer overruns; If you append to a std::string and its internal buffer is full, it’ll realloc() its buffer. This does have the problem of the possibility of a realloc(), but I prefer that over buffer overruns.
- saagarjha 6y ago
  Note that C++11 got this right, this wasn't guaranteed prior to that.
throwaway894345 6y ago
I agree. The framing of the article could have been clearer that (start, length) data structures are widely better for the general case, but that null terminated strings can be faster for certain niche cases.
- klodolph 6y ago
  That is the framing of the article.
  - throwaway894345 6y ago
    I argued that the framing could have been clearer and you responded with "that is the framing". I don't think your response passes the type checker.
    - klodolph 6y ago
      The framing is obvious from the title of the article. It's a short article. Adding a bunch of context and framing would make the article worse. The problem is that when an article gets shared on HN, people hold it to unreasonable standards of clarity and correctness... the kind of standards that are usually only achieved with careful editing. It's appropriate to level that kind of criticism at a textbook or a Wikipedia article, but the feedback is unwelcome for simple blog posts like this. There's also a weird current of pedantry here, like "I understood the article, but someone else might misunderstand, and so the article should be clearer."
      - throwaway894345 6y ago
        > people hold it to unreasonable standards of clarity and correctness. I only said it would be better if it were clearer. I'm not arguing that it's unfit for HN or any other venue. You're reading much too far into this.
        klodolph 6y ago
dundarious 6y ago
See Alexandrescu’s Fastware talk on how amazingly sentinels can improve even textbook algorithms, and how to apply the approach intelligently. E.g., for a linear search, overwrite the last element with the sought after value, and do a tiny bit of work to make that safe and to undo it before return. If you’re skeptical, I really do encourage you to watch, he’s not sloppy. https://youtu.be/AxnotgLql0k https://youtu.be/AxnotgLql0k
- deleted 6y ago
  [deleted]
- bjoli 6y ago
  This brings back memories! I discovered the same thing in high school in a programming class. We had a speed-golfing assignment and in the end my program ended up quite a bit faster than the "golden reference" our teacher had. He refused to believe I had come up with it myself (though I got the highest grade on the assignment). This was back when we could assume 8-bit encodings(iso 8859-1 was the one we used). Simpler times!
hinkley 6y ago
Is that even the core contention? Or is the core contention that within mutable data it's possible to destroy the sentinel through bugs or malice?

colejohnson66 6y ago

I think this is something C++ (and other later ones) got right; A size field and a sentinel’d (null-terminated) char[]. So getting the length only requires reading 4 or 8 bytes, but if you want to pass that string to a function that expects a null terminated string, just pass x.c_str().

twic 6y ago
It would be even better if it was terminated by 8-len%8 null bytes, as that would make blocked loops simpler.
- deleted 6y ago
  [deleted]
throwaway894345 6y ago
This seems useful if you're expecting to pass your strings to a lot of C libraries, which is probably sensible for C++ (especially whatever vintage of C++ happened to introduce this string design); however, surely this is a negligible concern for most mainstream languages?
- pengaru 6y ago
  > This seems useful if you're expecting to pass your strings to a lot of C libraries, which is probably sensible for C++ (especially whatever vintage of C++ happened to introduce this string design); however, surely this is a negligible concern for most mainstream languages? No, the system call interface of the operating system expects NUL-terminated strings as parameters all over the place, especially the filesystem APIs.
  - steveklabnik 6y ago
    Who came first, the chicken or the egg? EDIT: Okay, this is at -1, maybe I shouldn't be slightly obtuse. These questions are, in my mind, two sides of the same coin. The OS expects null terminated strings, not for some inherent reason, but because C and UNIX grew up together. There's no inherent reason you can't have an OS that does not use sentinels to demarcate strings.
    - throwaway894345 6y ago
      Probably my fault for phrasing the question ambiguously, but the parent interpreted my question as I intended it to be interpreted. Interfacing with the system libraries is a common enough case for using null-terminated strings. I'm actually a little curious how what these low-level APIs look like and how "modern" languages handle efficiently converting to null-terminated strings. Do they just copy everything while C/C++/etc would pass a straight reference? Also, what do the underlying syscall APIs look like?
      - steveklabnik 6y ago
        It's all good. You are 100% right that it's still a good use-case. And yeah, in Rust we have a separate CString type that's null terminated, so you may need a copy to move between the two worlds. It just depends, if you're only reading, for example, then you can create a pointer + len where the length doesn't include the 0, and that's effectively zero cost. You got me curious about my days as a kid putting "pascal" in front of Mac System 7 stuff; I believe that it only accepted Pascal strings. I also vaguely remember people doing funny stuff like null terminating pascal strings anyway and then putting the length before the actual pointer so that you get both in one...
        colejohnson66 6y ago
        Weren’t “Pascal strings” limited in that they were only a byte though? So, your string could only be 255 bytes long (conveniently going to a nice round 256 when you add the length byte).
- colejohnson66 6y ago
  For most people, the time difference between reading 4/8 bytes and scanning for a null terminator is negligible, but there’s the other benefit of not having to worry as much about buffer overruns; If you append to a std::string and its internal buffer is full, it’ll realloc() its buffer. This does have the problem of the possibility of a realloc(), but I prefer that over buffer overruns.
saagarjha 6y ago
Note that C++11 got this right, this wasn't guaranteed prior to that.

throwaway894345 6y ago

I agree. The framing of the article could have been clearer that (start, length) data structures are widely better for the general case, but that null terminated strings can be faster for certain niche cases.

klodolph 6y ago
That is the framing of the article.
- throwaway894345 6y ago
  I argued that the framing could have been clearer and you responded with "that is the framing". I don't think your response passes the type checker.
  - klodolph 6y ago
    The framing is obvious from the title of the article. It's a short article. Adding a bunch of context and framing would make the article worse. The problem is that when an article gets shared on HN, people hold it to unreasonable standards of clarity and correctness... the kind of standards that are usually only achieved with careful editing. It's appropriate to level that kind of criticism at a textbook or a Wikipedia article, but the feedback is unwelcome for simple blog posts like this. There's also a weird current of pedantry here, like "I understood the article, but someone else might misunderstand, and so the article should be clearer."
    - throwaway894345 6y ago
      > people hold it to unreasonable standards of clarity and correctness. I only said it would be better if it were clearer. I'm not arguing that it's unfit for HN or any other venue. You're reading much too far into this.
      - klodolph 6y ago

dundarious 6y ago

See Alexandrescu’s Fastware talk on how amazingly sentinels can improve even textbook algorithms, and how to apply the approach intelligently. E.g., for a linear search, overwrite the last element with the sought after value, and do a tiny bit of work to make that safe and to undo it before return. If you’re skeptical, I really do encourage you to watch, he’s not sloppy. https://youtu.be/AxnotgLql0k https://youtu.be/AxnotgLql0k

deleted 6y ago
[deleted]
bjoli 6y ago
This brings back memories! I discovered the same thing in high school in a programming class. We had a speed-golfing assignment and in the end my program ended up quite a bit faster than the "golden reference" our teacher had. He refused to believe I had come up with it myself (though I got the highest grade on the assignment). This was back when we could assume 8-bit encodings(iso 8859-1 was the one we used). Simpler times!

hinkley 6y ago

Is that even the core contention? Or is the core contention that within mutable data it's possible to destroy the sentinel through bugs or malice?