Forum Programmation.c Performances de memcpy ???

Posté par .
Tags : aucun
8
8
fév.
2010
Bonjour chers lecteurs du forum,

Une petite question me tarabuste : je viens de découvrir le benchmark tout simple mbw (pour memory bandwith) qui teste les performance de la machine pour ce qui est de la mémoire. Il est disponible sous debian testing ou à l'adresse http://linux.softpedia.com/progDownload/MBW-Download-12167.h(...) il n'y a pas plus simple : un simple fichier C à compiler).

Il s'agit d'allouer un tableau d'entiers, et de le copier le plus vite possible vers un autre tableau. Le test mesure la vitesse de copie. De manière basique on précise simplement la quantité (en Mo) de mémoire à utiliser pour le test, par exemple 200: ./mbw 200 (utilisera au total 400 Mo, hé oui si vous avez suivi il faut 200 Mo pour l'original et 200Mo pour la copie).
Essentiellement 3 tests sont disponibles
* le premier, un memcpy tout bête, source -> destination pour la quantité donnée initialement
* le deuxième, une copie a la mano du type for (...) { dest[i] = src[i] }
* le dernier, un memcpy par blocs de taille prédéfinie (quelques dizaines de Ko).

Les résultats (sur différentes machines, architectures variées 64 et 32 bits, amd et intel, datant des années 2003 à aujourd'hui, distributions variées avec une dominante debian) sont éloquents:
Dans tous les cas, le memcpy tout seul est le plus mauvais.
La copie naïve met entre 1,5 et 2.5 fois moins de temps que memcpy (suivant les architectures).
Le memcpy par blocs de quelques ko est infiniment plus rapide que les autres (de l'ordre de 8 fois plus rapide que le memcpy standard, surtout si on tune la taille du bloc).

Alors on pense immédiatement à des effets de cache, ce qui se conçoit pour le memcpy par blocs (quelques dizaines de ko = taille du cache L1 par exemple). Ce que confirme valgrind --tool=cachegrind par exemple (même en tunant les paramètres pour le faire ressembler aux machines à ma disposition, x86info --cache est votre ami).

Les optimisations du compilateur n'entrent pas en jeu (en -O0 comme en -O3 comme avec -march=native ou non ne change pas grand-chose). J'exclus également les mécanismes de prefetch hardware qui pour les données n'existent que depuis peu (pas vraiment sur les anciens processeurs en tous cas).

En revanche, rien ne m'explique pourquoi la copie naïve est plus rapide que le memcpy. Les résultats de cachegrind ne font pas apparaître de différences flagrantes dans l'utilisation du cache, pourtant la différence est réelle... C'est pourquoi je vous pose la question !

D'ailleurs memcpy ne devrait-il pas (ou le compilateur quand il compile memcpy) faire attention au cache en choisissant une taille de copie convenable ? pas forcément optimale mais convenant à une majorité de processeurs actuels, et l'utiliser comme le fait la version par blocs de la copie, un peu comme fait gparted quand on copie des partitions, pour ce qui est de la taille de bloc à prendre.

Notons que ce benchmark est assez spécifique bien entendu. Dans d'autres applications plus orientées calcul j'ai déjà vu memcpy faire gagner pas mal de temps. Mais là j'ai vraiment du mal à m'expliquer le résultat, même en ayant relu http://people.redhat.com/drepper/cpumemory.pdf

En résumé deux choses sont étonnantes de mon point de vue :
1) le manque de tenue de memcpy par rapport à la copie naïve. On mesure quand même bien l'appel le plus simple qui peut être fait de ces fonctions ! Et la différence est significative. Alors certes il ne s'agit que de copier des entiers et pas des structures compliquées, mais tout de même.
2) pourquoi memcpy ne fait pas par défaut une copie par taille de quelques ko. Les processeurs ont tous depuis plusieurs années un cache L1 qui fait au moins 32Ko, on pourrait décider que memcpy copie par bloc de 16Ko par exemple.


PS : si quelqu'un pouvait faire tourner ce bench sur quelques archis intel type core i* avec DDR3 et poster les chiffres des lignes AVG, je l'en remercie d'avance.
PS : je vais recompiler en utilisant les options de la branche graphite de gcc-4.4 qui est censée bien gérer la gestion du cache dans les boucles, voir la dépêche https://linuxfr.org//2009/04/21/24809.html J'ose espérer que la boucles si simple de la méthode naïve pourra être optimisée sans trop de difficultés par le compilateur, sinon il faudra voir ce que donne un découpage à la main.
  • # C'est posté dans un forum...

    Posté par . Évalué à 6.

    Mais ça pourrait peut-être intéresser plus de monde en journal si la réponse n'est pas trop triviale. Ok fallait réfléchir avant de poster mais je ne pensais pas être si long.
    Qu'en pensez-vous ?
  • # Une piste...

    Posté par . Évalué à 7.

    J'ai jeté un coup d'oeil au code. La «copie naive» utilise des pointeurs sur des entiers longs, donc du 32 bits sur x86. memcpy fait une copie d'octet
    (au moins d'après la page de man)
  • # Commentaire supprimé

    Posté par . Évalué à 5.

    Ce commentaire a été supprimé par l'équipe de modération.

  • # Parce qu'il n'y a pas que Linux / i386 dans la vie...

    Posté par (page perso) . Évalué à 4.

    Pour apporter quelques points de données supplémentaires, des tests sur d'autres systèmes que les tiens. Sur Linux-sparc64 pas très jeune (machine multi-utilisateurs, avec 512Mo de RAM dont 300 sont réellement utilisés). On constate les mêmes choses :
    fperrin@gadget:~/mbw$ ./mbw 10|grep AVG
    AVG     Method: MEMCPY  Elapsed: 0.14899        MiB: 10.00000   Copy: 67.116 MiB/s
    AVG     Method: DUMB    Elapsed: 0.07369        MiB: 10.00000   Copy: 135.695 MiB/s
    AVG     Method: MCBLOCK Elapsed: 0.07356        MiB: 10.00000   Copy: 135.940 MiB/s
    Sur FreeBSD (7.2, sur i386) :
    papillon:~% tar -xf mbw-1.1-1.tar.gz
    papillon:~% cd mbw
    papillon:~/mbw% make mbw
    cc -O -Wall -g  mbw.c  -o mbw
    mbw.c: In function 'worker':
    mbw.c:102: warning: implicit declaration of function 'mempcpy'
    mbw.c:102: warning: incompatible implicit declaration of built-in function 'mempcpy'
    mbw.c:105: warning: incompatible implicit declaration of built-in function 'mempcpy'
    /var/tmp//ccz83HJk.o(.text+0x1f5): In function `worker':
    /home/fred/mbw/mbw.c:102: undefined reference to `mempcpy'
    /var/tmp//ccz83HJk.o(.text+0x247):/home/fred/mbw/mbw.c:105: undefined reference to `mempcpy'
    *** Error code 1
    
    Stop in /usr/home/fred/mbw.
    zsh: exit 1     make mbw
    papillon:~/mbw% vi mbw.c
    # remplacer mempcpy avec un no-op...
    papillon:~/mbw% make mbw
    cc -O -Wall -g  mbw.c  -o mbw
    mbw.c: In function 'worker':
    mbw.c:89: warning: unused variable 'c'
    papillon:~/mbw% ./mbw 100 | grep AVG
    AVG     Method: MEMCPY  Elapsed: 0.17829        MiB: 100.00000  Copy: 560.894 MiB/s
    AVG     Method: DUMB    Elapsed: 0.14917        MiB: 100.00000  Copy: 670.365 MiB/s
    AVG     Method: MCBLOCK Elapsed: 0.00000        MiB: 100.00000  Copy: 62500000.000 MiB/s
    papillon:~/mbw% ./mbw 200 | grep AVG
    AVG     Method: MEMCPY  Elapsed: 0.33782        MiB: 200.00000  Copy: 592.032 MiB/s
    AVG     Method: DUMB    Elapsed: 0.28624        MiB: 200.00000  Copy: 698.709 MiB/s
    AVG     Method: MCBLOCK Elapsed: 0.00000        MiB: 200.00000  Copy: 133333333.333 MiB/s
    # en enlevant -g
    papillon:~/mbw% gcc -O -Wall mbw.c -o mbw
    mbw.c: In function 'worker':
    mbw.c:89: warning: unused variable 'c'
    papillon:~/mbw% ./mbw 100|grep AVG
    AVG     Method: MEMCPY  Elapsed: 0.17197        MiB: 100.00000  Copy: 581.484 MiB/s
    AVG     Method: DUMB    Elapsed: 0.14150        MiB: 100.00000  Copy: 706.733 MiB/s
    AVG     Method: MCBLOCK Elapsed: 0.00000        MiB: 100.00000  Copy: 62500000.000 MiB/s
    # avec -O3
    papillon:~/mbw% gcc -O3 -Wall mbw.c -o mbw
    mbw.c: In function 'worker':
    mbw.c:89: warning: unused variable 'c'
    papillon:~/mbw% ./mbw 100|grep AVG
    AVG     Method: MEMCPY  Elapsed: 0.15598        MiB: 100.00000  Copy: 641.096 MiB/s
    AVG     Method: DUMB    Elapsed: 0.14457        MiB: 100.00000  Copy: 691.689 MiB/s
    AVG     Method: MCBLOCK Elapsed: 0.00000        MiB: 100.00000  Copy: 62500000.000 MiB/s
    Donc : les GNUism, c'est pas génial ; il y a d'autres OS sous lesquels memcpy n'est pas si mauvais que ça ; il faudrait tester wmemcpy ; -O3 semble profiter plus à memcpy qu'à la copie manuelle.
    • [^] # Re: Parce qu'il n'y a pas que Linux / i386 dans la vie...

      Posté par (page perso) . Évalué à 2.

      > -O3 semble profiter plus à memcpy qu'à la copie manuelle.

      Et pour cause... elles sont inversées !
      • [^] # Re: Parce qu'il n'y a pas que Linux / i386 dans la vie...

        Posté par (page perso) . Évalué à 4.

        Effectivement, dans les commentaires et dans main() les tests sont 0 = MEMCPY, 1 = DUMB, 2 = MCBLOCK, dans worker() c'est 1 = MEMCPY, 2 = MCBLOCK et 3 = DUMB.

        Ça m'étonnait d'autant plus qu'après avoir posté, je suis allé faire un tour dans /usr/src/lib/libc/i386 (c'est beau un BSD, les sources sont à un cd de distance :-p ), et memcpy (identique à memmove) était écrit en assembleur. Je savais pas trop quoi penser d'un compilateur qui optimise mieux de l'assembleur écrit avec amour que du C écrit à la main...

        Sinon, pour rebondir sur ce que disait quelqu'un d'autre plus haut, memcpy copie la source vers la destination par mots entiers (dans BSD libc toujours).
    • [^] # Re: Parce qu'il n'y a pas que Linux / i386 dans la vie...

      Posté par . Évalué à 2.

      Merci pour les exemples, j'avais essayé sur une autre archi que i386 et amd64, mais pas du sparc.
  • # la version bloc de mbw est bugguée

    Posté par (page perso) . Évalué à 5.

    La version bloc de mbw est bugguée, elle ne fait pas vraiment un
    memcpy, il ne faut vraiment pas prendre en compte le résultat obtenu
    avec... Il faut appliquer le patch ci-dessous pour que ce soit vraiment
    une copie complète:

    Seulement dans mbw-mine: mbw
    diff -ur mbw/mbw.c mbw-mine/mbw.c
    --- mbw/mbw.c 2006-07-04 14:45:01.000000000 +0200
    +++ mbw-mine/mbw.c 2010-02-09 13:39:52.000000000 +0100
    @@ -98,11 +98,11 @@
    gettimeofday(&endtime, NULL);
    } else if(type==2) { /* memcpy block test */
    gettimeofday(&starttime, NULL);
    - for(t=0; t<array_bytes; t+=block_size) {
    - c=mempcpy(b,a,block_size);
    + for(t=0; t+block_size<=array_bytes; t+=block_size) {
    + c=mempcpy((void*)b+t,(void*)a+t,block_size);
    }
    - if(t>array_bytes){
    - c=mempcpy(b,a,t-array_bytes);
    + if(t<array_bytes){
    + c=mempcpy((void*)b+t,(void*)a+t,array_bytes-t);
    }
    gettimeofday(&endtime, NULL);
    } else { /* dumb test */
  • # Les versions "dumb" et "memcpy" sont INVERSEES

    Posté par (page perso) . Évalué à 10.

    Bon, mbw est vraiment à jeter tel quel. Les version dumb et memcpy sont
    INVERSEES:

    type: 0=use memcpy, 1=use dumb copy

    if(type==1) { /* memcpy test */

    Donc il faut inverser complètement l'interprétation, et le memcpy de la
    glibc est bien celui qui remporte le benchmark.
  • # versions optimisées à venir

    Posté par (page perso) . Évalué à 2.

    Par ailleurs, pour les versions 32bits de la glibc qui a priori ne
    peuvent pas supposer disposer des instructions SSE pour utiliser à
    plein régime le processeur, les distributions fournissent
    éventuellement une version "i686" de la glibc, et par ailleurs, cf

    http://vger.kernel.org/~davem/cgi-bin/blog.cgi/2010/02/07#st(...)
  • # Merci pour toutes vos réponses...

    Posté par . Évalué à 2.

    j'avoue que ces erreurs triviales (inversion des tests) m'étaient complètement passées à côté /o\

    Tout est pour le mieux donc, l'ordre des choses est respecté. Je vais quand même regarder ce que donne gcc-4.4 en optimisant un peut les boucles avec le framework graphite.

    khivapia
  • # Copier "par bloc" ?

    Posté par . Évalué à 2.

    Juste une remarque sur ta question 2 : que veux-tu dire par "copier par bloc" exactement ? Ça voudrait dire qu'il faut faire 16Ko (par exemple), s'arrêter, et continuer ?

    Car sache que pour une copie de mémoire en mémoire, étant donné que c'est le CPU qui fait le boulot, il ne peut le faire qu'avec les instructions et les registres dont il dispose. C'est à dire que généralement, il va faire la copie 4 octets par 4 octets sur archi 32 bits. Bref, on ne peut pas faire "16Ko" d'un coup. Donc tu le fait 4o par 4o, et ça jusqu'à la fin.

    Après, comme le précise Samuel ci-dessus, aujourd'hui pas mal de memcpy utilisent les instructions SIMD, qui ont des registres plus gros (128 voire 256 bits) et sont généralement architecturée pour gérer des gros débits de données.

    Inconvénient avec cette méthode, il faut aligner les lectures/écritures (en plus, l'alignement est aussi très important pour le cache, vu qu'ils n'ont généralement pas une associativité de fou). Enfin, c'est aussi valable dans une ALU classique, même si on a la possibilité de faire des lectures/écritures non-alignées de manière transparente ; mais on perd en perf.
    • [^] # Re: Copier "par bloc" ?

      Posté par . Évalué à 2.

      Cette deuxième question venait essentiellement de divers résultats sur le troisième test, copie "par blocs". Comme elle est complètement bugguée, (merci Samuel Thibault aka youpi), cette deuxième question n'est plus très pertinent.
      Je voulais dire qu'il existe une taille optimale pour que le cache L1 soit utilisé au mieux : schématiquement, le processeur mettra de toutes façons beaucoup moins de temps à faire la copie (surtout avec les SSE) qu'à charger les données depuis la mémoire et à les y renvoyer, du coup il y a un compromis à effectuer entre données à charger dans le cache en attente d'y être copiée et taille du cache dédiée à la destination.

      En fait le processeur doit gérer ça de lui même de toutes façons (c'est aussi son boulot de gérer le cache). Mais pas forcément très bien, voir par exemple http://software.intel.com/en-us/articles/copying-accelerated(...) . Pour laisser plus de place aux données en provenance ils suggèrent d'utiliser les instructions de "streaming" (opérations mémoire non temporelles) qui court-circuitent le cache (notamment pour ce qui est de l'écriture, pour laisser plus de place à ce qui arrive). C'est bénéfique dans le cas de mbw car les données copiées ne sont pas immédiatement réutilisées.
      • [^] # Re: Copier "par bloc" ?

        Posté par . Évalué à 4.

        J'allais dire ce que tu décris dans ton deuxième paragraphe : tu n'as (généralement) pas le contrôle sur la manière dont le processeur gère le cache. Tu ne peux donc rien dire quant à la quantité de données qui sera en L1. Et même si c'était le cas, que veux tu faire de spécifique par rapport à ça dans ton algorithme ? Faire des pauses tous les n octets ? (je prend cette histoire débile de pause pour essayer de te faire réfléchir à ce que tu veux vraiment mettre dans ce code pour gérer la copie "par bloc" ; car moi, je ne comprend pas du tout ce que ça change dans ton algo de savoir la taille du L1).

        Bon après, sur des archis un peu plus évoluées que le x86, vu que tu as un paquet de registres pour faire la copie, tu peux effectivement essayer de t'arranger pour utiliser autant de registres qu'une ligne de cache par exemple. Tu peux aussi essayer de voir que de toutes façons ton pipeline sera plein assez vite vu que tu ne peux faire que deux load/store par cycle, ou un truc du genre, et essayer de régler ces paramètres en fonction.

        Ce qui est marrant avec le lien que tu donnes, c'est que les indications de gestion de cache (accessibles uniquement pour l'Altivec) des PowerPC G4 ont disparu dans le G5 car elles ne servaient à priori pas à grand chose niveau perf. Bizarre que Intel s'y mette.
        • [^] # Re: Copier "par bloc" ?

          Posté par . Évalué à 4.

          et même si c'était le cas, que veux tu faire de spécifique par rapport à ça dans ton algorithme ?

          Rien de spécial du coup, en ayant pris un peu de recul. J'étais étonné du fait que dans la version par blocs buggée, si on mettait comme taille de bloc la moitié environ du cache L1 c'est là qu'on obtenait les meilleures vitesses. D'où mon interrogation.

          Mais étant donné que la version était buggée et que tout ce qu'elle faisait c'était copier toujours les même size_block octets d'un même pointeur source à un même pointeur destination, peu étonnant qu'on obtienne les meilleures perfs quand on peut copier toutes les données d'un côté à l'autre en restant dans le cache...
          • [^] # Re: Copier "par bloc" ?

            Posté par . Évalué à 2.

            peu étonnant qu'on obtienne les meilleures perfs quand on peut copier toutes les données d'un côté à l'autre en restant dans le cache...

            Oui, je pense que tu as trouvé la vraie raison des chiffres de ce test.

Suivre le flux des commentaires

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