News for hackers. Stuff that matters.
Re:What to use instead of std::set [pdf] by ludwigschubert on Thursday August 25, 2016 @11:42AM (#12359917)
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?

Re:What to use instead of std::set [pdf] by Analemma_ on Thursday August 25, 2016 @01:08PM (#12360654)
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...
Re:What to use instead of std::set [pdf] by taeric on Thursday August 25, 2016 @01:35PM (#12360868)
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.

Re:What to use instead of std::set [pdf] by kazinator on Thursday August 25, 2016 @01:27PM (#12360797)
This is covered in digital design and computer architecture courses. But kind of in isolation from data structures and algorithms.