[Development] On quadratic behaviour

[Volker Hilsheimer]

> On 27 Feb 2025, at 09:37, Marc Mutz via Development <development at qt-project.org> wrote:
> 
> 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


As long as there is a user-originated P1 ticket (which is the case for https://bugreports.qt.io/browse/QTBUG-127549), cherry-picking order-of-magnitude performance improvements back into a very strict branch should be generally acceptable, especially when we regressed.

Maintainer discretion applies as usual. The change might be in very poorly tested code, in which case it’s better to be slow and correct than fast and wrong.

Details as comments on the code review.

Volker