Les listes spécifiques de Numba¶

Numba travaille aisément et efficacement avec des tableaux Numpy. Mais ces derniers, sont, par construction, statiques, leur taille est allouée une bonne fois pour toutes et le tableau n’est pas extensible. Pour les rendre plus dynamiques, Numpy dispose de deux méthodes mais elles sont peu efficaces :

• la méthode append mais elle récrit un nouveau tableau,
• la méthode resize mais elle est écrite en pur Python.

En outre les tableaux Numpy ont le désavantage qu’ils sont formés de sous-tableaux ayant tous la même taille, autrement dit, pas de ragged array qui soit pris en charge sous Numpy.

Depuis sa version 0.45 (juillet 2019), Numba supporte des listes mono-types, extensibles et ayant la même interface que celles de Python. En particulier, les listes emboîtées sont prises en charge ainsi que la méthode append ce qui rend ces listes extensibles. Bien sûr, ces listes sont utilisables en mode nopython. Ces listes sont définies dans une classe List.

Encore en version 0.54 dev (mai 2021), ces listes sont considérées comme expérimentales. Pour l’instant, ces listes sont loin d’avoir l’efficacité des tableaux Numpy ou des vectors du C++. Les performances sont variables, mais dans de nombreuses situations, elles sont plus proches de celles de Python que de celles d’un langage compilé. Toutefois, les performances se sont améliorées depuis la version 0.50 de Numba.

D’après mes expérimentations,

• les listes Numba sont performantes en tant que listes extensibles : la méthode append est efficace
• lorsque la liste doit se comporter aussi comme un vrai tableau, avec accès direct à un item en lecture ou écriture (l’équivalent d’un getitem ou setitem), les performances sont très dégradées, et comparables à celles de Python pur.

Concernant l’absence de ragged array sous Numpy, on notera que le module Awkward Array semble les prendre en charge. Voir en fin de cette page.

Les listes Numba sont implémentées dans trois fichiers :

• containers
• List object in Python
• List object in C

Il y est clairement indiqué que les listes Numba sont, à divers titres, largement inspirées de l’implémentation des listes de CPython.

Listes Numba : exemple basique¶

Les listes de Numba font partie de la classe List, accessible depuis le module typedlist. On notera le L en capitale de List. L’interface est quasiment la même que pour les listes Python. Voici un exemple de quelques utilisations :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

>>> from numba.typed import List
>>> L = List([2024, 2038])
>>> L
ListType[int64]([2024, 2038])
>>> type(L)
<class 'numba.typed.typedlist.List'>
>>> L.append(3000)
>>> L
ListType[int64]([2024, 2038, 3000])
>>> M = List([42, 99])
>>> L.extend(M)
>>> L[-2]
42
>>> L[1]=2025
>>> L
ListType[int64]([2024, 2025, 3000, 42, 99])
>>> L.append(3.14)
Traceback (most recent call last):
...
numba.core.errors.TypingError: Failed in nopython mode pipeline (step: nopython frontend)

• Ligne 4 : On aura noté que, par inférence de type, L est considérée comme une liste d’entiers sur 64 bits.
• Ligne 6 : on n’obtient qu’un type générique
• Ligne 17 : il faut respecter le type des éléments de la liste.

Listes de listes¶

C’est semblable aux listes 2D :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

>>> from numba.typed import List
>>> A=List([42, 99])
>>> B=List([2, 3, 5])
>>> L=List([A, B])
>>> L
ListType[ListType[int64]]([[42, 99], [2, 3, 5]])
>>> L.append(A)
>>> L
ListType[ListType[int64]]([[42, 99], [2, 3, 5], [42, 99]])
>>> L[0][0]=100
>>> L
ListType[ListType[int64]]([[100, 99], [2, 3, 5], [100, 99]])
>>>

• Ligne 4 : création d’une liste de listes

Bien sûr, et c’est tout l’intérêt, les listes Numba fonctionnent en mode nopython :

from numba.typed import List
from numba import njit

@njit
def f():
    L=List([List([42]*5)])
    L.append(List([2030]*4))
    print(L)

