Explication de code (memset).

Version imprimable

Bonjour,

Je suis tomber sur le code d'une fonction memset en téléchargeant la libelf (http://directory.fsf.org/wiki/Libelf).

Voila a quoi ca resemble :

Code:

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
#if HAVE_CONFIG_H
# include <config.h>
#endif /* HAVE_CONFIG_H */
 
#ifndef lint
static const char rcsid[] = "@(#) $Id: memset.c,v 1.10 2005/05/21 15:39:24 michael Exp $";
#endif /* lint */
 
#include <stddef.h>     /* for size_t */
#include <sys/types.h>
 
void*
_elf_memset(void *s, int c, size_t n) {
    char *t = (char*)s;
 
    if (n) {
        switch (n % 8u) {
            do {
                n -= 8;
                default:
                case 0: *t++ = (char)c;
                case 7: *t++ = (char)c;
                case 6: *t++ = (char)c;
                case 5: *t++ = (char)c;
                case 4: *t++ = (char)c;
                case 3: *t++ = (char)c;
                case 2: *t++ = (char)c;
                case 1: *t++ = (char)c;
            }
            while (n > 8);
        }
    }
    return s;
}

Je voulais savoir, quel interret de faire ca, alors que la fonction pourrait ressembler a ca ?

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void	*memset(void *s, int c, size_t n)
{
  char	        *m;
  size_t        i;
 
  c = m;
  i = 0;
  while (i < n)
    {
      m[i] = (char)c
      i++;
    }
  return (s);
}

J'imagine que le mec qui a écrit ça avait une bonne raison de le faire, mais je comprend pas l'avantage.

Si quelqu'un a l'explication :)

12/06/2012, 08h40
Bktero

Je ne vois pas trop l'intérêt de ce code, comme ça au saut du lit...

En revanche, je suis carrément sûr que tu ne voulais pas écrire : c = m;
12/06/2012, 09h01
fregolo52

Wahou !!!

Un do ... while entre un swtich .. case.

A part le fait de diviser le nombre de while par 8 (ou presque), je ne vois pas trop l'intérêt. Mais c'est sûrement plus performant que ton code.

J'ai modifié ta fonction en ça :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
void	*memset(void *s, int c, size_t n)
{
  char	        *m = (char*) s;
  size_t        i = 0;
 
  while (i < n)
    {
      m[i] = (char)c;
      i++;
    }
  return (s);
}

Et j'ai comparé les codes assembleurs des 2 fonctions avec CodeBlocks 10.3 sous Windows XP. C'est la première fois que je le fais, alors je me suis peut-être trompé mais j'obtiens :

Pour ta fonction :

Code:

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
Project title : developpez
Project path  : d:\Documents and Settings\pgradot\Mes documents\Tools SD\A voir\developpez\

Frame function: memset (d:\Documents and Settings\pgradot\Mes documents\Tools SD\A voir\developpez\your.c:6)
Frame address : 0022FF30
--------------------------------------------------------------------------------
0040135C	push   %ebp
0040135D	mov    %esp,%ebp
0040135F	sub    $0x10,%esp
00401362	mov    0x8(%ebp),%eax
00401365	mov    %eax,-0x8(%ebp)
00401368	movl   $0x0,-0x4(%ebp)
0040136F	jmp    0x401381 <memset+37>
00401371	mov    -0x4(%ebp),%eax
00401374	mov    -0x8(%ebp),%edx
00401377	add    %eax,%edx
00401379	mov    0xc(%ebp),%eax
0040137C	mov    %al,(%edx)
0040137E	incl   -0x4(%ebp)
00401381	mov    -0x4(%ebp),%eax
00401384	cmp    0x10(%ebp),%eax
00401387	jb     0x401371 <memset+21>
00401389	mov    0x8(%ebp),%eax
0040138C	leave
0040138D	ret

Et pour la sienne :

Code:

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
Project title : developpez
Project path  : d:\Documents and Settings\pgradot\Mes documents\Tools SD\A voir\developpez\

