Défi : traiter 1 milliard de lignes en Go, de 1 min 45 s à 4 s avec 9 méthodes

• 1BRC : un challenge consistant à écrire du code qui lit des mesures de température dans un fichier texte de 1 milliard de lignes et calcule, pour chaque station, la température minimale, moyenne et maximale
• Il s’est déroulé du 1er janvier au 31 janvier 2024, avec pour objectif d’exploiter au maximum les versions récentes de Java
• Le sujet a ensuite suscité l’intérêt de nombreuses personnes, qui ont commencé à relever le défi dans divers langages (Rust, Go, C++, SQL)
• Présentation détaillée de 9 solutions écrites en Go (de la plus lente à la plus rapide)

Mesures de base

• Le temps nécessaire pour lire les 13 Go de données texte (1 milliard de lignes) avec la commande cat est de 1,052 seconde.
• La commande wc, qui traite réellement le fichier, prend presque 1 minute (55,710 secondes).
• Résoudre le problème avec une solution AWK prend 7 minutes et 35 secondes.

Solution 1 : Go simple et idiomatique

• La première solution, basée sur la bibliothèque standard de Go, prend 1 minute et 45 secondes.
• Elle lit les lignes avec bufio.Scanner et les découpe sur ';' avec strings.Cut.
• Elle analyse la température avec strconv.ParseFloat et accumule les résultats dans une map Go.

Solution 2 : map avec valeurs pointeurs

• Utilisation de map[string]*stats pour éviter deux opérations de hachage dans la map.
• L’usage de valeurs pointeurs fait passer le temps de 1 minute et 45 secondes à 1 minute et 31 secondes.

Solution 3 : éviter strconv.ParseFloat

• La température est analysée avec du code personnalisé au lieu de strconv.ParseFloat.
• Le temps passe de 1 minute et 31 secondes à 55,8 secondes.

Solution 4 : utiliser des entiers à virgule fixe

• Les températures sont représentées par des entiers afin d’éviter les opérations en virgule flottante.
• Le temps passe de 55,8 secondes à 51,0 secondes.

Solution 5 : éviter bytes.Cut

• Au lieu de parcourir tout le nom de la station pour trouver ';', l’analyse se fait depuis la fin.
• Le temps passe de 51,0 secondes à 46,0 secondes.

Solution 6 : éviter bufio.Scanner

• bufio.Scanner est supprimé et le fichier est lu par gros chunks.
• Le temps passe de 46,0 secondes à 41,3 secondes.

Solution 7 : table de hachage personnalisée

• Une table de hachage personnalisée est implémentée à la place de la map Go.
• Le temps passe de 41,3 secondes à 25,8 secondes.

Solution 8 : traitement parallèle par chunks

• La version simple et idiomatique est parallélisée, ce qui réduit le temps de 1 minute et 45 secondes à 24,3 secondes.

Solution 9 : toutes les optimisations + parallélisation

• La combinaison de toutes les optimisations avec le traitement parallèle réduit le temps de 24,3 secondes à 3,99 secondes.

Tableau des résultats

• Un tableau compare toutes les solutions Go, ainsi que les solutions Go et Java les plus rapides.
• La plus rapide des versions Go traite le fichier en 2,90 secondes, contre 0,953 seconde pour la version Java.
• La version Java sous la seconde a été réalisée par Thomas Wuerthinger (créateur de GraalVM), ce qui semble possible grâce à son expertise dans ce domaine.

Commentaire final

• Pour les tâches de programmation du quotidien, un code simple et idiomatique constitue un bon point de départ.
• Lorsqu’on construit un pipeline de traitement de données, rendre le code 4 ou 26 fois plus rapide peut améliorer la satisfaction des utilisateurs et réduire les coûts de calcul.
• Lorsqu’on développe un runtime ou un interpréteur, les gains de performance sont importants.

Avis de GN⁺

• Cet article offre une étude de cas intéressante sur l’optimisation des performances en explorant diverses façons d’optimiser le traitement de données à grande échelle avec Go.
• Il montre que, dans le processus d’optimisation, implémenter des structures de données comme une table de hachage personnalisée au-delà de la bibliothèque standard de Go joue un rôle important.
• Il met en avant l’effet du traitement parallèle, et montre qu’en combinant optimisation sur un seul cœur et parallélisation, on peut obtenir des gains de performance remarquables.
• L’article fournit des enseignements utiles aux ingénieurs logiciel qui développent des applications sensibles aux performances.
• L’utilité réelle de ces optimisations en production peut toutefois varier selon le cas d’usage. Toutes les applications n’ont pas nécessairement besoin d’un tel niveau d’optimisation.

[cosine20]

Je me demande concrètement quel travail a été effectué à l’étape 7. C’est la section où le gain de performances a été énorme, haha.

[sddsdd94]

C’est intéressant de voir le gain de performance indiqué séparément à chaque étape, haha.

[galadbran]

Avec wc, ça prend aussi une minute... décidément, le mieux reste encore de ne pas écrire de code... haha

[jhbaek]

Merci de partager cet excellent article. Ça me rappelle l’époque où j’étais obsédé par l’optimisation système haha.
Avec les années d’expérience en développement, j’ai souvent constaté que le code optimisé au maximum est difficile à maintenir, ce qui le rend compliqué à exploiter dans un environnement d’équipe ; du coup, je me suis peu à peu éloigné de la voie de l’optimisation. (Petite réflexion personnelle soudaine)

[misolab]

Du code optimisé pour l’organisation !!

[GN⁺]

Réactions sur Hacker News

• Le premier utilisateur mentionne qu’il n’avait pas d’expérience en optimisation de code pour la manipulation de données, et qu’il a donc trouvé particulièrement intéressante la première section qui obtient des mesures de référence avec cat, wc, etc. Il considère que c’est un moyen simple d’obtenir une fourchette « raisonnable ».
• Le deuxième utilisateur mentionne qu’avec la bibliothèque Polars, le temps de traitement est de 33 secondes, et exprime son intérêt pour la solution la plus simple qui se rapproche de la solution optimisée manuellement la plus rapide.
• Le troisième utilisateur indique que le rapport de profilage des performances en Go est déroutant et explique que, lorsqu’il n’est pas intuitif de comprendre le temps d’exécution d’une ligne de code donnée, c’est peut-être parce que les données sont difficiles à prédire et que le prédicteur de branche se trompe.
• Le quatrième utilisateur partage le résultat de son exécution du 1BRC (1 Billion Row Challenge) en Go et dit avoir appris des techniques d’optimisation spécifiques à Go. Par exemple, la lecture mémoire sans vérification des limites avec unsafe.Pointer, le fait que les fonctions des packages bytes et bits de la bibliothèque standard sont écrites en assembleur, la désactivation du garbage collector, ou encore la manière d’épingler une goroutine à un thread.
• Le cinquième utilisateur affirme qu’un développeur de scripts shell aurait déjà terminé le traitement de ces 1 milliard de lignes pendant que les développeurs des autres langages se préparent encore.
• Le sixième utilisateur affirme que les bases de données sont plus rapides, moins complexes et plus robustes aux mises à jour de données que le code applicatif, et souligne qu’il faudrait faire davantage de travail dans la base de données.
• Le septième utilisateur partage son expérience d’avoir développé en 2010, avec PostgreSQL, une application web interrogeant 270 millions de lignes de données climatiques d’Environnement Canada, et précise que ce logiciel a reçu un prix. L’application avait été optimisée pour générer des rapports en moins d’une minute.
• Le huitième utilisateur remarque qu’il est appréciable que le code parallèle en Go conserve malgré tout le style idiomatique propre à Go.
• Le neuvième utilisateur mentionne que, pour traiter de gros fichiers texte en CLI, le fait d’ignorer l’analyse Unicode rend awk, grep, etc. nettement plus rapides, et affirme qu’en ajoutant LC_ALL=C à la solution awk, on peut ramener le temps de traitement à moins d’une minute.
• Le dernier utilisateur trouve intéressant que la version Java la plus rapide soit plus rapide que la version Go la plus rapide, et estime que les performances de la JVM sont particulièrement bonnes.