News for hackers. Stuff that matters.

A comment on Myths Programmers Believe about CPU Caches (2018). Parent comment

Re:Myths Programmers Believe about CPU Caches (2018) by hvidgaard on Thursday November 21, 2019 @09:02AM (#21594055)
On the BigO notation, you have to remember is that it's an upper bound on the runtime. There is no guarantee other than the growth of the function.
[ Parent | on HN ]
Re:Myths Programmers Believe about CPU Caches (2018) by elweston2 on Friday November 22, 2019 @09:17AM (#21605703)
Oh I agree. It is just that +C bit. What happens when your O(nLog(n)) basically just trashes the cache because of your data structures? Yet maybe something 'worse' would run better because of the way cache works? That +c bit can sometimes turn into its own big O. It is a nasty little gotcha when it does happen.

It is a good framework to get you in the ballpark of the correct thing. Even usually 99% of the time it is right. But sometimes the arch bites back due to your data.

[ Parent | on HN ]