Frame function: elf_memset (d:\Documents and Settings\pgradot\Mes documents\Tools SD\A voir\developpez\his.c:6)
Frame address : 0022FF30
--------------------------------------------------------------------------------
00401390	push   %ebp
00401391	mov    %esp,%ebp
00401393	sub    $0x10,%esp
00401396	mov    0x8(%ebp),%eax
00401399	mov    %eax,-0x4(%ebp)
0040139C	cmpl   $0x0,0x10(%ebp)
004013A0	je     0x40142c <elf_memset+156>
004013A6	mov    0x10(%ebp),%eax
004013A9	and    $0x7,%eax
004013AC	cmp    $0x7,%eax
004013AF	ja     0x4013be <elf_memset+46>
004013B1	mov    0x403024(,%eax,4),%eax
004013B8	jmp    *%eax
004013BA	subl   $0x8,0x10(%ebp)
004013BE	mov    0xc(%ebp),%eax
004013C1	mov    %al,%dl
004013C3	mov    -0x4(%ebp),%eax
004013C6	mov    %dl,(%eax)
004013C8	incl   -0x4(%ebp)
004013CB	mov    0xc(%ebp),%eax
004013CE	mov    %al,%dl
004013D0	mov    -0x4(%ebp),%eax
004013D3	mov    %dl,(%eax)
004013D5	incl   -0x4(%ebp)
004013D8	mov    0xc(%ebp),%eax
004013DB	mov    %al,%dl
004013DD	mov    -0x4(%ebp),%eax
004013E0	mov    %dl,(%eax)
004013E2	incl   -0x4(%ebp)
004013E5	mov    0xc(%ebp),%eax
004013E8	mov    %al,%dl
004013EA	mov    -0x4(%ebp),%eax
004013ED	mov    %dl,(%eax)
004013EF	incl   -0x4(%ebp)
004013F2	mov    0xc(%ebp),%eax
004013F5	mov    %al,%dl
004013F7	mov    -0x4(%ebp),%eax
004013FA	mov    %dl,(%eax)
004013FC	incl   -0x4(%ebp)
004013FF	mov    0xc(%ebp),%eax
00401402	mov    %al,%dl
00401404	mov    -0x4(%ebp),%eax
00401407	mov    %dl,(%eax)
00401409	incl   -0x4(%ebp)
0040140C	mov    0xc(%ebp),%eax
0040140F	mov    %al,%dl
00401411	mov    -0x4(%ebp),%eax
00401414	mov    %dl,(%eax)
00401416	incl   -0x4(%ebp)
00401419	mov    0xc(%ebp),%eax
0040141C	mov    %al,%dl
0040141E	mov    -0x4(%ebp),%eax
00401421	mov    %dl,(%eax)
00401423	incl   -0x4(%ebp)
00401426	cmpl   $0x8,0x10(%ebp)
0040142A	ja     0x4013ba <elf_memset+42>
0040142C	mov    0x8(%ebp),%eax
0040142F	leave
00401430	ret

Je pige encore moins l'intérêt..... :?

J'ai fait une version "Kernighan and Ritchie compliant" encore plus courte :

Code:

1
2
3
4
5
6
7
void* bktero_memset(void *s, int c, size_t n)
{
  while (n>0)
      *( (char*)s + n-- -1 ) = (char)c;
 
  return (s);
}

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Project title : developpez
Project path  : d:\Documents and Settings\pgradot\Mes documents\Tools SD\A voir\developpez\

Frame function: bktero_memset (d:\Documents and Settings\pgradot\Mes documents\Tools SD\A voir\developpez\bktero.c:5)
Frame address : 0022FF30
--------------------------------------------------------------------------------
004014C8	push   %ebp
004014C9	mov    %esp,%ebp
004014CB	jmp    0x4014df <bktero_memset+23>
004014CD	mov    0x8(%ebp),%eax
004014D0	mov    0x10(%ebp),%edx
004014D3	dec    %edx
004014D4	lea    (%eax,%edx,1),%edx
004014D7	mov    0xc(%ebp),%eax
004014DA	mov    %al,(%edx)
004014DC	decl   0x10(%ebp)
004014DF	cmpl   $0x0,0x10(%ebp)
004014E3	jne    0x4014cd <bktero_memset+5>
004014E5	mov    0x8(%ebp),%eax
004014E8	leave
004014E9	ret

