A quel point le langage C permet-il de faire des codes rapides ?

Pour optimiser la vitesse au max, est-il le meilleur ?

Le problème exposé dans ce sujet a été résolu.

Bonjour,

Je suis de retour avec une question très générale sur le langage C. Je mets ci dessous un petit exemple codé rapidement d’une implémentation d’une fonction qui copie le contenu d’une chaine de caractères dans une autre. C’est ultra basique et la librairie standard fournit déjà des solutions à ce problème. Mais justement.

Est-ce que le langage C permet bien de faire les codes les plus rapides qui soient ? Je veux dire, est-ce que les programmes les plus gourmands et les plus optimisés sont codés en C ? Ou auraient intérêt à l’être ? Ou pourraient avoir intérêt à l’être ?

J’ai déjà un peu codé en python et pour l’exemple, on ne faisait pas de manipulations sur les images pixel par pixel en python car c’était beaucoup trop lent. On utilisait des librairies apparemment codées en C qui faisaient ces manipulations basiques.

En bref, quand je code un algo de copie d’une chaine dans une autre comme ci-dessous, ai-je la garantie que si je m’y prends pas comme un pied, les performances seront très similaires à celles de la librairie standard, et donc je suppose, de ce qui se fait de plus optimisé pour un tel algo ? La librairie standard est-elle codée en assembleur pour optimiser encore plus ? Et est-ce que coder en assembleur produirait des algos encore plus rapides, ou bien est-ce que le langage C est déjà au max ?

Et enfin, même si je compte un jour aller y jeter un œil par moi-même, est-ce que les codes de la librairie standard sont à peu près compréhensibles pour un être humain qui connaît le langage C rapidement, où est-ce qu’elle a été codée par des sorciers qui utilisent des goto toutes les 3 lignes pour ne pas perdre la moindre nanoseconde de temps ?

Le code en question :


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void stringCopy(char* dest, const char* src, size_t sizeDest)
{
	if (sizeDest > 0)
	{
		size_t indexDest;
		for (indexDest = 0; indexDest < sizeDest - 1; indexDest++)
		{
			dest[indexDest] = src[indexDest];

			if (src[indexDest] == '\0') break;
		}
		dest[indexDest] = '\0';
	}
}

int main()
{
	char dest[100];

	stringCopy(dest, "coucou le monde", 100);
	printf("dest : %s\n", dest);

	return 0;
}

Et est-ce que coder en assembleur produirait des algos encore plus rapides, ou bien est-ce que le langage C est déjà au max ?

Dans le cas général, certains compilateurs comme gcc ou clang font un travail de dingue. Amuse-toi à compiler des petites fonctions avec un flag -O3 et regarde le code assembleur généré. Le compilateur pense à des astuce que le programmeur lui-même n’aurait pas forcément eues.

Cela dit, ça ne t’empêche pas d’écrire du code C optimisé en prenant compte en amont le fonctionnement la machine. Il y a des leviers intéressants qui ne nécessitent aucunement d’avoir recours à l’assembleur, par exemple :

  • structurer son programme pour optimiser les accès mémoire et la mise en cache CPU ;
  • donner des hints au compilateur pour qu’il puisse générer un code assembleur plus optimal dans le cas général en structurant correctement les branches ([[likely]] ou [[unlikely]] après les conditions)

Là où écrire de l’assembleur c’est généralement une excellente idée niveau performance, c’est quand il faut utiliser des instructions spécialisées, comme par exemple les très connues SSE et AVX (SIMD), mais aussi des trucs encore plus spécifiques. Je me souviens par exemple d’instructions spécialement faites pour calculer des SHA512 sur les puces Arm M1 d’Apple. Aussi malin soit-il, un compilateur C ne peut pas deviner que tu écris justement une implémentation de SHA512 pour te pondre les instructions spécialement prévues. Idem pour les instructions AES qui sont prévues pour… faire de l’AES.

La librairie standard est-elle codée en assembleur pour optimiser encore plus ?

Ça dépend de laquelle. Dans celle de GNU, c’est le cas parfois1, voici un exemple récent où on a recours à l’assembleur pour utiliser spécifiquement certaines instructions intéressantes dont on parlait : https://sourceware.org/git/?p=glibc.git;a=commit;h=58bcf7b71a113378dd490f6c41931a14f25a26c9

