[Development] On quadratic behaviour

[Marc Mutz]

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.mutz@qt.io+message:quadratic 
for example fixes.

Thanks,
Marc

-- 
Marc Mutz <marc.mutz at 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