La taille de l'assembleur est-elle complètement proportionnelle à la contre-performance ?

12/06/2012, 10h23
boboss123

Salut,

Citation:

Envoyé par Bktero

La taille de l'assembleur est-elle complètement proportionnelle à la contre-performance ?

Pas forcement. Certaines commandes ASM peuvent nécessiter plusieurs cycles pour être exécutées (voir la doc ASM du CPU utilisé) mais en général c'est deux cycles max par commandes (en général ce sont des commandes de saut d'adresse).
Aussi il faut analyser les commandes de type "jump" pour voir si tu ne rappelles pas plusieurs fois le même code (ce qui fait qu'au final tu exécutes plus de commandes) => ce qui n'est a priori pas le cas dans ton code.

=> donc en gros, il faut que tu comprennes l'ASM pour être sure que ton programme soit plus performant
12/06/2012, 10h29
gulain

C'est une variante de https://en.wikipedia.org/wiki/Duff%27s_device.
12/06/2012, 12h25
Bktero

J'y connais pas grand chose en assembleur alors impossible pour moi de comprendre pourquoi autant de lignes avec 3 sauts est plus efficace que moins de lignes avec 2 sauts. :(

Je me rends compte que j'avais foiré mon lien. Je l'ai corrigé.

En gros, ça permet de dérouler la boucle. Voir http://stackoverflow.com/questions/5...fs-device-work, que je recopie en dessous :

Citation:

This being my AHA moment:

Code:

1
2
3
4
 
for (i = 0; i < len; ++i) {
    HAL_IO_PORT = *pSource++;
}

becomes:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
 
int n = len / 8;
for (i = 0; i < n; ++i) {
    HAL_IO_PORT = *pSource++;
    HAL_IO_PORT = *pSource++;
    HAL_IO_PORT = *pSource++;
    HAL_IO_PORT = *pSource++;
    HAL_IO_PORT = *pSource++;
    HAL_IO_PORT = *pSource++;
    HAL_IO_PORT = *pSource++;
    HAL_IO_PORT = *pSource++;
}

:) becomes:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
int n = (len + 8 - 1) / 8;
switch (len % 8) {
    case 0: do { HAL_IO_PORT = *pSource++;
    case 7: HAL_IO_PORT = *pSource++;
    case 6: HAL_IO_PORT = *pSource++;
    case 5: HAL_IO_PORT = *pSource++;
    case 4: HAL_IO_PORT = *pSource++;
    case 3: HAL_IO_PORT = *pSource++;
    case 2: HAL_IO_PORT = *pSource++;
    case 1: HAL_IO_PORT = *pSource++;
               } while (--n > 0);
}

Et donc au lieu de faire N tours de boucle, on en fait N/8

Comme je suis un peu un bouledogue, j'ai utilisé gproof pour la 1ère fois de ma vie (il en existe une version Windows dans les MinGW binutils d'ailleurs).

J'ai fait le programme suivant :

Code:

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
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stddef.h>     /* for size_t */
#include <sys/types.h>
 
 
void* bktero_memset(void *s, int c, size_t n)
{
  while (n>0)
      *( (char*)s + n-- -1 ) = (char)c;
 
  return (s);
}
 
 
void* elf_memset(void *s, int c, size_t n)
{
    char *t = (char*)s;
 
    if (n) {
        switch (n % 8u) {
            do {
                n -= 8;
                default:
                case 0: *t++ = (char)c;
                case 7: *t++ = (char)c;
                case 6: *t++ = (char)c;
                case 5: *t++ = (char)c;
                case 4: *t++ = (char)c;
                case 3: *t++ = (char)c;
                case 2: *t++ = (char)c;
                case 1: *t++ = (char)c;
            }
            while (n > 8);
        }
    }
    return s;
}
 
 
#define TAILLE_MEM 100000
#define LONG_BOUCLE 10000
int main(void)
{
    char *dest = malloc(TAILLE_MEM);
    int i=0;
 
 
    for(i=0;i<LONG_BOUCLE;i++)
    {
        bktero_memset(dest, 0, TAILLE_MEM);
        bktero_memset(dest, 'a', TAILLE_MEM);
        bktero_memset(dest, 'b', TAILLE_MEM);
        bktero_memset(dest, 'c', TAILLE_MEM);
        bktero_memset(dest, 'd', TAILLE_MEM);
 
        elf_memset(dest, 0, TAILLE_MEM);
        elf_memset(dest, 'a', TAILLE_MEM);
        elf_memset(dest, 'b', TAILLE_MEM);
        elf_memset(dest, 'c', TAILLE_MEM);
        elf_memset(dest, 'd', TAILLE_MEM);
 
    }
 
 
    free(dest);
 
    return i;
}