f()

qui affiche

[[42, 42, 42, 42, 42], [2030, 2030, 2030, 2030]]

Créer un type de liste¶

On peut avoir besoin d’accéder au type d’une liste. La fonction standard type ne donne qu’un type générique :

from numba.typed import List

L=List([42, 25])
print(type(L))
print(repr(L))

qui affiche

<class 'numba.typed.typedlist.List'>
ListType[int64]([42, 25])

Pour générer un type de liste, on utilise numba.types. Voici un exemple d’utilisation :

1
2
3
4
5
6
7
8
9

from numba.typed import List
from numba.types import ListType
from numba import int64

my_type1=ListType(int64)
print(my_type1)

my_type2=ListType(my_type1)
print(my_type2)

ListType[int64]
ListType[ListType[int64]]

• Lignes 5 et 10 : on créé le type List d’entiers de type int64
• Lignes 8 et 11 : on créé le type List de List d’entiers de type int64

Savoir définir un type de liste est utile quand on a besoin d’une liste vide d’un certain type.

Par ailleurs, partant cette fois d’une liste donnée, je n’ai pas trouvé dans la doc comment accéder à l’objet type de cette liste.

Listes vides¶

Comme les listes de Numba sont typées en mode nopython, le code suivant renvoie une erreur :

1
2
3
4
5
6
7
8
9

from numba.typed import List
from numba import njit

@njit
def f(L):
    return len(L)

L=List([])
f(L)

10
11
12

Traceback (most recent call last):
[... omis ...]
TypeError: invalid operation on untyped list

• Ligne 8 : La liste vide non typée est bien définie en mode object
• Ligne 9 : La liste vide non typée n’est pas utilisable en mode nopython

Il existe donc une méthode de la classe List qui permet de créer une liste vide et de type donné. Il s’agit de la méthode empty_list. Exemple d’utilisation :

1
2
3
4
5
6
7
8
9

from numba.typed import List
from numba import njit, int64

@njit
def f(L):
    return len(L)

L=List.empty_list(int64)
print(f(L))

10

0

• Ligne 8 : on crée une liste Numba d’entiers 64 bits (importé ligne 2) mais vide.
• Lignes 4 et 9 : elle fonctionne en mode nopython
• Ligne 10 : la liste est bien vide.

Les listes vides sont utiles car on peut avoir à en insérer une dans une liste déjà existante. Voici un exemple d’utilisation :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

from numba.typed import List
from numba import njit, int64, types

A=List([42, 25])
B=List.empty_list(int64)
L1=List([A, B])

print("L1 =", L1)

C=List([55, 66, 77])
D=List([33])
L2=List([C, D])

print("L2 =", L2)

L=List([L1, L2])

print("L = [L1, L2] =", L)

empty2d=List.empty_list(types.ListType(int64))
L.append(empty2d)

print("L =", L)

24
25
26
27

L1 = [[42, 25], []]
L2 = [[55, 66, 77], [33]]
L = [L1, L2] = [[[42, 25], []], [[55, 66, 77], [33]]]
L = [[[42, 25], []], [[55, 66, 77], [33]], []]

• Ligne 6 : on crée une liste Numba L1 de listes Numba d’entiers int64 dont une, B, est vide
• Ligne 12 : on crée de même une liste Numba L2 de listes Numba d’entiers int64
• Ligne 16 : on rassemble L1 et L2 dans une liste 3d appelé L
• Ligne 21 : on rajoute à L la liste vide du bon type.

Liste de tableaux Numpy¶

On peut créer une liste de tableaux Numpy, pas forcément de même taille, par exemple (ligne 13 ci-dessous) :

import numpy as np
from numba.typed import List
from numba import njit

@njit
def f(L):
    s=0
    for i in range(len(L)):
        s+=L[i][0]
    return s

LL=[[42,81], [42,81, 51, 29], [4]]
L=List(map(np.array, LL))

print(f(L))

qui affiche

88

Performance des listes Numba : la méthode append¶

Le programme ci-dessous détermine la liste des N premiers nombres premiers (l’algorithme implémenté est mathématiquement peu efficace mais ce n’est pas le propos ici). On va comparer les performances d’une fonction utilisant une liste Python et d’une fonction utilisant une liste Numba :

from time import  perf_counter
import numpy as np
from numba import njit, int64
from numba.typed import List

def primes(N):
    P=[]
    n = 2
    while len(P) < N:
        for p in P:
            if n % p == 0:
                break
        else:
            P.append(n)
        n += 1

    return P

@njit
def primes_nb(N):
    P=List.empty_list(int64)
    n = 2
    while len(P) < N:
        for p in P:
            if n % p == 0:
                break
        else:
            P.append(n)
        n += 1

    return P

N=40000

print("Testing with Numba List ...")

# Numba compilation warmup
primes_nb(2)

begin_perf=perf_counter()

PP=primes_nb(N)

nb_perf=perf_counter()-begin_perf
print("Numba List: %.2fs\n" %nb_perf)


print("Testing with Python list ...")
begin_perf=perf_counter()

P=(primes(N))

py_perf=perf_counter()-begin_perf
print("Python list: %.2fs" %py_perf)


ratio=py_perf/nb_perf
print("%.2f" %ratio)

print(P==[int(z) for z in PP])

qui affiche

Testing with Numba List ...
Numba List: 4.83s

Testing with Python list ...
Python list: 33.94s
7.03
True

L’amélioration semble seulement substantielle. En fait, elle est remarquable, car exactement le même programme écrit avec des vectors du C++ est moins rapide, sur ma machine, il met 6.3s.

Performance des listes Numba : le tri par sélection¶

Le programme ci-dessous implémente un tri par sélection et l’applique à une liste de 20000 entiers en comparant les performances des listes Numba par rapport aux listes Python :

from time import perf_counter
from random import randrange
from numba import njit, __version__
from numba.typed import List

def selection(L):
    n=len(L)
    for i in range(n-1):
        jMin=i
        mini=L[i]
        for j in range(i+1, n):
            if L[j] < mini:
                jMin=j
                mini=L[j]
        if mini!=L[i]:
            L[i], L[jMin]= L[jMin], L[i]

print("Numba version :", __version__, end='\n\n')

N=20000
# ------------ Data Python -----------------------

begin_perf = perf_counter()

L=[randrange(10**6) for _ in range(N)]

delta = perf_counter() - begin_perf

print(f"Generation : {delta:.2f}s")


# ------------Numba copy -----------------------

begin_perf = perf_counter()

LL=List(L)

delta = perf_counter() - begin_perf

print(f"Numba Copy : {delta:.2f}s")



# ------------ Python -----------------------
print("Sorting ...")

begin_perf = perf_counter()

selection(L)

delta_py = perf_counter() - begin_perf

print(f"Python list: {delta_py:.2f}s")



# ------------ Numba + List -----------------------
selection_nb_List=njit(selection)

# warmup
selection_nb_List(List([42]))

print("Sorting ...")

begin_perf = perf_counter()

selection_nb_List(LL)

delta_nb_List = perf_counter() - begin_perf

print(f"Numba List: {delta_nb_List:.2f}s")

# -----------------------------------

print(f"ratio : {delta_py/delta_nb_List:.1f}")

print(L==list(LL))

Numba version : 0.53.1

Generation : 0.01s
Numba Copy : 0.31s
Sorting ...
Python list: 8.08s
Sorting ...
Numba List: 2.91s
ratio : 2.8
True

On voit que l’amélioration apportée par les listes Numba est modeste, d’un facteur 2,8 mais il s’est amélioré depuis la version 0.50 de Numba où le ratio était de 1,3. On pourra noter que le coût de la transformation de la liste Python en liste Numba n’a pas été pris en compte.

En comparaison, on avait vu que Numba traitait la même liste mais récrite en tableau Numpy avec une performance améliorée d’un facteur 36.

Performance des listes Numba : listes d’adjacence¶

Ce qui suit ne nécessite aucune connaissance en théorie des graphes.

On donne un entier n et une liste de \(\mathtt{m}\) arcs d’un graphe orienté de sommets \(\mathtt{0, 1, ..., n-1}\). On veut créer la liste d’adjacence de ce graphe, c’est-à-dire la liste des listes des voisins de chaque sommets.

Par exemple, si \(\mathtt{n=4}\) et \(\mathtt{m=9}\), et si la liste des 9 arcs est :

(1, 2)
(1, 0)
(3, 1)
(1, 4)
(2, 1)
(2, 3)
(4, 3)
(0, 3)
(4, 1)

la liste d’adjacence est vue comme :

0: 3
1: 2 0 4
2: 1 3
3: 1
4: 3 1

ou encore L=[[3], [2, 0, 4], [1, 3], [1], [3, 1]].

Pour effectuer les tests qui suivent, on génère une liste aléatoire d’arcs dans un fichier texte. Pour le graphe ci-dessus, le fichier serait :

5
9
1 2
1 0
3 1
1 4
2 1
2 3
4 3
0 3
4 1

Syntaxe du fichier :

• Première ligne : la valeur de \(\mathtt{n}\)
• Deuxième ligne : la valeur de \(\mathtt{m}\)
• Les m lignes suivantes : un arc, formé de deux entiers, l’origine et l’extrémité de l’arc.

Pour le test, un fichier pour les valeurs \(\mathtt{n=10 000}\) et \(\mathtt{m=6 000 000}\) sera utilisé.

L’objectif est donc de faire la transformation suivante :

• objet initial : une liste de listes de deux entiers
• objet final : une liste de \(\mathtt{n}\) listes de longueurs variables.

Voici le code et le résultat de son exécution :

from time import perf_counter
import numpy as np
from numba.typed import List
from numba import njit, int64, types, __version__

def edges2adj(edges, n):
    adj=[[] for _ in range(n)]
    for u,v in edges:
        adj[u].append(v)
    return adj

LIST_int64=types.ListType(int64)

@njit
def edges2adj_nb(edges, n):
    adj=List.empty_list(LIST_int64)
    for i in range(n):
        adj.append(List.empty_list(int64))

    for u,v in edges:
        adj[u].append(v)
    return adj

def capture():
    n=int(input())
    m=int(input())
    return n, [tuple(map(int, input().split())) for _ in range(m)]

print("Numba version : %s" %__version__)

print("Building dataset...")

begin_perf = perf_counter()

n, edges=capture()

delta = perf_counter() - begin_perf

print(f"Dataset: {delta:.2f}s\n")

# --------- Python ----------------


print("Python building adj ...")

begin_perf = perf_counter()

adj=edges2adj(edges, n)

delta_py = perf_counter() - begin_perf

print(f"Python : {delta_py:.2f}s\n")


# --------- Numba ----------------
# warmup
edges2adj_nb(List({(0, 1), (1, 0)}), 2)

print("Numba building List ...")

begin_perf = perf_counter()

edges_nb=List(edges)

delta = perf_counter() - begin_perf

print(f"List : {delta:.2f}s\n")


print("Numba building adj ...")

begin_perf = perf_counter()

adj_nb=edges2adj_nb(edges_nb, n)

delta_nb = perf_counter() - begin_perf

print(f"Numba : {delta_nb:.2f}s")

print(f"ratio : {delta_py/delta_nb:.1f}")

Numba version : 0.53.1
Building dataset...
Dataset: 10.34s

Python building adj ...
Python : 0.95s

Numba building List ...
List : 8.45s

Numba building adj ...
Numba : 0.42s
ratio : 2.2

Pour donner une idée, en C++, sur la même machine, l’opération de conversion dure 0.13s.

Le code précédent est lancé avec la commande suivante :

$ python3 adj_from_file.py < test_10000_600000.txt

où test_10000_600000.txt est le nom du fichier de test.

Le fichier des arêtes est généré par le code Python suivant :

from random import randrange

def maketest(n, m):
    edges=set([])
    while len(edges)<m:
        u=randrange(n)
        v=randrange(n)
        if u!=v:
            edges.add((u, v))
    return edges

n=10000
m=6000000

edges=maketest(n, m)
print(n)
print(m)
for u,v in edges:
    print(u, v)

puis par la ligne de commande :

python3 maketest.py > test_10000_600000.txt

Cet exemple montre que les listes de Numba n’apportent qu’une modeste amélioration des performances par rapport à leur équivalent Python (ratio de 2,2) mais en amélioration depuis la version 0.50 de Numba (ratio de 1,5). Sans compter le coût très important de la conversion.

Dans le cas présent d’une construction d’une liste d’adjacence, Numba pourrait obtenir d’excellentes performances en plaçant le contenu de chaque liste d’adjacence dans un tableau Numpy T d’entiers et que l’on couplerait à une 2e tableau d’offsets de n entiers qui indiquerait le début de chaque liste d’adjacence dans la liste T. Mais avec l’inconvénient majeur que les listes d’adjacence seraient statiques.

Performances des dictionnaires Python¶

CPython utilise en interne et pour l’interpréteur lui-même une table de hachage. Quand vous utilisez un dictionnaire dans un code Python, c’est en fait cette table de hachage qui est appelée.

Pour pouvoir comparer les dictionnaires Python aux dictionnaires de Numba, se pose la question des performances de cette table de hachage.

L’analyse des performances est toujours très délicate, de nombreux facteurs peuvent entrer en jeu comme le choix de la fonction de hachage, la gestion de la mémoire et les fonctionnalités offertes. Une même table peut présenter des performances variables selon le type d’épreuve qu’elle va effectuer (insertion et le type d’insertion, suppression de clés, lecture, écriture, parcours de la table, nature et taille des clés). En plus de cela, de nombreux benchmarks présentent des épreuves très simplifiées.

Les benchmarks de dictionnaires Python utilisés depuis l’API C de Python sont assez rares. En voici deux assez anciens :

• incise.org de 2010, qui n’est plus accessible en ligne et web-archivé,
• preshing de 2011.

Les résultats ne sont pas facilement interprétables. Mais grosso modo, il semble ressortir que, du point de vue de la vitesse d’exécution, les résultats des dictionnaires Python sont acceptables voire corrects mais sans être excellents.

En juillet 2018, J. P. Hansson a proposé des benchmarks assez variés. Sur les graphiques, il semble apparaître que :

• la table de hachage de Python et de la STL du C++ ont des performances comparables mais celles de Python sont peut-être un peu en retrait (vitesse et consommation mémoire) ;
• les performances de la table de Python sont nettement dans la 2e moitié du classement.

Par ailleurs, de nombreux benchmarks, par exemple

• Attractive Chaos en septembre 2018
• Martin Ankerl en avril 2019

semblent montrer que la table de hachage de la STL du C++ a de très mauvaises performances, et cela s’explique assez bien par son implémentation par chaînage (imposée par le standard ISO).

De tout cela, il semble ressortir que la table de hachage de CPython, bien qu’implémentant la technique efficace de l’adressage ouvert à sondage linéaire (linear probing) et bien qu’optimisée, a des performances plutôt moyennes par rapport à d’autres tables de hachage généralistes, implémentées en C ou C++ et largement diffusées.

Noter que les deux fichiers sources de l’implémentation de Numba pour son dictionnaire dictobject.h et dictobject.c reprennent intégralement et adaptent l’implémentation de la table de hachage de CPython.

Je comparerai ici les performances des dictionnaires Numba à son équivalent dans la STL du C++, à savoir unordered_map.

Les dictionnaires de Numba¶

Depuis sa version 0.44, Numba met à disposition un dictionnaire en mode nopython. L’usage est très proche de celui des dictionnaires Python. Ci-dessous, je présente des exemples simples et je fais des micro-benchmarks pour comparer avec les dictionnaires de Python.

from time import perf_counter
from random import shuffle
from numba.typed import Dict, List
from numba import njit, __version__


def f(L):
    d={}
    for k in L:
        d[k]=k
    return d

@njit
def g(L):
    d=Dict()
    for k in L:
        d[k]=k
    return d


print("Numba version : %s" %__version__)

n=3*10**6

begin_perf = perf_counter()

L=list(range(n))
shuffle(L)

delta_py = perf_counter() - begin_perf

print(f"shuffle : {delta_py:.2f}s")

# ------------- Python -------------

begin_perf = perf_counter()

f(L)

delta_py = perf_counter() - begin_perf

print(f"Python : {delta_py:.2f}s")


# ------------- Numba -------------

g(List([5]))

L=List(L)

begin_perf = perf_counter()

g(L)

delta_nb= perf_counter() - begin_perf

print(f"Numba : {delta_nb:.2f}s")

print(f"ratio : {delta_py/delta_nb:.1f}")

Numba version : 0.53.1
shuffle : 1.97s
Python : 0.72s
Numba : 0.47s
ratio : 1.5

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

from time import perf_counter
from random import shuffle
import numpy as np
from numba import njit
from numba.typed import Dict, List

def f(d):
    n=len(d)
    s=0
    for k in d:
        s+=d[k]
    return s

@njit
def g(d):
    n=len(d)
    s=0
    for k in d:
        s+=d[k]
    return s

n=10**6


print("Generating data ...")
begin_perf = perf_counter()

L=list(range(n+1))
shuffle(L)

D=Dict()
for k in L:
    D[k]=k


d=dict(D)

delta_py = perf_counter() - begin_perf

print(f"Data: {delta_py:.2f}s")

# ------------- Python -------------

begin_perf = perf_counter()

s1=f(L)

delta_py = perf_counter() - begin_perf

print(f"Python : {delta_py:.2f}s")


# ------------- Numba -------------

DD=Dict()
DD[5]=5
g(DD)

begin_perf = perf_counter()

s2=g(D)

delta_nb = perf_counter() - begin_perf

print(f"Numba : {delta_nb:.2f}s")

# check
print(s1 == s2)

from numba import __version__
print("Numba version :", __version__)
print(f"ratio : {delta_py/delta_nb:.1f}")

73
74
75
76
77
78
79

Generating data ...
Data: 4.88s
Python : 0.23s
Numba : 0.03s
True
Numba version : 0.53.1
ratio : 7.0

Dictionnaire de dictionnaires¶

Il est possible de définir des dictionnaires de dictionnaires de type spécifique à Numba. Ci-dessous, voici un code qui marche en mode objet mais pas en mode nopython.

from numba import njit, int64, types
from numba.typed import Dict

@njit
def f():
    Dict.empty(int64, int64)
    print("f is OK")

def g():
    Dict.empty(int64, types.DictType(int64, int64))
    print("g is OK")

@njit
def h():
    Dict.empty(int64, types.DictType(int64, int64))
    print("h is OK")

f()
g()
h()

Il renvoie un long message d’erreur dont voici un extrait :

$ python dict_dict.py
f is OK
g is OK
Traceback (most recent call last):

... omis ...


There are 2 candidate implementations:

... omis ...

def h():
    Dict.empty(int64, types.DictType(int64, int64))
    ^

On dirait que le type des valeurs du dictionnaire doit être connu à la compilation. On peut y pallier avec les codes suivants mais on y perd en souplesse.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110

from time import perf_counter
from random import randrange
from numba import njit, int64, types
import numpy as np
from numba.typed import Dict, List


def product_direct(A, B):
    n, p=len(A), len(A[0])
    q=len(B[0])

    P=[[0]*q for _ in range(n)]
    for i in range(n):
        for j in range(q):
            for k in range(p):
                P[i][j]+=A[i][k]*B[k][j]
    return P

def square_py(d):
    n=len(d)
    P={i:{j:0 for j in range(n)} for i in range(n)}
    for i in range(n):
        for j in range(n):
            for k in range(n):
                P[i][j]+=d[i][k]*d[k][j]
    return P


INT64_TO_INT64=types.DictType(int64, int64)

@njit
def square_nb(D):
    n=len(D)
    P=Dict.empty(int64,INT64_TO_INT64)
    for i in range(n):
        P[i]=Dict.empty(int64, int64)
        for j in range(n):
            P[i][j]=0
    for i in range(n):
        for j in range(n):
            for k in range(n):
                P[i][j]+=D[i][k]*D[k][j]
    return P



def build_matrices(n):
    M=[[randrange(2) for _ in range(n)] for _ in range(n)]
    d={}
    D=Dict.empty(int64, types.DictType(int64, int64))
    for i in range(n):
        d[i]={}
        D[i]=Dict.empty(int64,int64)
        for j in range(n):
            d[i][j]=D[i][j]=M[i][j]
    return d, D, M


n=400
d, D, A=build_matrices(n)


begin_perf = perf_counter()

PP=product_direct(A, A)

delta = perf_counter() - begin_perf

print(f"Python list : {delta :.2f}s")

# -------------------------------------------

begin_perf = perf_counter()


P=square_py(d)

delta_py = perf_counter() - begin_perf

print(f"Python dict : {delta_py :.2f}s")

# -------------------------------------------
# warmup
DD=Dict.empty(int64, types.DictType(int64, int64))
dd=Dict.empty(int64,int64)
dd[0]=0
DD[0]=dd
square_nb(DD)


begin_perf = perf_counter()


PPP=square_nb(D)

delta_nb = perf_counter() - begin_perf

print(f"Numba Dict : {delta_nb :.2f}s")

# -------------------------------------------


print([P[i][j] for i in range(n) for j in range(n)]==
      [PP[i][j] for i in range(n) for j in range(n)]==
      [PPP[i][j] for i in range(n) for j in range(n)])

from numba import __version__
print("Numba version : %s" %__version__)

print(f"ratio : {delta_py/delta_nb:.1f}")

1
2
3
4
5
6

Python list : 8.00s
Python dict : 15.08s
Numba Dict : 9.23s
True
Numba version : 0.53.1
ratio : 1.6

from time import perf_counter
from random import randrange
from numba import njit, int64, types
import numpy as np
from numba.typed import Dict


def build_py(M):
    n=len(M)
    return {i:{j:M[i][j] for j in range(n)} for i in range(n)}


INT64_TO_INT64=types.DictType(int64, int64)

@njit
def build_nb(M):
    n=len(M)
    D=Dict.empty(int64,INT64_TO_INT64)
    for i in range(n):
        D[i]=Dict.empty(int64, int64)
        for j in range(n):
            D[i][j]=M[i][j]
    return D


n=3000

begin_perf = perf_counter()

M=[[randrange(2) for _ in range(n)] for _ in range(n)]

delta = perf_counter() - begin_perf

print(f"Data Python : {delta :.2f}s")

begin_perf = perf_counter()

MM=np.array(M)



delta = perf_counter() - begin_perf

print(f"Data Numba: {delta :.2f}s")


# -------------------------------------------

begin_perf = perf_counter()

d=build_py(M)


delta_py = perf_counter() - begin_perf

print(f"Python dict : {delta_py :.2f}s")

# -------------------------------------------
# warmup
build_nb(np.array([[randrange(2) for _ in range(1)] for _ in range(1)]))


begin_perf = perf_counter()

D=build_nb(MM)

delta_nb = perf_counter() - begin_perf

print(f"Numba Dict : {delta_nb :.2f}s")

# -------------------------------------------

print(dict(D)==d)

from numba import __version__
print("Numba version : %s" %__version__)

print(f"ratio : {delta_py/delta_nb:.1f}")

Data Python : 5.91s
Data Numba: 0.50s
Python dict : 0.77s
Numba Dict : 0.56s
True
Numba version : 0.53.1
ratio : 1.4

Prise en charge de heapq¶

Depuis Numba 0.43, une prise en charge de la structure de données heapq de Python est assurée en mode nopython (rappel : le module heapq implémente une file de priorité).

