Hi, TL;DR: - reminder that quadratic algorithms are rare, but easily introduced by sloppiness - request to change QUIP-16 to allow fixing quadratic behaviour in all branches
Quadratic Bahaviour O(N²) behaviour is very, very bad: doubling the input size quadruples the run-time, a 10x increase in input size causes a 100x increase in runtime. For the vast majority of algorithms, much better algorithms exist: - Bubblesort is quadratic, but Introsort (std::sort) is O(NlogN), so quasi-linear (because logN < 64 on all current hardware) - insert or erase into a sequential container in a loop is quadratic, but linear (unsorted) or linearithmic (O(NlogN), sorted container) There is absolutely no excuse to use a quadratic algorithm when a faster-O one exists, and we should fix quadratic behaviour whereever we find it, because it can mean the difference between usable and not usable for our users. QUIP-16 In that vein, I would suggest to amend QUIP-16, which, currently, slaps all algorithmic complexity improvements into one bucket, and limits the cherry-picking to LTS Strict (excluding LTS Very Strict), to realize that there is a material difference between, say, a 2x or 3x speed-up or a O(N) to O(logN) improvement on one side and a O(n) to O(n²) speedup on the other, and allow the latter for all active branches. Fixing quadratic behaviour is _not_ your garden-variety performance improvement! Proposed change: https://codereview.qt-project.org/c/meta/quips/+/627689 See https://codereview.qt-project.org/q/owner:marc.m...@qt.io+message:quadratic for example fixes. Thanks, Marc -- Marc Mutz <marc.m...@qt.io> (he/his) Principal Software Engineer The Qt Company Erich-Thilo-Str. 10 12489 Berlin, Germany www.qt.io Geschäftsführer: Mika Pälsi, Juha Varelius, Jouni Lintunen Sitz der Gesellschaft: Berlin, Registergericht: Amtsgericht Charlottenburg, HRB 144331 B -- Development mailing list Development@qt-project.org https://lists.qt-project.org/listinfo/development