Je l'ai compilé avec -g et -pg, je l'ai exécuté et j'ai fait mangé l'exécutable et le fichier gmon.out à gproof. Voici le résultat (avec l'option -b) :

Code:

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
Flat profile:
 
Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  us/call  us/call  name    
 50.27     13.26    13.26    50000   265.10   265.10  elf_memset
 49.73     26.37    13.12    50000   262.30   262.30  bktero_memset
 
			Call graph
 
 
granularity: each sample hit covers 4 byte(s) for 0.04% of 26.37 seconds
 
index % time    self  children    called     name
                                                 <spontaneous>
[1]    100.0    0.00   26.37                 main [1]
               13.26    0.00   50000/50000       elf_memset [2]
               13.12    0.00   50000/50000       bktero_memset [3]
-----------------------------------------------
               13.26    0.00   50000/50000       main [1]
[2]     50.3   13.26    0.00   50000         elf_memset [2]
-----------------------------------------------
               13.12    0.00   50000/50000       main [1]
[3]     49.7   13.12    0.00   50000         bktero_memset [3]
-----------------------------------------------
 
Index by function name
 
   [3] bktero_memset           [2] elf_memset

Ce qui voudrait dire que mon code serait un (très) petit peu plus rapide.... :oops:

Je m'attendais au résultat inverse pourtant... :roll:

12/06/2012, 18h16
gulain

De mon coté (sous cygwin ou dans une VM debian), j'ai :

- en non optimisé sous cygwin :
21 s pour bktero, 12 s pour elf ;

- en non optimisé sous VM Debian:
14s pour bktero, 13 s pour elf ;

- en optimisé (-O2) sous cygwin :
1,55 s pour bktero et 1,88 pour elf ;

en optimisé (-O2) sous cygwin :
1,85 s pour bktero et 1,91 pour elf.

En -O1, c'est bktero qui gagne aussi :ccool:. Je suppose que les compilos ont fait des progrès, et que ce genre d'optimisation n'a plus vraiment de sens aujourd'hui (enfin, ça doit dépendre du matériel/compilo/optionsducompilo).

En vérifiant, c'est plus ou moins écrit dans l'article Wikipedia : il y a des cas (XFree86 Server) où enlever ce genre de code a permis d'améliorer les perfs.
12/06/2012, 19h18
gheaeckkseqrz

Merci pour toutes ces réponses,

Pour l'instant je préoccupe pas d'optimiser mes programmes a ce point la (projets scolaire qui ne seront plus jamais exécutés après la soutenance), mais c'est toujours intéressant de voir des astuces comme celle la.
13/06/2012, 09h23
Bktero

@gulain : j'ai aussi fait des tests en mettant des -O et je crois que tel est présenté le programme ci-dessus, ma version était toujours légèrement plus rapide.

En revanche, j'ai essayé de faire des tests, toujours en variant le niveau d'optimisation, mais surtout en variant la taille de la zone à memseter. Et là, j'ai des résultats qui partent dans tous les sens..... Je crois quand même que dans l'ensemble, si la zone à allouer est faible, alors la version Duff's Device est plus rapide. C'est moins vrai quand la taille augmente. Je trouve ça bizarre encore une fois...J'essayerai au calme sur un PC avec Ubuntu et une version de gprof à jour.