Generazione concomitante di chiavi sequenziali

Question

Sto lavorando a un progetto che genera un numero molto elevato di stringhe di testo sequenziali, in un ciclo molto stretto. La mia applicazione fa un uso intenso delle estensioni di set di istruzioni SIMD come SSE e MMX, in altre parti del programma, ma il generatore chiave è C ++ semplice.

Il modo in cui funziona il mio generatore chiave è che ho una classe KeyGenerator, che contiene un singolo array di char che memorizza la chiave corrente. Per ottenere la chiave successiva, c'è una funzione chiamata "IncrementKey", che tratta la stringa come un numero, aggiungendo una alla stringa, trasportando dove necessario.

Ora, il problema è che il keygen è in qualche modo un collo di bottiglia. È veloce, ma sarebbe bello se fosse più veloce. Uno dei maggiori problemi è che quando sto generando una serie di chiavi sequenziali da elaborare usando il mio codice SSE2, devo avere l'intero set memorizzato in un array, il che significa che devo generare e copiare sequenzialmente 12 stringhe in Array, uno per uno, come così:

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

Quindi, come genereresti in modo efficiente queste stringhe in chiaro in ordine? Ho bisogno di alcune idee per aiutare a muoverlo. La concorrenza sarebbe carina; Poiché il mio codice è in questo momento, ogni chiave successiva dipende da quella precedente, il che significa che il processore non può iniziare a lavorare sulla chiave successiva fino a quando quella attuale non è stata completamente generata.

Ecco il codice rilevante per il generatore chiave:

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];
};

Personaggit.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

Bene .. Per quanto riguarda le prestazioni, tutti i nuovi/strcpy/strmp probabilmente ti fanno male molto più del tuo keygen.

Assegna la memoria in un pool più grande alla volta e quindi usa i puntatori al suo interno.

Con Keygen, dovresti evitare di attenersi all'astrazione di perdita di una chiave singola prodotta, produrre invece la quantità ottimale alla volta. Forse multipli più grandi.

A determinati intervalli è possibile utilizzare effettivamente SSE/MMX per produrre i tasti, almeno quando la stringa è allineata ed è divisibile dalla lunghezza delle parole SSE/MMX. Potresti anche provare a colpirlo con 0 e quindi spostarli se la corda non lo è. Probabilmente non vale davvero lo sforzo se genera solo 16 alla volta.