Une lib C standard peut aussi avoir un impératif de compatibilité maximum, de sécurité maximum, etc., et cela au prix de la performance. Donc la réponse dépend de chaque lib C.

Quant à ton code, il est algorithmiquement assez trivial pour que l’optimisation de la performance de calcul brute ne se pose pas. Tes facteurs limitants dans ce programme sont finalement externes : c’est l’accès en lecture et en écriture à la RAM, ainsi que l’appel système qui permet d’afficher coucou le monde.

Comme dans beaucoup de programmes, la performance ne tient pas que du fait que le calcul brut soit optimisé sur les algos mais plutôt du fait d’une utilisation correcte et savante des API du système (bufferiser correctement, utiliser un syscall spécialisé qui fait du zero-copy, éviter les allers et retours inutiles entre l'userspace et le kernel, éviter d’appeler le kernel trop souvent (overhead induit de chaque appel), gestion stratégique des lock et des allocations mémoire, …).

Cela permet d’esquisser une réponse à la question :

Est-ce que le langage C permet bien de faire les codes les plus rapides qui soient ? Je veux dire, est-ce que les programmes les plus gourmands et les plus optimisés sont codés en C ? Ou auraient intérêt à l’être ? Ou pourraient avoir intérêt à l’être ?

En termes de performances brutes, certaines implémentations C font un travail formidable. Mais le C n’a pas le monopole : d’autres langages qui ont un backend LLVM utilisé correctement rivalisent.

Mais comme on l’a vu, la performance brute des algos ne fait pas tout. Il faut aussi savoir composer correctement avec le système sous-jacent. À cet égard, je dirais que le C a l’avantage d’être l’interface en vigueur dans le cas général. Sous Linux, par exemple, utiliser le nouveau syscall à la mode quand on fait du C, c’est facile sans se poser trop de questions, sans faire un binding ou un wrapper, etc. Ce n’est pas impossible avec un autre langage, mais l’expérience n’est pas toujours très lisse. Mais pour le C, c’est là un avantage de situation plutôt qu’un avantage intrinsèque.


  1. Sans compter le cas de l’implémentation des syscalls.
+1 -0

D’une manière générale, le point limitant des performances est rarement le CPU, qui passe quand même beaucoup de temps à attendre qu’on veuille bien lui donner du boulot. Les deux contre exemples qui me viennent en tête sont le jeu vidéo et le calcul haute performance. Dans le reste des usages, même si un programme lourd (légitimement ou non) fait que l’utilisateur aura du lag et une mauvaise expérience, en fait le CPU passe quand même beaucoup de temps à attendre.

Ça ne veut pas dire qu’il faut faire n’importe quoi, au contraire. La surconsommation des programmes actuels est un vrai problème, mais c’est souvent des problèmes d’algorithmique et de fonctionnalités inutiles plus que de langage.

Dernier point pour ton strncat à la main, le compilo ferait un meilleur boulot de compilation en l’aidant

  • utilisation de restrict
  • organisation du code pour aider à vectoriser (le nombre d’itérations doit être connu à l’avance, or le break en plein milieu l’interdit),

Maintenant dans ce cas particulier, il y a carrément une optimisation dédiée: https://sourceware.org/pipermail/libc-alpha/2019-January/100459.html (et pas accessible au commun des mortels). On n’a aucune raison valable d’éviter la lib standard. Le seul intérêt à réécrire ces fonctions, c’est dans des TDs pour débutants ou pour pratiquer nos katas.

EDIT: avec ce genre de fonction on est dans la non prematrure-pessimisation. On sait que c’est beaucoup utilisé, pas toujours dans des chemins critiques cotés perfs, mais pour les cas où cela l’est, alors il est vraiment plus intelligent que cela soit très optimisé.


Concernant Python, le C, le C++ et les libs. Python est avant tout interprété et on récupère de la performance en utilisant des syntaxes qui vont en fait se finir en appel de fonctions plus ou moins complexes qui sont écrites dans d’autres langages (C, C++, Fortran…) et surtout optimisées. Ou pourquoi on évite les boucles.

Naïvement on pourrait croire que si une multiplication de matrice est lente avec des boucles en python, et qu’en interne c’est du C ou du C++, on fera mieux en écrivant cette fonction nous même en C ou C++.

C’est faux. Il y a un savoir faire derrière l’écriture efficace de ces fonctions. Un programme Python qui multiplie des matrices avec scipy sera toujours plus performant qu’une multiplication naive de matrice écrite en C ou C++. Pourquoi? Parce que scipy va dépendre d’une des multiples implémentations disponible de la multiplication (entre LAPACK, OpenBLAS, ATLAS, IntelMKL…). Ces libs sont écrites en mélange de C et de Fortran en général, voire avec des gros morceaux d’assembleur dedans (MKL) et on sait que sur une plateforme Intel on fera difficilement mieux que la MKL (normal, ils connaissent leurs procs!).

Maintenant on peut totalement avoir les mêmes perfs en C++: en utilisant une lib dédiée (Eigen, Blaze…) qui en sous-main sous traite aussi à la MKL…

Salut,

Et enfin, même si je compte un jour aller y jeter un œil par moi-même, est-ce que les codes de la librairie standard sont à peu près compréhensibles pour un être humain qui connaît le langage C rapidement, où est-ce qu’elle a été codée par des sorciers qui utilisent des goto toutes les 3 lignes pour ne pas perdre la moindre nanoseconde de temps ?

AScriabine

Juste sur ce point et pour compléter les propos de @sgble, la glibc est effectivement assez cryptique par moment. Cela dit ce n’est pas la seule implémentation de la libc disponible, tu as par exemple musl ou celle du projet OpenBSD. :)

