Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

  1. #21
    Rédacteur/Modérateur

    Avatar de Roland Chastain
    Homme Profil pro
    Enseignant
    Inscrit en
    décembre 2011
    Messages
    3 506
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 46
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : décembre 2011
    Messages : 3 506
    Points : 12 229
    Points
    12 229
    Billets dans le blog
    8

    Par défaut

    J'ai fait un programme qui compare les performances de trois fonctions : la fonction actuellement utilisée dans le code de mon moteur d'échecs, une autre que j'ai écrite et une autre basée sur la fonction BitCount en Assembleur.

    Code Delphi : Sélectionner tout - Visualiser dans une fenêtre à part
    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
     
    {$asmMode intel}
     
    uses
      SysUtils, Damier, Tables;
     
    type
      TFonction = function(const ADamier: TDamier): integer;
     
    function CompteCasesAllumees2(const ADamier: TDamier): integer;
    const
      CZero = TDamier(0);
      CUn   = TDamier(1);
    var
      LDamier: TDamier;
    begin
      result := 0;
      LDamier := ADamier;
      while LDamier <> CZero do
      begin
        if LDamier and CUn = CUn then
          Inc(result);
        LDamier := LDamier shr 1;
      end;
    end;
     
    function BitCount(var n : Int64): byte; assembler; nostackframe; inline; // Testé en 32 et 64 bits
    asm
       popcnt edx,   dword ptr [n]        // 32 bits eax = @n,  en 64 bits rcx = @n 
       popcnt eax,   dword ptr [n+4]   
       add    eax,    edx                   
    end;
     
    function CompteCasesAllumees3(const ADamier: TDamier): integer;
    var
      LDamier: TDamier;
    begin
      LDamier := ADamier;
      result := BitCount(LDamier);
    end;
     
    procedure Test(ADamier: TDamier; AFonction: TFonction);
    var
      i, res: integer;
      t: cardinal;
    begin
      t := GetTickCount64;
      for i := 1 to 1000000 do
        res := AFonction(ADamier);
      WriteLn(GetTickCount64 - t);
    end;
     
    const
      CCavaliers = %0100001000000000000000000000000000000000000000000000000001000010;
     
    begin
      Test(CCavaliers, @CompteCasesAllumees);
      Test(CCavaliers, @CompteCasesAllumees2);
      Test(CCavaliers, @CompteCasesAllumees3);
    end.

    La différence est si énorme que je me demande si je ne me suis pas trompé quelque part !


    Le test a été fait avec FPC 32 bits. Ci-joint le code source complet.
    Fichiers attachés Fichiers attachés

  2. #22
    Rédacteur/Modérateur

    Avatar de Roland Chastain
    Homme Profil pro
    Enseignant
    Inscrit en
    décembre 2011
    Messages
    3 506
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 46
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : décembre 2011
    Messages : 3 506
    Points : 12 229
    Points
    12 229
    Billets dans le blog
    8

    Par défaut

    La fonction non compatible 32 bits va encore plus vite !

  3. #23
    Rédacteur/Modérateur

    Avatar de Roland Chastain
    Homme Profil pro
    Enseignant
    Inscrit en
    décembre 2011
    Messages
    3 506
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 46
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : décembre 2011
    Messages : 3 506
    Points : 12 229
    Points
    12 229
    Billets dans le blog
    8

    Par défaut

    Pour revenir à la fonction BitScanForward en Assembleur, j'ai appliqué la correction que vous avez proposée. Ça ne donne pas les bons résultats, avec aucun compilateur.

    Comme vous sembliez dire que la fonction originale n'était pas très bien écrite, comment l'écririez-vous ?

  4. #24
    Membre actif

    Homme Profil pro
    Directeur de projet
    Inscrit en
    mai 2013
    Messages
    21
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Administration - Collectivité locale

    Informations forums :
    Inscription : mai 2013
    Messages : 21
    Points : 257
    Points
    257

    Par défaut Vite

    Bonjour Roland,

    Une manière simple de se faire une idée est de regarder en mode debug la fenêtre assembleur et de compter les lignes assembleurs dans les divers cas. Ça donne une bonne idée du rapport de performances (c'est un peu au doigts mouillé mais le ratio est souvent très proche de la réalité - avant division on ajoute aux deux 2x(le nombre d'argument +1) pour tenir compte du chargement des arguments et de l'appel de fonction).

    Pour le comptage de bits à 1, le ratio entre la solution pascal (optimisée par masquages qui est environ 2x plus rapide que par décalages) et asm est de l'ordre de 20x (près du double en asm 64 bits). Mais nous parlons de temps qui sont de l'ordre de 50 à 150 ns dans le cas le plus défavorable. Il faut donc qu'il y ait un grand nombre d’occurrences pour que la différence soit humainement perceptible.

    Ci-dessous les versions (testées) en pascal utilisant les masquages :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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
     
    function BitCount(X: Int64): Byte;
    begin
       X := (X and $5555555555555555) + ((X shr  1) and $5555555555555555);
       X := (X and $3333333333333333) + ((X shr  2) and $3333333333333333);
       X := (X and $0F0F0F0F0F0F0F0F) + ((X shr  4) and $0F0F0F0F0F0F0F0F);
       X := (X and $00FF00FF00FF00FF) + ((X shr  8) and $00FF00FF00FF00FF);
       X := (X and $0000FFFF0000FFFF) + ((X shr 16) and $0000FFFF0000FFFF);
       X := (X and $00000000FFFFFFFF) + ((X shr 32) and $00000000FFFFFFFF);
      result := Byte(X);
    end;
     
    function BitScanForward(X : Int64): Integer;
    var Y : int64;
    begin
       if X = 0 then Exit(-1);
       Result := 0;
       Y := X and $00000000FFFFFFFF; if Y = 0 then Result += 32 else X := Y;
       Y := X and $0000FFFF0000FFFF; if Y = 0 then Result += 16 else X := Y;
       Y := X and $00FF00FF00FF00FF; if Y = 0 then Result +=  8 else X := Y;
       Y := X and $0F0F0F0F0F0F0F0F; if Y = 0 then Result +=  4 else X := Y;
       Y := X and $3333333333333333; if Y = 0 then Result +=  2 else X := Y;
       if X and $5555555555555555 = 0 then Result +=  1;
    end;
     
    function BitScanReverse(X: Int64): Integer;
    var Y : int64;
    begin
       if X = 0 then Exit(-1);
       Result := 63;
       Y := X and $FFFFFFFF00000000; if Y = 0 then Result -= 32 else X := Y;
       Y := X and $FFFF0000FFFF0000; if Y = 0 then Result -= 16 else X := Y;
       Y := X and $FF00FF00FF00FF00; if Y = 0 then Result -=  8 else X := Y;
       Y := X and $F0F0F0F0F0F0F0F0; if Y = 0 then Result -=  4 else X := Y;
       Y := X and $CCCCCCCCCCCCCCCC; if Y = 0 then Result -=  2 else X := Y;
       if   X and $AAAAAAAAAAAAAAAA = 0 then Result -= 1;
    end;
    Dans le code mis à disposition, il y a des fonctions identiques FirstOne/BitScanForward et LastOne/BitScanReverse. C'est normal ?

    Salutations
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  5. #25
    Rédacteur/Modérateur

    Avatar de Roland Chastain
    Homme Profil pro
    Enseignant
    Inscrit en
    décembre 2011
    Messages
    3 506
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 46
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : décembre 2011
    Messages : 3 506
    Points : 12 229
    Points
    12 229
    Billets dans le blog
    8

    Par défaut

    Merci beaucoup pour les explications et pour le code. J'ai hâte de l'essayer.

    Cependant dans mon message précédent, je parlais de la fonction BitScanForward en Assembleur. Je me demandais comment vous l'écririez en Assembleur, sur le modèle de la fonction BitCount que vous avez proposée (qui marche "du tonnerre" et qui est acceptée par tous les compilateurs, contrairement à la version originale).

    Citation Envoyé par Guesset Voir le message
    Dans le code mis à disposition, il y a des fonctions identiques FirstOne/BitScanForward et LastOne/BitScanReverse. C'est normal ?
    Les fonctions FirstOne et LastOne ne sont pas utilisées dans le programme. Je n'avais pas remarqué qu'elles étaient identiques à BitScanForward et BitScanReverse. Je ne sais pas pourquoi l'auteur du programme les a laissées dans le code.

    Bon, je marque la discussion comme résolue, puisque j'ai eu ce dont j'avais besoin et même plus. Je reviendrai quand même donner les résultats de mes essais pour les nouvelles fonctions en Pascal.

  6. #26
    Rédacteur/Modérateur

    Avatar de Roland Chastain
    Homme Profil pro
    Enseignant
    Inscrit en
    décembre 2011
    Messages
    3 506
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 46
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : décembre 2011
    Messages : 3 506
    Points : 12 229
    Points
    12 229
    Billets dans le blog
    8

    Par défaut

    Voici les résultats :

    Code X : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    Pascal     Roland 1      : 1985 ms
    Pascal     Roland 2      :  641 ms
    Pascal     Guesset       :   62 ms
    Assembleur Guesset 32/64 :   47 ms
    Assembleur Guesset 64    :   16 ms

    Votre fonction en Pascal est juste dix fois plus rapide que la mienne.

    Et presque aussi rapide que les fonctions en Assembleur.

    Je vais l'adopter, même si je ne comprends pas trop (pas du tout, en fait) comment elle fonctionne.

    Merci !

  7. #27
    Membre actif

    Homme Profil pro
    Directeur de projet
    Inscrit en
    mai 2013
    Messages
    21
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Administration - Collectivité locale

    Informations forums :
    Inscription : mai 2013
    Messages : 21
    Points : 257
    Points
    257

    Par défaut Résolue

    Bonjour Roland,

    J'espère que nous pourrons bénéficier de ton travail de mise à niveau de cette application (au moins en voir l'exécutable).

    Les technique de masquage sont classiques même si elles ne sont pas très faciles à lire. Le principe est d'utiliser des masques pour paralléliser des fragment d'opération (bit, duo, quartet, octet, et plus si affinités).

    Bonne continuation.
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  8. #28
    Rédacteur/Modérateur

    Avatar de Roland Chastain
    Homme Profil pro
    Enseignant
    Inscrit en
    décembre 2011
    Messages
    3 506
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 46
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : décembre 2011
    Messages : 3 506
    Points : 12 229
    Points
    12 229
    Billets dans le blog
    8

    Par défaut

    Citation Envoyé par Guesset Voir le message
    J'espère que nous pourrons bénéficier de ton travail de mise à niveau de cette application (au moins en voir l'exécutable).
    Avec plaisir. Cependant j'ai eu la désagréable surprise de constater que l'application est boguée. L'ordinateur joue des coups illégaux, annonce des mats qui n'existent pas... Alors je pourrais chercher les bogues mais je ne suis pas sûr d'en venir à bout, étant donné que le code est plein d'opérations binaires obscures pour moi. Je vais quand même essayer d'y jeter un œil et éventuellement j'ouvrirai une discussion dans le forum Pascal ou Delphi. En attendant vous pouvez trouver l'application originale . Tiens, en relisant la discussion de 2015, je m'aperçois que le bogue avait déjà été signalé...

    Quoi qu'il en soit les fonctions que vous avez proposées ne seront pas perdues. Je pense les intégrer dans la prochaine version de mon propre programme, qui est lui aussi basé sur les bitboards.

+ Répondre à la discussion
Cette discussion est résolue.
Page 2 sur 2 PremièrePremière 12

Discussions similaires

  1. Réponses: 3
    Dernier message: 30/12/2016, 21h59
  2. Utiliser une fonction ec C dans un code assembleur (ARM)
    Par serialC dans le forum Autres architectures
    Réponses: 1
    Dernier message: 26/12/2012, 15h51
  3. Réécriture d'une fonction
    Par gedeon555 dans le forum Zend Framework
    Réponses: 1
    Dernier message: 26/06/2009, 23h27
  4. Réponses: 0
    Dernier message: 21/01/2009, 00h16
  5. Réponses: 6
    Dernier message: 21/09/2007, 14h18

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo