Ce notebook est facultatif et destiné à ceux qui souhaitent aller au-delà du matériel de cours
Les langages de programmation sont couramment classés comme compilés ou interprétés.
Un langage compilé utilise un compilateur pour transformer le code d'entrée en un programme (code machine) qui est exécuté par un ordinateur. Le code machine est l'ensemble d'instructions qu'un ordinateur doit exécuter dans la langue native des CPU d'ordinateurs ( un jeu d'instructions). Ce n'est pas lisible par l'homme. Le compilateur traite généralement l'intégralité du programme, le transformant en une séquence d'étapes en code machine.
Les langages compilés courants incluent C, C ++ et Rust.
Un langage interprété traite les instructions du programme au fur et à mesure qu'elles sont rencontrées (ligne par ligne) plutôt que de traiter le programme entier en code machine à l'avance.
Python est un langage interprété (comme R, Julia et Matlab).
Les langages compilés mènent à des programmes qui sont généralement plus rapides que les programmes interprétés, bien que les implémentations en langage interprété soient aujourd'hui assez rapides. Les programmes compilés peuvent avoir une empreinte plus petite, ce qui peut être important pour les périphériques embarqués et d'autres plates-formes à capacité limitée. L'ordinateur sur lequel un programme compilé s'exécute n'a pas besoin d'avoir un compilateur ou un interpréteur installé.
Lorsqu'un compilateur traduit du code en programme exécutable, il effectuera généralement des vérifications et effectuera des optimisations (analyse statique). Le compilateur vérifie la syntaxe valide et les optimisations sophistiquées peuvent effectuer une transformation de code pour accélérer les programmes. Les langages interprétés sont généralement plus simples à développer et plus interactifs et évitent le besoin d'une étape de compilation. Les langages interprétés sont souvent typées dynamiquement via l'interpréteur en déduisant les types, par ex. entiers contre flottants. Avec les langages compilés, les types sont généralement fixés au moment de la compilation.
La différence entre les langages interprétés et compilés n'est pas aussi claire qu'elle l'était autrefois, les langages interprétés utilisant maintenant souvent la compilation juste à temps.
Nous allons explorer l'impact du code compilé en utilisant Numba, un compilateur juste à temps pour Python. Pour les fonctions spécifiques que nous marquons, Numba peut compiler le code et appliquer des optimisations de performances typiques des langages compilés dans le but de rendre les fonctions plus rapides.
Nous utiliserons plus tard Numba, donc nous pouvons l'installer maintenant.
!conda install numba
Nous considérons ici le problème suivant: calculer le produit scalaire d'un vecteur avec lui-même, $\boldsymbol{x} \cdot \boldsymbol{x}$, en utilisant notre propre fonction Python et en utilisant NumPy:
import numpy as np
import random
def compute_norm2(x):
norm2 = 0.0
for xi in x:
norm2 += xi*xi
return norm2
x = np.random.rand(10000000)
%time n0 = compute_norm2(x)
%time n1 = np.dot(x, x)
Comme prévu, le code NumPy est plus rapide de plusieurs ordres de grandeur. NumPy utilise en fait du code compilé pour le calcul, ce qui explique pourquoi il est beaucoup plus rapide que notre implémentation pure Python.
Nous apportons maintenant un petit changement et ajoutons le décorateur @numba.jit à notre fonction. Cela demande à Numba de transformer notre fonction en une fonction / programme compilé.
import numba
@numba.jit(nopython=True)
def compute_norm2(x):
norm2 = 0.0
for xi in x:
norm2 += xi*xi
return norm2
x = np.random.rand(10000000)
compute_norm2(x)
%time n0 = compute_norm2(x)
%time n1 = np.dot(x, x)
Noter que nous appelons compute_norm2 deux fois et ne chronométrons que le deuxième appel. Nous voulons mesurer le coût brut du calcul et non la petite surcharge de compilation juste à temps (jit) Numba qui est effectuée la première fois qu'une fonction est traitée.
La version Numba est beaucoup plus rapide que la version pure Python. NumPy peut être à nouveau plus rapide pour cette opération, mais relativement proche de Numba. Cela est probablement dû au fait que NumPy utilise un BLAS hautement optimisé (Basic Linear Algebra Subprograms).
Nous pouvons explorer la différence que la compilation pourrait apporter à notre implémentation. Pour commencer, nous reproduisons l'implémentation pure quicksort Python:
def partition_ref(A, lo, hi):
"Partitioning function for use in quicksort"
pivot = A[hi]
i = lo
for j in range(lo, hi):
if A[j] <= pivot:
A[i], A[j] = A[j], A[i]
i += 1
A[i], A[hi] = A[hi], A[i]
return i
def quicksort_ref(A, lo=0, hi=None):
"Sort A and return sorted array"
# Initialise data the first time function is called
if hi is None:
A = A.copy()
hi = len(A) - 1
# Sort
if lo < hi:
p = partition_ref(A, lo, hi)
quicksort_ref(A, lo, p - 1)
quicksort_ref(A, p + 1, hi)
return A
Nous introduisons maintenant une version annotée avec un décorateur Numba:
@numba.jit(nopython=True)
def partition_jit(A, lo, hi):
"Partitioning function for use in quicksort"
pivot = A[hi]
i = lo
for j in range(lo, hi):
if A[j] <= pivot:
A[i], A[j] = A[j], A[i]
i += 1
A[i], A[hi] = A[hi], A[i]
return i
@numba.jit(nopython=True)
def quicksort_jit(A, lo=0, hi=-1):
"Sort A and return sorted array"
# Initialise data the first time function is called
if hi == -1:
A = A.copy()
hi = len(A) - 1
# Sort
if lo < hi:
p = partition_jit(A, lo, hi)
quicksort_jit(A, lo, p - 1)
quicksort_jit(A, p + 1, hi)
return A
Le dernier argument de quicksort_jit a été légèrement modifié pour que le type d'argument ne change pas (les types d'argument qui changent sont problématiques pour un compilateur car il a besoin de savoir à l'avance pour quels types générer du code machine).
Nous pouvons maintenant chronométrer notre implémentation pure Python, l'implémentation compilée par Numba et la fonction de tri intégrée. Comme précédemment, nous appellerons quicksort_jit une fois avant le timing pour éliminer le coût de la compilation juste-à-temps.
data = np.random.rand(500000)
# Time the pure Python implementation
%time x = quicksort_ref(data)
# Time the Numba implementation
quicksort_jit(data)
%time x = quicksort_jit(data)
# Time the built-in implementation
%time x = np.sort(data, kind='quicksort')
L'implémentation pure Python est clairement la plus lente. L'implémentation via Numba et l'implémentation intégrée sont relativement proches dans le temps. Noter que l'implémentation Numba est pratiquement une traduction directe de l'implémentation Python pure et n'a pas été soigneusement optimisée.