Mesurer les performances d’un snippet Python 6

This entry was posted in Programmation and tagged dict merge perf python on by

Ca fait longtemps que j’avais pas musique.

L’open source c’est fantastique. Github c’est merveilleux. On parle de batbelt, et paf, quelques jours plus tard on a notre première contribution.

Ce qui est sympa avec cette lib, c’est que ce sont des fonctions simples et courtes, axées sur des tâches très précises. Le code est donc généralement intéressant à lire, mais pas trop compliqué, et on tombe souvent sur des cas d’école.

C’est le cas de cette modification de la fonction dmerge(). Originalement, dmerge permet de créer un dictionnaire à partir de la fusion de de 2 autres dicos, et ça marchait comme ça:

def dmerge(d1, d2):
    d = {}
    d.update(d1)
    d.update(d2)
    return d

Facile à comprendre, rapide, simple, et le comportement par défaut est intuitif : si une clé est en double, la clé du deuxième dico écrase la première.

Comme le précisait Etienne, ce comportement est néanmoins un parmi de nombreux possibles. On pourrait aussi vouloir:

  • Lever une exception en cas de doublon.
  • Concaténer ou additionner les doublons.
  • Mettre les doublons dans une liste.
  • Garder la valeur originale en cas de doublon.
  • Prendre la valeur la plus grande / petite en cas de doublon.
  • Etc.

Pour cela, notre contributeur a proposé qu’on puisse passer en paramètre une fonction qui choisit quelle valeur garder en cas de doublon. Le code devient donc :

def dmerge(d1, d2, merge_func=lambda v1, v2: v2):
    d = {}
    d.update([(k, v) for k, v in d1.iteritems() if k not in d2])
    d.update([(k, v) for k, v in d2.iteritems() if k not in d1])
    d.update([(k, merge_func(v, d2[k])) for k, v in d1.iteritems() if k in d2])
    return d

Avoir une valeur par défaut nous permet de garder le comportement initial. Pour cela on utilise une lambda. C’est ce qu’on appelle l’injection de dépendance.

