シーケンシャルキーの同時生成

Question

非常にタイトなループで、非常に多くのシーケンシャルテキスト文字列を生成するプロジェクトに取り組んでいます。私のアプリケーションでは、プログラムの他の部分でSSEやMMXなどのSIMD命令セット拡張機能を大量に使用していますが、キージェネレーターはプレーンC ++です。

私のキージェネレーターの動作方法は、現在のキーを保存する単一のchar配列を保持するKeygeneratorクラスを持っていることです。次のキーを取得するには、「incrementKey」と呼ばれる関数があり、文字列を数字として扱い、必要に応じて文字列に追加します。

さて、問題は、keygenはややボトルネックのようなものです。それは速いですが、それがより速いならいいでしょう。最大の問題の1つは、SSE2コードを使用して処理するシーケンシャルキーのセットを生成している場合、セット全体を配列に保存する必要があることです。つまり、12文字列を順次生成してコピーする必要があります。アレイ、1つずつ、そうです：

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よりもはるかにあなたを傷つけているでしょう。

一度に大きなプールでメモリを割り当ててから、その中のポインターを使用します。

keygenを使用すると、生成された単一のキーの漏れの抽象化に固執することを避け、代わりに一度に最適な量を生成する必要があります。おそらく大きな倍数。

特定の間隔で、実際にSSE/MMXを使用してキーを生成することができます。少なくとも文字列が揃っていて、SSE/MMXワードの長さによって分割可能である場合は、キーを生成できます。また、0でパッドしてから、文字列がない場合は離れてシフトしようとすることもできます。あなたが一度に16しか生成しないなら、それはおそらく努力する価値がないでしょう。