+1 -0

Salut,

En plus du fait qu’il faut effectivement utiliser correctement C pour que le code écrit avec soit rapide (ce qui n’est pas facile!), il y a un autre point à prendre en compte pour répondre à cette question

Est-ce que le langage C permet bien de faire les codes les plus rapides qui soient ? Je veux dire, est-ce que les programmes les plus gourmands et les plus optimisés sont codés en C ? Ou auraient intérêt à l’être ? Ou pourraient avoir intérêt à l’être ?

Un des problèmes de C en matière de performances est le fait qu’il est extrêmement permissif, et ceci limite en fait ce que le compilateur peut faire comme optimisations. L’exemple cité couramment est celui de l’aliasing : tu peux avoir deux pointeurs qui pointent vers la même chose en mémoire avec la possibilité d’y lire et d’y écrire. Ça vaut dire que le compilateur ne peut pas toujours par exemple virer une lecture en mémoire et réutiliser ce qui est déjà dans un registre parce qu’il est possible qu’un autre pointeur a écrit entre temps et donc que la valeur dans le registre n’est plus à jour. En théorie, ça veut dire qu’un langage comme Rust qui est beaucoup plus strict sur les programmes qu’il accepte (et donc a plus de propriétés à utiliser pour pouvoir faire des optimisations valides) pourrait produire du code machine de meilleur qualité que C. En pratique, ce n’est en général pas encore le cas à cause de la maturité des compilateurs C, et aussi à cause du fait que LLVM (par exemple) ne sait pas encore exploiter ces propriétés comme il n’y a pas vraiment eu de langages répandus qui pouvaient les garantir avant. Ça s’améliore mais c’est pas encore parfait, il y a souvent des optimisations LLVM (comme l’opti noalias que je mentionne précédemment) qui sont désactivées ou réactivées par défaut dans les versions de Rust selon le degré de confiance que LLVM fait bien la bonne chose derrière.

Note que la permissivité de C se fait aussi ressentir ailleurs. Le dernier exemple en tête date de la dernière version de Rust sorti hier qui utilise maintenant des mutex plus fines et rapides que précédemment sous Linux au lieu d’utiliser celles de pthreads qui sont programmées défensivement contre le gruyère de permissions qu’est C.

+0 -0

La première question à se poser, c’est la raison pour laquelle un programme est lent ou risque d’être lent. Il y a tout plein de raisons possible et écrire un programme (ou une partie du programme) en C n’aide que dans certains cas et va être une (très) mauvaise idée dans d’autres.

