Fait des manipulations de vecteurs et de matrices en Octave et en C et tu vas vite comprendre.
Tout ce que tu peut faire en Octave peut être fait en C bien sur, mais de manière bien plus complexe. L'avantage de Octave est que la notation est beaucoup plus proche des formules mathématiques que l'on écrit et est beaucoup plus concise. Elle donc bien plus facilement vérifiable.
Un exemple tout con, j'ai un décodage de Viterbi à un moment, une des opérations nécessaire consiste à prendre une matrice et pour chaque ligne, chercher la plus grande valeur. Il faut stocker pour chaque lignes, la valeur maximale et son indice.
En Octave, cela ce code val, idx = max(M') M étant la matrice en question, que l'on transpose et sur laquelle on appelle la fonction max. Elle retourne le vecteur val qui contient les valeurs maximales, et le vecteur idx qui contient les indices.
Maintenant en C, c'est beaucoup moins trivial. Bien sur, on peut utiliser des libs toutes faites, mais cela implique de stocker dde nombreuse valeurs intermédiaires, ce qui n'est pas possible dans notre cas vu la taille de tout ces éléments.
Il faut donc coder tout cela avec des boucles, en tenant compte du fait que les matrices sont stocker en column-major (car de manière globale pour les calculs que l'on fait, c'est l'ordre le plus pratique.
Donc pour éviter d'avoir des cache-miss en permanence il faut travail dans un ordre qui n'est pas spécialement logique, c'est-à-dire que l'on ne calcul pas le max d'une ligne puis le suivant, mais toutes les lignes en même temps. Ça permet d'avoir des patterns d'accès mémoire très prévisibles par le processeur et presque aucun cache-miss.
La version en Octave n'est absolument pas optimisée et construit explicitement en mémoire de nombreuses matrices intermédiaires et donc, est lente à mourir car, dès que les données deviennent un peu importantes, elle swap énormément.
Mais par contre, le code est très simple et parfaitement lisible car très proche de la description mathématique de l'algo et donc très facilement vérifiable.
La version en C est prévue pour stocker complètement aucune matrices intermédiaire, ce qui implique de travailler par blocs, donc des niveaux de boucles supplémentaire et du code pour gérer les limites entre blocs.
Donc cela donne très rapidement un code beaucoup plus dur à comprendre, mais plusieurs ordres de grandeurs plus rapide.
Pour donner une idée, la version octave ne peut gérer de manière réaliste des modèle de plus de 100000 éléments, là ou la version en C est encore loin de ses limites avec un modèle de 1.3 milliard d'éléments.
La version en Octave permet de valider l'algorithme et d'obtenir une implémentation de référence. Celle est C permet de travailler sur des données réelles dans des condition correcte avec des temps de calculs raisonnables.
Le code en C à été relu de nombreuse fois et possède de nombreuses vérifications, mais ce n'est pas suffisant pour être sur de sa validité. Ce genre de code est à peu près impossible à prouver, le meilleur outils que l'on a pour l'instant pour être à peu près sûr qu'il fait ce que l'on pense c'est de vérifier qu'il donne les même résultats qu'une autre implémentation indépendante qu'il elle est bien plus facilement vérifiable.
Bien sûr on est loin d'une preuve absolue, mais c'est le mieux que l'on puisse faire pour l'instant et c'est le prix à payer pour pouvoir travailler avec d'aussi gros modèles.
[^] # Re: Surprise
Posté par beagf . En réponse au journal Lisaac: sorti de la 0.39beta. Évalué à 5.
Tout ce que tu peut faire en Octave peut être fait en C bien sur, mais de manière bien plus complexe. L'avantage de Octave est que la notation est beaucoup plus proche des formules mathématiques que l'on écrit et est beaucoup plus concise. Elle donc bien plus facilement vérifiable.
Un exemple tout con, j'ai un décodage de Viterbi à un moment, une des opérations nécessaire consiste à prendre une matrice et pour chaque ligne, chercher la plus grande valeur. Il faut stocker pour chaque lignes, la valeur maximale et son indice.
En Octave, cela ce code
val, idx = max(M')M étant la matrice en question, que l'on transpose et sur laquelle on appelle la fonction max. Elle retourne le vecteur val qui contient les valeurs maximales, et le vecteur idx qui contient les indices.Maintenant en C, c'est beaucoup moins trivial. Bien sur, on peut utiliser des libs toutes faites, mais cela implique de stocker dde nombreuse valeurs intermédiaires, ce qui n'est pas possible dans notre cas vu la taille de tout ces éléments.
Il faut donc coder tout cela avec des boucles, en tenant compte du fait que les matrices sont stocker en column-major (car de manière globale pour les calculs que l'on fait, c'est l'ordre le plus pratique.
Donc pour éviter d'avoir des cache-miss en permanence il faut travail dans un ordre qui n'est pas spécialement logique, c'est-à-dire que l'on ne calcul pas le max d'une ligne puis le suivant, mais toutes les lignes en même temps. Ça permet d'avoir des patterns d'accès mémoire très prévisibles par le processeur et presque aucun cache-miss.
La version en Octave n'est absolument pas optimisée et construit explicitement en mémoire de nombreuses matrices intermédiaires et donc, est lente à mourir car, dès que les données deviennent un peu importantes, elle swap énormément.
Mais par contre, le code est très simple et parfaitement lisible car très proche de la description mathématique de l'algo et donc très facilement vérifiable.
La version en C est prévue pour stocker complètement aucune matrices intermédiaire, ce qui implique de travailler par blocs, donc des niveaux de boucles supplémentaire et du code pour gérer les limites entre blocs.
Donc cela donne très rapidement un code beaucoup plus dur à comprendre, mais plusieurs ordres de grandeurs plus rapide.
Pour donner une idée, la version octave ne peut gérer de manière réaliste des modèle de plus de 100000 éléments, là ou la version en C est encore loin de ses limites avec un modèle de 1.3 milliard d'éléments.
La version en Octave permet de valider l'algorithme et d'obtenir une implémentation de référence. Celle est C permet de travailler sur des données réelles dans des condition correcte avec des temps de calculs raisonnables.
Le code en C à été relu de nombreuse fois et possède de nombreuses vérifications, mais ce n'est pas suffisant pour être sur de sa validité. Ce genre de code est à peu près impossible à prouver, le meilleur outils que l'on a pour l'instant pour être à peu près sûr qu'il fait ce que l'on pense c'est de vérifier qu'il donne les même résultats qu'une autre implémentation indépendante qu'il elle est bien plus facilement vérifiable.
Bien sûr on est loin d'une preuve absolue, mais c'est le mieux que l'on puisse faire pour l'instant et c'est le prix à payer pour pouvoir travailler avec d'aussi gros modèles.