L’usage est similaire à l’usage en Python pur. Les éléments de la file doivent être tous du même type et il faut que Numba puisse inférer ce type.

Voici un exemple qui va comparer les performances de heapq en Numba et en Python pur. Le test consiste à remplir une file de priorité depuis une liste aléatoire (Numba ou Python) d’un million d’entiers par alternance des opérations suivantes :

• 20 insertions
• 5 supressions

Une fois le contenu de la liste complètement placé dans la file, on vide un par un les éléments de la file.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

from time import perf_counter
from heapq import heappush, heappop
from random import shuffle
from numba import njit, int64
from numba.typed import List


def f(L):
    n=len(L)
    H=[]
    i=0
    while i<n:
        for j in range(10):
            heappush(H, L[i])
            heappush(H, L[i])
            i+=1
        for j in range(5):
            heappop(H)
    while H:
        heappop(H)

@njit
def g(L):
    n=len(L)
    H=[0]
    H.pop()
    i=0
    while i<n:
        for j in range(10):
            heappush(H, L[i])
            heappush(H, L[i])
            i+=1
        for j in range(5):
            heappop(H)
    while H:
        heappop(H)


L=list(range(10**6))
shuffle(L)

# -------------- Python --------------------

begin_perf = perf_counter()


f(L)

delta_py = perf_counter() - begin_perf

print(f"Python : {delta_py:.2f}s")

# -------------- Numba --------------------
L=List(L)


#warmup
g(List(range(20)))


begin_perf = perf_counter()


g(L)

delta_nb = perf_counter() - begin_perf

print(f"Numba : {delta_nb:.2f}s")

from numba import __version__
print("Numba version : %s" %__version__)

print(f"ratio : {delta_py/delta_nb:.1f}")

qui affiche

Python : 1.72s
Numba : 0.43s
Numba version : 0.53.1
ratio : 4.0

L’amélioration est nette et est en progrès par rapport à la version 0,50 où le ratio était de 3. En C++ avec la STL, un code équivalent s’exécute 0.25s.

Quelques commentaires de code :

• les codes des fonctions f et g sont très proches
• f reçoit une liste Python
• g reçoit une liste Numba
• Lignes 25-26 : la file est H car c’est sur elle que se font les opérations heappush (ligne 30 par exemple). Pour que Numba puisse inférer le type des éléments de la file, j’utilise une astuce : je place un élément, l’entier 0 qui est vu par Numba comme du type int64 et je le retire aussitôt car la file doit être vide au départ.

Le module Awkward Array¶

Numpy ne prend pas en charge le type ragged array ni les tableaux extensibles. Le module Awkward Array semble prendre en charge le type ragged array et en outre, ce module est compatible avec Numba 0.50.

Après échange avec l’auteur, Jim Pivarski, il apparaît que seule la structure de données ArrayBuilder pourrait permettre d’implémenter des vecteurs extensibles (mais non rétractables). Par ailleurs, les strutures de données du module dont essentiellement immuables.

Quoi qu’il en soit, les tableaux Awkward array peuvent être utiles pour des traitements de données complexes. Voici un exemple exécuté sous Google Colab. Le code est extrait d’un fichier Jupyter présent dans le code source de Awkward Array.

On installe le module awkward :

!pip install awkward

Collecting awkward

...Affichage tronqué....

Successfully installed awkward-1.3.0

On met à jour Numba :

!pip install --upgrade numba

Collecting numba

...Affichage tronqué....

Successfully installed llvmlite-0.36.0 numba-0.53.1

On teste :

import numba as nb

@nb.jit(nopython=True)
def run(array):
    out = np.empty(len(array), np.float64)
    for i in range(len(array)):
        out[i] = array[i]["x"]
        for y in array[i]["y"]:
            out[i] += y
    return out

akarray = ak.Array([{"x": 100, "y": [1.1, 2.2]}, {"x": 200, "y": []},
                    {"x": 300, "y": [3.3]}])

# Works for the layout nodes, but not the high-level ak.Array wrapper yet.
print(run(akarray))

[103.3 200.  303.3]