Journal Analyse de plage de valeurs dans Pythran

Posté par  (site Web personnel) . Licence CC By‑SA.
Étiquettes :
16
11
mai
2020

Sommaire

Demat'iNal,

Il y a quelques semaines, Pythran a gagné une analyse de plage de valeurs un peu plus solide que la précédente implémentation. Rien qui ne révolutionne la recherche, mais l'occasion pour moi d'explorer le sujet avec vous ici.

L'histoire commence en octobre 2018 avec l' issue #1029, alors que j'essayais de convertir des bouts de code de scikit-image à Pythran.

La fonction _integ

La fonction ci-dessous est extraite du fichier _hessian_det_appx.pyx, écrite en cython

# cython: wraparound=False
cdef inline Py_ssize_t _clip(Py_ssize_t x, Py_ssize_t low, Py_ssize_t high) nogil:
    if(x > high):
        return high
    if(x < low):
        return low
    return x

cdef inline cnp.double_t _integ(cnp.double_t[:, ::1] img, Py_ssize_t r, Py_ssize_t c, Py_ssize_t rl, Py_ssize_t cl) nogil:

    r = _clip(r, 0, img.shape[0] - 1)
    c = _clip(c, 0, img.shape[1] - 1)
    r2 = _clip(r + rl, 0, img.shape[0] - 1)
    c2 = _clip(c + cl, 0, img.shape[1] - 1)
    cdef cnp.double_t ans = img[r, c] + img[r2, c2] - img[r, c2] - img[r2, c]

    if (ans < 0):
        return 0
    return ans

On y retrouve les traditionnelles annotations de type, ainsi que des commentaires en début de fichier pour aider la génération de code.

La version Pythran est assez semblable

#pythran export _integ(float64[::], int, int, int, int)
import numpy as np
def _clip(x, low, high):
    assert 0 <= low <= high
    if x > high:
        return high
    if x < low:
        return low
    return x

def _integ(img, r, c, rl, cl):
    r = _clip(r, 0, img.shape[0] - 1)
    c = _clip(c, 0, img.shape[1] - 1)

    r2 = _clip(r + rl, 0, img.shape[0] - 1)
    c2 = _clip(c + cl, 0, img.shape[1] - 1)

    ans = img[r, c] + img[r2, c2] - img[r, c2] - img[r2, c]
    return max(0, ans)

On dégage les annotations de types et les aides à la génération de code. On spécifie la signature de la fonction à traduire (mais pas de la fonction auxiliaire), et on ajoute un assert qui prendra tout son sens plus tard dans le journal. Disons qu'il remplace le # cython: wraparound=False.

C'est le propos de ce journal : comment détecter qu'il n'y aura pas de wraparound sur les accès de tableau dans _integ, autrement dit que r, c et consorts sont positifs ou nuls. Pour cela, on va s'intéresser à l'analyse de plage de valeur.

note : en pythran, le comportement des assert est contrôlable à la compilation, par défaut ils dégagent

Implémentation de base

Depuis la PR #1522, Pythran est capable de calculer que la fonction clip renvoie une valeur toujours prositive ou nulle, et en déduit l'inutilité du wraparound.

L'analyse implémentée par Pythran est assez simple : elle travaille sur des intervalles à bornes numériques (non symboliques quoi); En gros on est capable de modéliser a \in [1:10] mais pas a \in [1: b].

L'analyse est interprocédurale, mais indépendante du site d'appel : on ne sait rien sur les arguments en entrée (et c'est pour cela qu'on a besoin d'un assert pour ajouter des préconditions) mais on peut en déduire des informations sur la valeur de retour, par exemple qu'elle est toujours positive ou nulle.

Commençons par un exemple simple :

def foo(a):
    assert a > 0
    b = c = 10
    while a > 0:
        a -= 1
        b += 1
    if b == 9:
        print("wtf")
    if b == 10:
        print("wtf")
    if b == 11:
        print("ok")
    return a, b, c

L'analyse va suivre le flot de contrôle, donc on commence par le début (d'oh) de la fonction, où l'on ne sait rien : a \in ]-\inf: +\inf[. Après le assert, on en sait un peu plus : a \in [1: +\inf[. Après les affectations, on a en plus b \in [10:10] , c \in [10:10].

Arrive le while. On sait d'après nos conditions actuelles que le premier test sera vrai, donc on rentre et on exécute les deux assignations pour arriver à a \in [0: +\inf[, b \in [11:11] , c \in [10:10]. On retombe sur le test, dont on ignore le résultat maintenant que a est peut-être passé en dessous de 1. L'astuce ici est d'effectuer un tour de boucle, regarder l'évolution des variables et de les prolonger. Dans notre cas, après un tour supplémentaire, on aurait a \in [0: +\inf[, b \in [12: 12] , c \in [10:10]. En regardant le comportement des bornes, on en déduit la sur-estimation a \in [0: +\inf[, b \in [11:+\inf] , c \in [10:10]. On a donc l'état en sortie de boucle.

On arrive sur plusieurs if consécutifs. Et d'après l'état de nos variables, on sait que les deux premières conditions seront fausses, on ne les visite pas. On se contente d'un passage dans la dernière…

Pythran peut utiliser ces informations pour dégager le code mort, comme on peut le voir avec un pythran -P test.py qui afficher sur la sortie standard :

def foo(a):
    a_ = a
    assert (a_ > 0)
    b = 10
    while (a_ > 0):
        a_ -= 1
        b += 1
    if (b == 11):
        builtins.print('ok')
    return (a_, b, 10)

Petits détails d'importance

Utiliser une approche naïve a quelques avantages en termes de précision. Par exemple, sur le cas suivant :

def foo(a):
    if a > 12:
        b = 1
    else:
        b = 2
    if a > 1:
        b = 2
    return b

Le passage dans la branche true du premier test enregistre b = 1 mais aussi, en suivant les successeurs de cette branche, que b = 2 car le second test sera forcément vrai. En suivant ce « fil » on arrive toujours à return 2. En suivant la branche false on a b = 2 et ensuite, que le second test soit vrai ou pas, on arrive toujours à return 2, donc la fonction est simplifiable par Pythran en

def foo(a):
    return 2

Mais le parcours complet de chacun des fils peut être très couteux. Et si on se retrouve avec une grosse série de if, on a une jolie explosion combinatoire du nombre de fils à suivre… Si le nombre de fils explose, Pythran se rabat sur un algorithme plus simple mais moins précis.

Conclusion

Il parait que c'est bien de mettre une conclusion… Je dirais qu'ici, je trouve ça chouette que Pythran bénéficie comme ça d'une construction qui reste du Python valide !

Note: il existe une version plus ou moins équivalente de cet article, en anglais.

  • # Sympa

    Posté par  (site Web personnel) . Évalué à 3 (+1/-0).

    Merci de nous partager ces détails d’implémentation, je trouve ça toujours fascinant.

    A noter que pour que ton explication sur foo() et a tienne la route, il y a un présupposé que a est un entier. Sinon, a -= 1 pourrait ouvrir des valeurs un peu négatives.

    Sinon, comment Pythran réalise-t-il l'exploration des fils que tu décris ? J'imagine que c'est à coup de graphe qui transportent les intervalles de variable d'un noeud à un autre, avec des possibles fils qui se rejoignent ? Ou tu fais juste une synthèse à la fin de tous les fils pour voir ce qui s'en dégage ?

    • [^] # Re: Sympa

      Posté par  (site Web personnel) . Évalué à 3 (+1/-0).

      Merci de nous partager ces détails d’implémentation, je trouve ça toujours fascinant.

      Merci ! Je ne comprends pas la moitié des notions théoriques que je manipule, mais au moins j'essaie

      il y a un présupposé que a est un entier

      Oui, c'est un vrai problème qui doit cacher quelques bugs dans Pythran. Mais c'est ma technique secrète pour faire vivre le projet : introduire des bugs pour que les utilisateurs lèvent des issues, je les corrige et y a du mouvement :-)

      Sinon, comment Pythran réalise-t-il l'exploration des fils que tu décris ? J'imagine que c'est à coup de graphe […]

      C'est ça, le graphe contient le successeur de chaque nœud, et chaque nœud a un traitement dédié. On accumule (en calculant des unions d'intervalles) les résultats de chaque fil par nœud rencontré. Par contre je ne prends pas en compte les intervalles de vie des variables, j'explore comme une nouille à chaque fois. Si tu te sens de regarder ça, je suis preneur ;-)

Envoyer un commentaire

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n’en sommes pas responsables.