J’aime le Big-O mais il me trompe

Talk de Valentin Deleplace; développer chez google Cloud. @val_deleplace

Presentation

Nous apprenons que trier N éléments prend un temps proportionnel à (N log N). Concentrons-nous sur la complexité algorithmique, le reste ce sont des détails d’implémentation! Cette approche universitaire permet en effet d’être rapidement productif en faisant abstraction de l’architecture physique des ordinateurs, du jeu d’instruction du microprocesseur, de la latence du SSD. Attention, c’est parfois un gros mensonge! Quand vous avez besoin d’améliorer les performances, c’est rarement “Big-O” qui vous y aidera. Je vais montrer plusieurs exemples où l’analyse de la complexité algorithmique ne sert à rien, et quelques cas où elle vous envoie carrément dans le mur. Mieux vaut être terre-à-terre, ne pas ignorer les coefficients multiplicateurs “cachés”, apprendre la “compassion mécanique”, et surtout mesurer les véritables latences, encore et encore.

Notes

La théorie : f(n) = O(n2) : La fonction f croit au niveau de n2

Il existe un entier n0, a partir du quel le big O fait sense.

Le Log

• Considérer log(n) comme un coefficient constant
• L’algo croit constamment qu’on peut

L’homme est la mesure de toute chose. Platon

Il y a 3 aspets a vérifier :

• Petite
• Moyenne
• Grande (type BigO)

Le broblème central :

• Ignorer les constantes
• La coutume est de supprimer les constantes => Pour dire en fin que f(n) € O(n2) en oubliant K & n0

Le pragmatisme : il faut tenir compte de tout ce qui impacte l’alto

• CPU cycle
• Cache access (L1,Lé,L3)
• Main memory access
• Solid-state disk IO
• Rotation disk IO

Voir les mesure et profiling pour savoir combien de temps : Générer un flame graph

Le speaker a parlé d’un exemple de Probleme : (N+1) Select problem

Conclusion :

• Le calcul de gibO est utile, mais faire des mesures c’est mieux
• Ne dit pas la vérité
• La latence côté user s’explique par les coefficient caché
• La formule de O ne sait pas qu’est ce qui plus rapide (cache / mémoire)
• Il faut identifier les goulots d’étrangement humainement, sans forcément
• Il faut mesurer les performance en 2 moments :
• Milieu / fin de projet quand l’archi est testable
• En production (mesure & constat des perf réelle)

Beware of bugs in the above code, I have only proved it correct, not tried it => Donald Knuth

Tools : Flame Graph / PProf