Comme j’ai bien faire mumuse avec Python, je me suis demandé : “quelle est la stratégie de merge la plus rapide ?”. J’ai donc fait plusieurs tests de merge, avec plusieurs algos. Voici ce que ça donne:

 from itertools import chain
 
 
 def dmerge1(d1, d2, merge_func=None):
     """
         Mon premier essai, en virant la lambda et en utilisant itertools.
     """
     d = {}
 
     if merge_func is None:
 
         d.update(d1)
         d.update(d2)
         return d
 
     for k, v in chain(d1.iteritems(), d2.iteritems()):
         if k in d1 and k in d2:
             d[k] = merge_func(d1[k], d2[k])
         else:
             d[k] = v
 
     return d
 
 
 
 def dmerge2(d1, d2, merge_func=lambda v1, v2: v2):
     """
         Le code du PR original
     """
     d = {}
     d.update([(k, v) for k, v in d1.iteritems() if k not in d2])
     d.update([(k, v) for k, v in d2.iteritems() if k not in d1])
     d.update([(k, merge_func(v, d2[k])) for k, v in d1.iteritems() if k in d2])
     return d
 
 
 def dmerge3(d1, d2, merge_func=None):
     """
        Un mélange du code original et de mon premier essai.
     """
     d = {}
 
     d.update(d1)
 
     if merge_func is None:
         d.update(d2)
         return d
 
     for k, v in d2.iteritems():
         if k in d:
             d[k] = merge_func(d[k], v)
         else:
             d[k] = v
 
     return d
 
 
 
 def dmerge4(d1, d2, merge_func=None):
     """
         Le code original, en virant la lambda
     """
     d = {}
 
     if merge_func is None:
         d.update(d1)
         d.update(d2)
         return d
 
     d.update([(k, v) for k, v in d1.iteritems() if k not in d2])
     d.update([(k, v) for k, v in d2.iteritems() if k not in d1])
     d.update([(k, merge_func(v, d2[k])) for k, v in d1.iteritems() if k in d2])
     return d
 
 
 if __name__ == "__main__":
 
     import random
     import timeit
 
     print('Generate test dicts')
 
     # pour que le test soit juste, il faut créer plusieurs types de dicos:
     # des longs, et des courts avec plein de collisions ou moins
     d1 = {random.randint(0, 100): 'd1' for x in xrange(10000)}
     d2 = {random.randint(0, 100): 'd2' for x in xrange(10000)}
     d3 = {random.randint(0, 10000000): 'd1' for x in xrange(1000000)}
     d4 = {random.randint(0, 10000000): 'd2' for x in xrange(1000000)}
 
     merge_to_list = lambda a, b: [a, b]
 
     # ensuite il faut s'assurer que toutes ces fonctions retournent bien
     # la même chose
 
     print("Testing returns value all match")
 
     assert (dmerge1(d1, d2) == dmerge2(d1, d2)
             == dmerge3(d1, d2) == dmerge4(d1, d2))
     assert (dmerge1(d1, d2, merge_to_list) == dmerge2(d1, d2, merge_to_list)
            == dmerge3(d1, d2, merge_to_list) == dmerge4(d1, d2, merge_to_list))
 
     assert (dmerge1(d3, d4) == dmerge2(d3, d4)
             == dmerge3(d3, d4) == dmerge4(d3, d4))
     assert (dmerge1(d3, d4, merge_to_list) == dmerge2(d3, d4, merge_to_list)
             == dmerge3(d3, d4, merge_to_list) == dmerge4(d3, d4, merge_to_list))
 
     assert (dmerge1(d1, d4) == dmerge2(d1, d4)
             == dmerge3(d1, d4) == dmerge4(d1, d4))
     assert (dmerge1(d1, d4, merge_to_list) == dmerge2(d1, d4, merge_to_list)
             == dmerge3(d1, d4, merge_to_list) == dmerge4(d1, d4, merge_to_list))
 
 
     # enfin on lance l'évaluation du temps d'éxécution avec timeit()
 
     print("Start timing")
 
 
     # ce code est exécuté une fois par appel de timeit
     # notez l'astuce 'from __main__ import x' qui importe du code
     # du fichier en cours, ce qui sert rarement
     setup = '''from __main__ import (dmerge1, dmerge2, dmerge3, dmerge4,
                                      d1, d2, d3, d4, merge_to_list)'''
 
 
 
     # ensuite on fait des appels à timeit : 
     # - le premier paramètre est le code à mesurer: il faut qu'il 
     #   soit le plus simple et court possible
     # - le second et le code d'initialisation avant le test (hors mesure)
     # - le 3e est le nombre de fois que le code va être appelé. 
 
 
     # on va tester chaque fonction pour chaque type de dico, une fois
     # avec l'approche par défaut, et une fois avec une fonction de merge
     # personnalisée
     print "Lots of collisions"
 
     print "Default merge strategy"
     print "1", timeit.timeit("dmerge1(d1, d2)", setup=setup, number=1000000)
     print "2", timeit.timeit("dmerge2(d1, d2)", setup=setup, number=1000000)
     print "3", timeit.timeit("dmerge3(d1, d2)", setup=setup, number=1000000)
     print "4", timeit.timeit("dmerge4(d1, d2)", setup=setup, number=1000000)
 
     print "Custom merge strategy"
     print "1", timeit.timeit("dmerge1(d1, d2, merge_to_list)",
                               setup=setup, number=100000)
     print "2", timeit.timeit("dmerge2(d1, d2, merge_to_list)",
                               setup=setup, number=100000)
     print "3", timeit.timeit("dmerge3(d1, d2, merge_to_list)",
                               setup=setup, number=100000)
     print "4", timeit.timeit("dmerge4(d1, d2, merge_to_list)",
                               setup=setup, number=100000)
 
 
    # le nombre de répétitions est bien plus faible ici car sinon le test
    # est très très long
 
     print "Long dictionaries"
 
     print "Default merge strategy"
     print "1", timeit.timeit("dmerge1(d3, d4)", setup=setup, number=100)
     print "2", timeit.timeit("dmerge2(d3, d4)", setup=setup, number=100)
     print "3", timeit.timeit("dmerge3(d3, d4)", setup=setup, number=100)
     print "4", timeit.timeit("dmerge4(d3, d4)", setup=setup, number=100)
 
     print "Custom merge strategy"
     print "1", timeit.timeit("dmerge1(d3, d4, merge_to_list)",
                               setup=setup, number=100)
     print "2", timeit.timeit("dmerge2(d3, d4, merge_to_list)",
                               setup=setup, number=100)
     print "3", timeit.timeit("dmerge3(d3, d4, merge_to_list)",
                               setup=setup, number=100)
     print "4", timeit.timeit("dmerge4(d3, d4, merge_to_list)",
                               setup=setup, number=100)
 
     print "Mixed dictionaries"
 
     print "Default merge strategy"
     print "1", timeit.timeit("dmerge1(d1, d4)", setup=setup, number=100)
     print "2", timeit.timeit("dmerge2(d1, d4)", setup=setup, number=100)
     print "3", timeit.timeit("dmerge3(d1, d4)", setup=setup, number=100)
     print "4", timeit.timeit("dmerge4(d1, d4)", setup=setup, number=100)
 
     print "Custom merge strategy"
     print "1", timeit.timeit("dmerge1(d1, d4, merge_to_list)",
                              setup=setup, number=100)
     print "2", timeit.timeit("dmerge2(d1, d4, merge_to_list)",
                              setup=setup, number=100)
     print "3", timeit.timeit("dmerge3(d1, d4, merge_to_list)",
                              setup=setup, number=100)
     print "4", timeit.timeit("dmerge4(d1, d4, merge_to_list)",
                              setup=setup, number=100)
 
 
