Never heard of the linear search with a sentinel value so needed to look it up. Here is a link in case anyone wants to learn what it is:

http://www.delorie.com/gnu/docs/avl/libavl_26.html

Andrei Alexandrescu describe the usage of this kind of search to speed up quicksort in his 'Fastware' (fun) video: https://www.youtube.com/watch?v=AxnotgLql0k

Discussed here: https://www.reddit.com/r/programming/comments/4jlkhv/accu_20...

Computer science curricula usually contain an introductory algorithms and data structures class, but these don't usually put focus on topics like cache locality or branch prediction.

Do you agree? And if so, would that—at least partially—explain your observation?

My undergraduate algorithms course did point out that memory hierarchies and branch predictors laugh at big-O notation, and that you should always (as Roboprog said) measure measure measure instead of just assuming a particular algo is best. It was one little piece of material in a course with a lot of ground to cover though, so it's hard to say how well it stuck with the class...

I honestly don't know. I should call out that my number of 1k is probably wrong. I wouldn't be surprised if it is too high. Though, it will probably depend a lot on caching.

Basically, it is a hard thing where being wrong flat out doesn't matter the vast majority of the time.

I think education does folks a disservice by asking "what is the fastest" or "which one should you choose" in many scenarios. Instead, we want people to be able to reason about all of the choices more holistically, which is not an easy task.

This is covered in digital design and computer architecture courses. But kind of in isolation from data structures and algorithms.

Kinda. Paul Khuong goes into depth here. https://www.pvk.ca/Blog/2012/07/03/binary-search-star-elimin...

Interesting. Yeah, performance tuning is a deep well to fall into :-)

Measure, measure, measure. How (memory) expensive is the element-matches check (can the array bound or address of final element stay in a register)? How often does the search fall off the end, vs finding something, perhaps in a list sorted in most often used order?

Alternately, would a trie be better than an array search? (Depends on key length, set element count, usage patterns...)