التوليد المتزامن من المفاتيح المتسلسلة

Question

أنا أعمل على مشروع يولد عددًا كبيرًا جدًا من سلاسل النص المتسلسلة ، في حلقة ضيقة للغاية. يستفيد طلبي من مجموعة تعليمات SIMD مثل SSE و MMX ، في أجزاء أخرى من البرنامج ، ولكن مولد المفاتيح هو C ++.

الطريقة التي يعمل بها مولد المفاتيح الخاص بي هي أن لدي فئة keygenerator ، التي تحمل مجموعة Char واحدة تخزن المفتاح الحالي. للحصول على المفتاح التالي ، هناك وظيفة تسمى "styprementkey" ، والتي تعامل السلسلة كرقم ، وإضافة واحدة إلى السلسلة ، وتحمل عند الضرورة.

الآن ، المشكلة هي أن كجن كجن هو عنق الزجاجة إلى حد ما. إنه سريع ، لكنه سيكون لطيفًا لو كان أسرع. واحدة من أكبر المشكلات هي أنه عندما أقوم بإنشاء مجموعة من المفاتيح المتسلسلة التي يجب معالجتها باستخدام رمز 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];
};

أحرف

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 في وقت واحد فقط.