# Et voici le résultat que ça nous ressort. On voit clairement 
# que la 3eme fonction donne les meilleurs perfs, du coup
# c'est celle qu'on a choisit
 
 ## Generate test dicts
 ## Testing returns value all match
 ## Start timing
 ## Lots of collisions
 ## Default merge strategy
 ## 1 19.9299340248
 ## 2 148.185166121
 ## 3 21.2276539803
 ## 4 21.2074358463
 ## Custom merge strategy
 ## 1 30.646312952
 ## 2 18.522135973
 ## 3 14.0125968456
 ## 4 18.5139119625
 ## Long dictionaries
 ## Default merge strategy
 ## 1 84.4819910526
 ## 2 383.444111109
 ## 3 80.7273669243
 ## 4 86.0287930965
 ## Custom merge strategy
 ## 1 294.41114521
 ## 2 377.38009119
 ## 3 154.505481005
 ## 4 256.771039963
 ## Mixed dictionaries
 ## Default merge strategy
 ## 1 19.9574320316
 ## 2 87.1410660744
 ## 3 19.3570361137
 ## 4 19.524998188
 ## Custom merge strategy
 ## 1 60.6157000065
 ## 2 86.3876900673
 ## 3 59.0331327915
 ## 4 87.0504939556
 ## [Finished in 2494.7s]

Le test complet a pris en tout 2494.7s, soit 41 minutes, pour tourner sur ma machine, et je l’ai lancé plusieurs fois avec différentes modifs au fil de la journée. Il faut vraiment est un geek pour aimer faire ce genre de connerie. Parce que soyons honnête, tout le monde s’en branle des perfs de cette fonction :-)

Il faut savoir aussi qu’après coup j’ai réalisé que son code utilisait des listes en intention, et non des expressions génératrices, ce qui fait qu’il faut attendre que toute la liste soit générée avec que update() fasse son travail.

Il y avait donc des cas supplémentaires à tester et j’avais mergé son code dans batbelt. Arf, l’optimisation n’a jamais de fin ^^

Bref, j’ai relancé un test avec avec des listes en intentions (et même avec des expressions ternaires ce qui donne des trucs capilotractés):

def dmerge1(d1, d2, merge_func=None):
    """
        Une version de l'ancien dmerge3 qui utilise une expression génératrice.
    """
    d = {}
 
    d.update(d1)
 
    if merge_func is None:
        d.update(d2)
        return d
 
    d.update((k, (v if k not in d else merge_func(d[k], v))) for k, v in d2.iteritems())
 
    return d
 
 
 
def dmerge2(d1, d2, merge_func=lambda v1, v2: v2):
    """
        La version du proposée par notre gentil contributeur, mais
        avec des expressions génératrices à la place des listes en 
        intention.
    """
    d = {}
    d.update((k, v) for k, v in d1.iteritems() if k not in d2)
    d.update((k, v) for k, v in d2.iteritems() if k not in d1)
    d.update((k, merge_func(v, d2[k])) for k, v in d1.iteritems() if k in d2)
    return d
 
 
 
def dmerge3(d1, d2, merge_func=None):
    """
      La version la plus rapide du test précédent.
    """
    d = {}
 
    d.update(d1)
 
    if merge_func is None:
        d.update(d2)
        return d
 
    for k, v in d2.iteritems():
        if k in d:
            d[k] = merge_func(d[k], v)
        else:
            d[k] = v
 
    return d
 
 
def dmerge4(d1, d2, merge_func=None):
    """
        La version proposée par notre contributeur, optimisée comme un connard.
    """
    d = {}
 
    if merge_func is None:
        d.update(d1)
        d.update(d2)
        return d
 
    d.update((k, v) for k, v in d1.iteritems() if k not in d2)
    d.update((k, v) for k, v in d2.iteritems() if k not in d1)
    d.update((k, merge_func(v, d2[k])) for k, v in d1.iteritems() if k in d2)
    return d
 
 
## Generate test dicts
## Testing returns value all match
## Start timing
## Lots of collisions
## Default merge strategy
## 1 12.2690660954
## 2 97.121183157
## 3 12.1084120274
## 4 12.6807589531
## Custom merge strategy
## 1 8.73903894424
## 2 12.0493769646
## 3 8.00074601173
## 4 11.4764301777
## Long dictionaries
## Default merge strategy
## 1 54.5233860016
## 2 218.695598841
## 3 70.213809967
## 4 61.8348701
## Custom merge strategy
## 1 103.258821964
## 2 217.720175982
## 3 96.5204670429
## 4 214.480421066
## Mixed dictionaries
## Default merge strategy
## 1 19.169850111
## 2 66.9599928856
## 3 19.4371211529
## 4 19.5183057785
## Custom merge strategy
## 1 64.7940750122
## 2 66.9712991714
## 3 58.5918440819
## 4 67.5281140804
## [Finished in 1619.3s]

La bonne nouvelle pour moi, c’est que l’algo 3 est toujours le plus rapide, j’ai pas à re pusher.

Mais il est intéressant de constater que globalement les 4 tests mettent 1619.3s à s’exécuter. Globalement utiliser des expressions génératrices boost bien les perfs.

Télécharger le code de l’article.

6 thoughts on “Mesurer les performances d’un snippet Python”

  • Badeu

    Moralité, la prochaine fois je pousserai pas du code écrit en 10 secondes et pas testé.

    Par contre un truc me turlupine toujours. Parce qu’au final en réessayant d’optimiser après la première série de tests de perf sur github, je suis aussi arrivé à la solution du deuxième dmerge1 (et je me disais putain ça va tout arracher c’est obligatoire !! quelle naiveté)


    ## Long dictionaries
    ## Default merge strategy
    ## 1 54.5233860016
    ## 3 70.213809967

    WTF ?! J’ai exécuté les tests de performances un paquet de fois, et ça se vérifie toujours. Pourtant dans ce cas, le code de dmerge1 et dmerge3 est identique.

  • kontre

    C’est le même algo mais ça ne fait pas la même chose : les générateurs sont plus rapides que les boucles for génériques. C’est relativement logique : c’est moins général, il y a moins de cas différents, donc on peut plus optimiser.

    On a toujours des surprises avec le profiling…

  • Etienne

    @ Kontre, Badeu

    Comme il s’agit de la “Default merge strategy”, le code passe pas par le générateur de dmerge1 ou le for de dmerge3. Donc le problème est pas là.

    J’ai essayé ça avec le code copié ci-dessus (les versions avec les expressions génératrices):

    if __name__ == "__main__":
    import random
    import timeit
 
    print('Generate test dicts')
    d3 = {random.randint(0, 10000000): 'd1' for x in xrange(1000000)}
    d4 = {random.randint(0, 10000000): 'd2' for x in xrange(1000000)}
    print("Start timing")
    setup = '''from __main__ import (dmerge1, dmerge2, dmerge3, dmerge4,
       d3, d4)'''
    print ("Long dictionaries")
    print ("Default merge strategy")
    print ("1", timeit.timeit("dmerge1(d3, d4)", setup=setup, number=100))
    print ("3", timeit.timeit("dmerge3(d3, d4)", setup=setup, number=100))
 
## Generate test dicts
## Start timing
## Long dictionaries
## Default merge strategy
## 1 79.4722130299
## 3 79.2059469223

    Les résultats sont identiques (ouf…). Donc le problème est de ton côté: soit le code des deux fonctions est pas identique, soit les conditions des deux tests sont pas les mêmes.

  • kontre

    My bad, j’ai bêtement zappé un return.
    [mauvaise foi] Mais aussi la bonne pratique de n’avoir qu’un point de sortie n’est pas respectée, on s’y perd ! [/mauvaise foi]

  • Badeu

    Quand on regarde d’un peu plus près au code généré, il n’est pas tout à fait identique entre dmerge1 et dmerge3.

    pour dmerge1, d est accédé avec des LOAD_DEREF et STORE_DEREF, pour dmerge3 avec des LOAD_FAST et STORE_FAST Ce qui semble logique vu que le générateur fait une closure sur d dans dmerge1.

    Je reste juste étonné de l’impact que ça a.

  • Etienne

    @ Badeu
    T’as raison, l’opcode est pas identique.

    Mais il y a un problème avec:
    ## Long dictionaries
    ## Default merge strategy
    ## 1 54.5233860016
    ## 3 70.213809967

    Chez moi c’est plutôt de l’ordre de :
    ## Long dictionaries
    ## Default merge strategy
    ## 1 78.3221180439
    ## 3 77.8049631119
    Un léger avantage pour dmerge3

Leave a comment

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <pre> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Des questions Python sans rapport avec l'article ? Posez-les sur IndexError.