Génération simultanée de clés séquentielles

Question

Je travaille sur un projet qui génère un très grand nombre de chaînes de texte séquentielles, dans une boucle très serrée. Mon application fait un usage intensif des extensions d'ensemble d'instructions SIMD comme SSE et MMX, dans d'autres parties du programme, mais le générateur de clé est simple C++. La façon dont fonctionne mon générateur de clé est que j'ai une classe keyGenerator, qui contient un seul tableau de caractères qui stocke la clé en cours. Pour obtenir la clé suivante, il existe une fonction appelée "incrementKey", qui traite la chaîne comme un nombre, en ajoutant un à la chaîne, en transportant si nécessaire.

Maintenant, le problème est, le keygen est un peu un goulot d'étranglement. C'est rapide, mais ce serait bien si c'était plus rapide. L'un des plus gros problèmes est que lorsque je génère un ensemble de clés séquentielles à traiter à l'aide de mon code SSE2, je dois stocker tout l'ensemble dans un tableau, ce qui signifie que je dois générer et copier séquentiellement 12 chaînes dans un tableau, un par un, comme si:

char* keys[12]; 
for(int i = 0; i < 12; i++) 
{ 
    keys[i] = new char[16]; 
    strcpy(keys[i], keygen++); 
} 

Alors, comment pourriez-vous générer efficacement ces chaînes de texte en clair dans l'ordre? J'ai besoin d'idées pour aider à avancer. La concurrence serait bien; comme mon code est en ce moment, chaque clé successive dépend de la précédente, ce qui signifie que le processeur ne peut pas commencer à travailler sur la clé suivante tant que la clé actuelle n'a pas été complètement générée.

Voici le code correspondant au générateur de clé:

KeyGenerator.h

class keyGenerator 
{ 

public: 

    keyGenerator(unsigned long long location, characterSet* charset) 
      : location(location), charset(charset) 
    {   
     for(int i = 0; i < 16; i++) 
      key[i] = 0; 

     charsetStr = charset->getCharsetStr(); 
     integerToKey(); 
    } 

    ~keyGenerator() 
    { 
    } 

    inline void incrementKey() 
    { 
     register size_t keyLength = strlen(key); 

     for(register char* place = key; place; place++) 
     { 
      if(*place == charset->maxChar) 
      { 
       // Overflow, reset char at place 
       *place = charset->minChar; 

       if(!*(place+1)) 
       { 
        // Carry, no space, insert char 
        *(place+1) = charset->minChar; 
        ++keyLength; 

        break; 
       } 
       else 
       { 
        continue; 
       } 
      } 
      else 
      { 
       // Space available, increment char at place 
       if(*place == charset->charSecEnd[0]) *place = charset->charSecBegin[0]; 
       else if(*place == charset->charSecEnd[1]) *place = charset->charSecBegin[1]; 

       (*place)++; 

       break; 
      } 
     } 
    } 

    inline char* operator++() // Pre-increment 
    { 
      incrementKey(); 
      return key; 
    } 

    inline char* operator++(int) // Post-increment 
    { 
      memcpy(postIncrementRetval, key, 16); 
      incrementKey(); 

      return postIncrementRetval; 
    } 

    void integerToKey() 
    { 
     register unsigned long long num = location; 

     if(!num) 
     { 
      key[0] = charsetStr[0]; 
     } 
     else 
     { 
      num++; 

      while(num) 
      { 
       num--; 
       unsigned int remainder = num % charset->length; 
       num /= charset->length; 

       key[strlen(key)] = charsetStr[remainder]; 
      } 
     } 
    } 

    inline unsigned long long keyToInteger() 
    { 
     // TODO 
     return 0; 
    } 

    inline char* getKey() 
    { 
     return key; 
    } 

private: 

    unsigned long long location; 

    characterSet* charset; 
    std::string charsetStr; 

    char key[16]; 

    // We need a place to store the key for the post increment operation. 
    char postIncrementRetval[16]; 
}; 

CharacterSet.h

struct characterSet 
{ 
    characterSet() 
    { 
    } 

    characterSet(unsigned int len, int min, int max, int charsec0, int charsec1, int charsec2, int charsec3) 
    { 
     init(length, min, max, charsec0, charsec1, charsec2, charsec3); 
    } 

    void init(unsigned int len, int min, int max, int charsec0, int charsec1, int charsec2, int charsec3) 
    { 
     length = len; 
     minChar = min; 
     maxChar = max; 

     charSecEnd[0] = charsec0; 
     charSecBegin[0] = charsec1; 
     charSecEnd[1] = charsec2; 
     charSecBegin[1] = charsec3; 
    } 

    std::string getCharsetStr() 
    { 
     std::string retval; 

     for(int chr = minChar; chr != maxChar; chr++) 
     { 
      for(int i = 0; i < 2; i++) if(chr == charSecEnd[i]) chr = charSecBegin[i]; 
      retval += chr; 
     } 

     return retval; 
    } 

    int minChar, maxChar; 

    // charSec = character set section 
    int charSecEnd[2], charSecBegin[2]; 

    unsigned int length; 
}; 

Answer 1

bien .. Côté performance, tous les les nouveaux/strcpy/strmp vous blessent probablement beaucoup plus que votre keygen. Allouer votre mémoire dans un pool plus grand à la fois, puis utiliser des pointeurs à l'intérieur. Avec keygen, vous devriez éviter de vous en tenir à l'abstraction qui fuit d'une seule touche produite, produisez plutôt la quantité optimale à la fois. Des plus gros possibles.

Sur certains intervalles, vous pouvez réellement utiliser SSE/MMX pour produire les clés, au moins lorsque la chaîne est alignée et divisible par votre longueur de mot SSE/MMX. Vous pouvez également essayer de le remplir avec 0 et ensuite les décaler si la chaîne ne l'est pas. Cela ne vaut probablement pas vraiment la peine si vous n'en produisez que 16 à la fois.