For those unfamiliar with sentinel values <https://en.wikipedia.org/wiki/Sentinel_value>, think "zero terminated string" instead of "knowing the length of the string and checking if you are inbound every step" - the former removes a comparison, because termination can become part of the character lookup.
Andrei Alexandrescu just gave a keynote about this very old technique. One thing to note was his claim that while this can be a very effective technique, it is not used in generics often, due to a lack of introspection capabilities in most programming languages. Enter Julia? It's a long presentation (albeit an entertaining one, as Alexandrescu's presentation tend to be) and there is no transcript yet AFAIK, so I'll also link directly to different parts: - Slideshare upload of the presentation slides <http://www.slideshare.net/AndreiAlexandrescu2/accu-keynote-by-andrei-alexandrescu> - Youtube upload of the presentation <https://www.youtube.com/watch> (total time: 1h06m). - 10m28s <https://www.youtube.com/watch?v=AxnotgLql0k&t=10m28s>: reintroduction to sentinels, and how to get sentinel guards in generic code with introspection. Uses Linear Find as an example - 29m04s <https://www.youtube.com/watch?v=AxnotgLql0k&t=28m4s>: sentinels in Tony Hoare's partitioning - 37m54s <https://www.youtube.com/watch?v=AxnotgLql0k&t=37m54s>: new-ish trick: creating a vacancy in the range to reduce full swaps to half-swaps: - put sentinels at both ends - remove pivot value to create a "vacancy" in the range: an empty slot in the range to move a value to - break swap into two assignments - a swap fills one vacancy and leaves another to be filled in from the other side - turns swaps into half-swaps, no need for temporary values! - at the end fill in the vacancy with removed value - cleanup - 49m13s <https://www.youtube.com/watch?v=AxnotgLql0k&t=49m13s>: claims of this trick being generalisable to many situations: - Dot product - Set intersection - Merging sorted lists - Lexing and parsing Given that at least three of these example are things I expect Julia does a lot, and that there might be more places this is effective, I figured this might be relevant to your interests. Then again, for all I know this is a trick the Julia team is already employing everywhere that it makes sense :P (Found on /r/programming <https://www.reddit.com/r/programming/comments/4jlkhv/accu_2016_keynote_by_andrei_alexandrescu/>, see comments there <http://Found on /r/programming>)
