News for hackers. Stuff that matters.
Re:Sentinels Can Be Faster by lalaland1125 on Wednesday September 09, 2020 @03:44PM (#24425074)
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.
Re:Sentinels Can Be Faster by dundarious on Wednesday September 09, 2020 @04:19PM (#24425459)
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

Re:Sentinels Can Be Faster by bjoli on Thursday September 10, 2020 @04:24AM (#24430098)
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!

Re:Sentinels Can Be Faster by hinkley on Wednesday September 09, 2020 @04:46PM (#24425736)
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?
Re:Sentinels Can Be Faster by throwaway894345 on Wednesday September 09, 2020 @03:53PM (#24425191)
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.
Re:Sentinels Can Be Faster by klodolph on Wednesday September 09, 2020 @08:25PM (#24427594)
That is the framing of the article.
Re:Sentinels Can Be Faster by throwaway894345 on Thursday September 10, 2020 @11:13AM (#24433075)
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.
Re:Sentinels Can Be Faster by klodolph on Thursday September 10, 2020 @02:01PM (#24434882)
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."

Re:Sentinels Can Be Faster by throwaway894345 on Thursday September 10, 2020 @03:03PM (#24435486)
> 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.

Re:Sentinels Can Be Faster by klodolph on Thursday September 10, 2020 @04:23PM (#24436212)
HN would be better off if people didn't nitpick the framing of articles. That's what I'm saying.
Re:Sentinels Can Be Faster by throwaway894345 on Saturday September 12, 2020 @11:41AM (#24453269)
That's certainly one possible opinion. Let's stay on topic though.
Re:Sentinels Can Be Faster by klodolph on Saturday September 12, 2020 @03:06PM (#24454654)
This isn't Usenet, HN doesn't have "topics".
Re:Sentinels Can Be Faster by colejohnson66 on Wednesday September 09, 2020 @03:50PM (#24425144)
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().
Re:Sentinels Can Be Faster by twic on Wednesday September 09, 2020 @04:05PM (#24425320)
It would be even better if it was terminated by 8-len%8 null bytes, as that would make blocked loops simpler.
Re:Sentinels Can Be Faster by throwaway894345 on Wednesday September 09, 2020 @03:57PM (#24425231)
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?
Re:Sentinels Can Be Faster by pengaru on Wednesday September 09, 2020 @04:03PM (#24425305)
> 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.

Re:Sentinels Can Be Faster by steveklabnik on Wednesday September 09, 2020 @04:23PM (#24425516)
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.

Re:Sentinels Can Be Faster by throwaway894345 on Wednesday September 09, 2020 @05:50PM (#24426339)
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?

Re:Sentinels Can Be Faster by steveklabnik on Wednesday September 09, 2020 @05:55PM (#24426378)
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...

Re:Sentinels Can Be Faster by colejohnson66 on Wednesday September 09, 2020 @06:12PM (#24426520)
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).
Re:Sentinels Can Be Faster by steveklabnik on Wednesday September 09, 2020 @06:15PM (#24426538)
Yep!
Re:Sentinels Can Be Faster by colejohnson66 on Wednesday September 09, 2020 @04:04PM (#24425312)
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.
Re:Sentinels Can Be Faster by saagarjha on Wednesday September 09, 2020 @07:54PM (#24427375)
Note that C++11 got this right, this wasn't guaranteed prior to that.