Re:Learn Big-O and stop hacking your way through algorithms
by smabie on Thursday August 20, 2020 @06:46PM
(#24229902)
In fact, with the way that modern CPUs work, big O can be very misleading, especially with small to moderate amounts of data. Performance nowadays is all about memory locality, avoiding pointers, eliminating the need for branches, etc.
For example, with Scala simple Arrays outperform most other collections, including Vectors and Lists, even when the big O is bad.
Array languages are especially powerful, even though algorithms implemented in them often do a lot of extra work. If you can keep all of your data in L1, it doesn't much matter what big O you have (usually) and the most naive data structures and algorithms will usually outperform fancy pointer chasing stuff in L3 or RAM.
For example, with Scala simple Arrays outperform most other collections, including Vectors and Lists, even when the big O is bad.
Array languages are especially powerful, even though algorithms implemented in them often do a lot of extra work. If you can keep all of your data in L1, it doesn't much matter what big O you have (usually) and the most naive data structures and algorithms will usually outperform fancy pointer chasing stuff in L3 or RAM.