Hacker News Reader

- Knuth puts sentinels at the end of an array to avoid having to bounds check in the search. - Knuth uses the register keyword. - Knuth custom writes each data structure for each application.

View on HN

When I was young someone pointed out to me how each hype cycle we cherry-pick a couple interesting bits out of the AI space, name them something else respectable, and then dump the rest of AI on the side of the road.

When I got a bit older I realized people were doing this with performance as well. We just call this part architecture, and that part Best Practices.

I like to call anything I don't like "anti-patterns".

When Knuth wrote his paper compilers/optimizer were not nearly as good as today, and CPUs were much more deterministic (only disk access shows the issues we now see with cache misses). Most of his optimizations are things that the compiler will do better than you can (most is not all!) and so not even worth thinking about. Meanwhile the compiler will almost never turn a O(n^2) into O(n*ln(n)) despite that resulting in a much faster speedup than anything the compiler can do.

Knuth does this today.

And a compiler will never make sentinels for you. Most of these tricks still work and have a measurable difference.

Reply on news.ycombinator.com