3 ms·
It's a good rule of thumb that can be quite useful without additional analysis. It's not always the right way to do performance tuning, but I can't count the n
by cogman10 4mo ago
It's a good rule of thumb that can be quite useful without additional analysis. It's not always the right way to do performance tuning, but I can't count the number of times I've changed an O(n^3) to an O(n) and seen massive performance gains as a result.
- marginalia_nu 4mo agoYeah it helps make awful code decent, and some algorithms are better than others, but in terms of high performance code, locality, vectorization, and branching often matter much more big O.
- cogman10 4mo agoTotally agree, but I'm in Java land and cursed to have about the worst case scenario for those things :D
- marginalia_nu 4mo agoOh yeah I'm also mostly in Java land. These concerns are also concerns in Java, plus whatever C2 gets up to.
- cogman10 4mo agoValhalla can't come soon enough. I've definitely had to change things into SOA in order to eke out performance. My coworkers aren't thrilled seeing `double[] x; double[] y;` but that really is about the only way to get the JVM to play nice.
- bluGill 4mo agoThat depends on what end ends. For a small N, very bad algorithms can still be plenty fast. Sometimes it can even be faster. Some of your lower O algorithms can have very terrible constant factors, which means they're terrible when N is small, but as N gets large. Big and small N different for different algorithms and hardware both.