Параллельное создание последовательных ключей

Question

Я работаю над проектом, который генерирует очень большое количество последовательных текстовых строк в очень узком цикле. Мое приложение активно использует расширения набора команд SIMD, такие как SSE и MMX, в других частях программы, но генератор ключей - это простой C++.

Как работает мой генератор ключей, у меня есть класс keyGenerator, который содержит единственный массив символов, который хранит текущий ключ. Чтобы получить следующий ключ, существует функция, называемая «incrementKey», которая обрабатывает строку как число, добавляя ее в строку, сохраняя при необходимости.

Теперь проблема заключается в том, что кейген скорее всего является узким местом. Это быстро, но было бы неплохо, если бы это было быстрее. Одна из самых больших проблем заключается в том, что когда я генерирую набор последовательных ключей для обработки с использованием кода SSE2, я должен иметь весь набор, хранящийся в массиве, что означает, что я должен последовательно генерировать и копировать 12 строк в массив, один за другим, так:

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

Итак, как бы вы эффективно сгенерировали эти строки простого текста? Мне нужны идеи, чтобы помочь двигаться вперед. Параллельность была бы приятной; поскольку мой код прямо сейчас, каждый последующий ключ зависит от предыдущего, а это означает, что процессор не может начать работу над следующей клавишей до тех пор, пока текущий не будет полностью сгенерирован.

Вот код отношение к ключевому генератору:

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

Ну .. С точки зрения производительности, все новые/strcpy/strmp, вероятно, причиняют вам боль намного больше, чем ваш кейген.

Выделите память в большом пуле за раз, а затем используйте в ней указатели.

С помощью keygen вы должны избегать прилипания абстракции одиночной клавиши, производящей вместо этого оптимальную сумму за раз. Вероятно, большие кратные.

С определенными интервалами вы можете использовать SSE/MMX для создания ключей, по крайней мере, когда строка выровнена и делится на вашу длину слова SSE/MMX. Вы также можете попытаться наложить его на 0, а затем сдвинуть их, если строка отсутствует. Вероятно, это не стоит усилий, если вы генерируете только 16 за раз.