Utiliser le C dans un programme te permet d’avoir un contrôle complet sur ce qui est fait et donc de ne pas "gaspiller" des cycles CPU ou de la RAM si le code est bien écrit. En contre-partie, ça sera à toi de t’occuper de beaucoup plus de trucs. Donc dans un scénario où tu dois écrire du code pour une machine dont la mémoire et la vitesse CPU se comptent en KB et KHz, le C est la solution la plus couramment utilisé. De même, si t’écris un programme qui fait surtout du calcul avec peu d’entrées/sorties et qu’il tourne sur assez de machines pour que 1–2% de performance se chiffre en millions, le C peut avoir un avantage (mais moindre que dans le premier cas).

Dans tous les autres cas, le C est loin d’être un bonne solution et risque d’être plus problématique qu’autre chose. Tout particulièrement, si ton programme passe la majeur partie de son temps à gérer des entrées/sorties (disque, réseau et autres) ou à attendre qu’un autre programme fasse son travail (par exemple attendre une réponse d’une base de donnée), le C est une mauvaise idée.

De même, si le problème est que tu utilises un algo peu efficace (genre complexité quadratique alors qu’il est possible d’en écrire un en O(n×log(n))O(n\times log(n)), ce n’est pas en changeant de langage de programmation que tu vas vraiment améliorer les choses.

Un des problèmes de C en matière de performances est le fait qu’il est extrêmement permissif, et ceci limite en fait ce que le compilateur peut faire comme optimisations. L’exemple cité couramment est celui de l’aliasing : tu peux avoir deux pointeurs qui pointent vers la même chose en mémoire avec la possibilité d’y lire et d’y écrire. Ça vaut dire que le compilateur ne peut pas toujours par exemple virer une lecture en mémoire et réutiliser ce qui est déjà dans un registre parce qu’il est possible qu’un autre pointeur a écrit entre temps et donc que la valeur dans le registre n’est plus à jour. En théorie, ça veut dire qu’un langage comme Rust qui est beaucoup plus strict sur les programmes qu’il accepte (et donc a plus de propriétés à utiliser pour pouvoir faire des optimisations valides) pourrait produire du code machine de meilleur qualité que C. En pratique, ce n’est en général pas encore le cas à cause de la maturité des compilateurs C, et aussi à cause du fait que LLVM (par exemple) ne sait pas encore exploiter ces propriétés comme il n’y a pas vraiment eu de langages répandus qui pouvaient les garantir avant. Ça s’améliore mais c’est pas encore parfait, il y a souvent des optimisations LLVM (comme l’opti noalias que je mentionne précédemment) qui sont désactivées ou réactivées par défaut dans les versions de Rust selon le degré de confiance que LLVM fait bien la bonne chose derrière.

adri1

Pour l'aliasing, ce qui est ironique, c’est qu’en fait les compilateurs peuvent depuis longtemps l’ignorer pour la plus grande partie via la règle de strict aliasing (deux pointeurs vers des objets de types différents sont supposés référencer des objets différents). Cependant, cette règle est souvent désactivée parce que considérée comme casse gueule (le noyau Linux désactive l’option par défaut, par exemple).

+1 -2

Non, c’est en fait complètement différent. Le rapprochement entre les deux vient seulement du fait que C n’est même pas typesafe, mais en fait les deux n’ont rien à voir.

+0 -0

@adri1 Tu peux développer ? Parce que je ne vois pas en quoi cela remet en cause ce que je dis, les deux assertions sont correctes : le typage du C est laxiste et les compilateurs disposent (entre autres) de la règle de strict aliasing pour leur permettre d’effectuer des optimisations, mais cette règle est souvent désactivée.

+0 -0

Dans un cas (le strict aliasing de C), le compilateur voit deux pointeurs et il sait qu’ils ne pointent pas vers la même chose. Dans l’autre cas, le compilateur voit un seul &mut T et il sait que rien d’autre ne pointe vers la même chose. Le premier cas est beaucoup plus restreint que le second, et ne vient en fait qu’en sparadrap par dessus le système de type de C pour pouvoir résoudre quelque cas simples d’aliasing.

Quand je dis que les deux n’ont rien à voir, c’est parce que tu sembles prétendre le contraire ici :

Pour l’aliasing, ce qui est ironique, c’est qu’en fait les compilateurs peuvent depuis longtemps l’ignorer pour la plus grande partie via la règle de strict aliasing

Le strict aliasing de C est un sous-ensemble minuscule des problèmes d’aliasing en général (et en plus il se casse complètement la gueule en pratique donc est inutilisable, ce qui fait que les implémentations sont pas forcément hyper-éprouvées et ça se ressent dans LLVM aujourd’hui quand on essaie de lui filer du code avec des contraintes fortes).

+0 -0

Dans un cas (le strict aliasing de C), le compilateur voit deux pointeurs et il sait qu’ils ne pointent pas vers la même chose. Dans l’autre cas, le compilateur voit un seul &mut T et il sait que rien d’autre ne pointe vers la même chose. Le premier cas est beaucoup plus restreint que le second, et ne vient en fait qu’en sparadrap par dessus le système de type de C pour pouvoir résoudre quelque cas simples d’aliasing.

adri1

Ok, je vois, il y a mécompréhension : mon propos ne concernait que le C, pas le Rust, j’aurais dû préciser vu que tu parlais aussi de Rust dans le passage que je cite plus haut.

Le strict aliasing de C est un sous-ensemble minuscule des problèmes d’aliasing en général (et en plus il se casse complètement la gueule en pratique donc est inutilisable, ce qui fait que les implémentations sont pas forcément hyper-éprouvées et ça se ressent dans LLVM aujourd’hui quand on essaie de lui filer du code avec des contraintes fortes).

adri1

C’est effectivement un sous-ensemble du problème, minuscule c’est assez abusif. Il est fréquent d’avoir des pointeurs vers des types différents. Cela ne couvre bien évidemment pas tout, c’est pour cela que le qualificateur restrict est apparu, mais cela reste une bonne base de mon point de vue.

Pour le côté casse gueule de la règle, il vient à mon sens bien plus de l’emploi qui est fait du C que d’autre chose. Je veux dire, les casts de pointeurs dans tous les sens sans respecter la norme, c’est malheureusement assez fréquent.

+0 -0

C’est effectivement un sous-ensemble du problème, minuscule c’est assez abusif. Il est fréquent d’avoir des pointeurs vers des types différents.

On notera qu’avoir deux pointeurs vers des types différents ne permet au compilateur que de dire que ces deux pointeurs ne pointent pas vers la même chose, pas que ces pointeurs eux-mêmes sont uniques (ce qui est quand même le fond de la question de l’aliasing !). Ajoute un troisième pointeur dans le mix vers un des deux types (que tu auras probablement dans n’importe quelle fonction non triviale), et c’est déjà foutu. On voit alors tout de suite que même dans ce cas favorable au strict aliasing, le strict aliasing est plutôt faible.

Pour le côté casse gueule de la règle, il vient à mon sens bien plus de l’emploi qui est fait du C que d’autre chose. Je veux dire, les casts de pointeurs dans tous les sens sans respecter la norme, c’est malheureusement assez fréquent.

Oui enfin, le fond du problème est surtout que C rend le développeur responsable de conserver des tonnes d’invariants qui sont impossibles à garder en tête. Patcher les problèmes du système de type via l’ajout d’un UB à une liste déjà trop longue n’améliore pas les choses. Si même les développeurs Linux qui sont loin d’être des amateurs préfèrent ne pas ouvrir la porte à des UB supplémentaires, c’est bien que c’est le design même de la règle qui est à mettre en cause.

+0 -0

En l’occurrence, on retrouve ce même problème de l’aliasing en vérification. La solution qui semble par ailleurs la plus utilisée pour aider les outils de vérification, c’est justement de supposer bien plus de séparation que ce que permettrait normalement le langage C, et ensuite seulement s’assurer que ce que l’on a supposé est vrai. Dans la réalité, la plupart des pointeurs même sur des types équivalents pointent sur des choses différentes parce qu’on est des développeurs avec un très petit cerveau et donc c’est plus simple d’avoir une supposition de la forme "si les pointeurs sont différents, c’est des mémoires différentes". Ça aide à raisonner. Malheureusement, avec le fonctionnement de C, ça n’aide absolument pas le compilateur qui ne peut pas faire cette supposition.

Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte