Более быстрая Строка GetHashCode (например, использование Многоядерного или GPU)

Вы можете распараллелить это, но проблема у вас столкнется с тем, что потоки, CUDA и т.д. имеют накладные расходы, связанные с ними. Даже если вы используете пул потоков, если ваши строки не очень большие, скажем, типичная строка составляет 128-256 символов (возможно, меньше, чем это), вы, вероятно, все равно будете делать каждый вызов этой функции дольше, чем это было изначально. .

Итак, если бы вы имели дело с очень большими струнами, тогда да, это улучшило бы ваше время.

Я думаю, что все предложенные вами подходы очень неэффективны по сравнению с текущей реализацией.

Использование графического процессора: Строковые данные необходимо передать в графический процессор, а результат - обратно, что занимает много времени. Графические процессоры очень быстрые, но только при сравнении вычислений с плавающей запятой, которые здесь не используются. Все операции выполняются с целыми числами, для которых мощность процессора x86 приличная.

Использование другого ядра процессора: Это потребует создания отдельного потока, блокировки памяти и синхронизации потока, запрашивающего хэш-код. Возникающие накладные расходы просто перевешивают преимущества параллельной обработки.

Если вы захотите вычислить значения хэша тысяч строк за один раз, все может выглядеть немного иначе, но я не могу представить сценарий, в котором это оправдало бы реализацию более быстрый GetHashCode () .

Учитывая, что строки неизменяемы, первое, что я хотел бы рассмотреть, это кеширование возвращаемого результата.

Один из способов ускорить выполнение функции - это принять во внимание особые случаи. Функция с входными данными переменного размера имеет особые случаи, зависящие от размера.

Работа в параллельном режиме имеет смысл только тогда, когда затраты на параллельную работу меньше, чем усиление, и для такого рода вычислений вероятно что струна должна быть достаточно большой, чтобы преодолеть стоимость разветвления параллельного потока. Но реализовать это несложно; в основном вам нужен тест для этого. Длина превышает эмпирически определенный порог, а затем разветвление нескольких потоков для вычисления хеши на подстроках, с последним шагом, объединяющим подхеши в последний хеш. Реализация оставлена ​​читателю.

Современные процессоры также имеют инструкции SIMD, которые могут обрабатывать до до 32 (или 64) байтов в одной инструкции. Это позволит вам обрабатывать строку 32 (16-битный символ) кусками в один-два Инструкции SIMD на блок; а затем сложите 64-байтовый результат в один хэш-код в конце. Вероятно, это будет очень быстро для струн любого разумного размера. Реализация этого из C # сложнее, потому что виртуальную машину не ожидаешь для обеспечения легкого (или портативного) доступа к инструкциям SIMD что вам нужно. Реализация также оставлена ​​читателю. РЕДАКТИРОВАТЬ: Другой ответ предполагает, что система Mono предоставляет Доступ к инструкции SIMD.

Сказав это, представленная конкретная реализация довольно глупая. Ключевое наблюдение заключается в том, что цикл проверяет предел дважды на каждой итерации. Эту проблему можно решить, предварительно проверив случаи конечных условий, и выполнение цикла, который выполняет правильное количество итераций. Можно добиться большего, используя Устройство Даффса чтобы перейти в развернутый цикл из N итераций. Это избавляет от накладные расходы на проверку ограничения цикла для N-1 итераций. Эта модификация было бы очень просто и, несомненно, стоило бы усилий для реализации.

РЕДАКТИРОВАТЬ: Вы также можете объединить идею SIMD и идею разворачивания цикла, чтобы включить обработку многих фрагментов из 8/16 символов в нескольких инструкциях SIMD.

Для языков, которые не могут переходить в циклы, можно выполнить эквивалент Устройство Даффа, просто сняв первоначальные футляры. Выстрел в как перекодировать исходный код с использованием подхода отслаивания цикла:

    public override unsafe int GetHashCode()
    {
        fixed (char* str = ((char*) this))
        {
            const int N=3; // a power of two controlling number of loop iterations
            char* chPtr = str;
            int num = 0x15051505;
            int num2 = num;
            int* numPtr = (int*) chPtr;
            count = this.length;
            unrolled_iterations = count >> (N+1); // could be 0 and that's OK
            for (int i = unrolled_iterations; i > 0; i--)
            {
               // repeat 2**N times
               { num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];
                 num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[1]; }
               { num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[2];
                 num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[3]; }
               { num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[4];
                 num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[5]; }
               { num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[6];
                 num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[7]; }
               { num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[8];
                 num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[9]; }
               { num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[10];
                 num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[11]; }
               { num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[12];
                 num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[13]; }
               { num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[14];
                 num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[15]; }
               numPtr += 16;
            }
            if (count & ((1<<N)-1))
            {
               { num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];
                 num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[1]; }
               { num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[2];
                 num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[3]; }
               { num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[4];
                 num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[5]; }
               { num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[6];
                 num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[7]; }
               numPtr += 8;
            }
            if (count & ((1<<(N-1))-1))
            {
               { num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];
                 num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[1]; }
               { num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[2];
                 num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[3]; }
               numPtr += 4;
            }
            if (count & ((1<<(N-2)-1))
            {
               { num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];
                 num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[1]; }
               numPtr += 2;
            }
            // repeat N times and finally:
            if { count & (1) }
            {
               { num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];
               // numPtr += 1;
            }

            return (num + (num2 * 0x5d588b65));
        }
    }

Я не компилировал и не тестировал этот код, но идея верна. Это зависит от компилятора, выполняющего разумное сворачивание констант и адресная арифметика.

Я попытался закодировать это, чтобы сохранить точное хеш-значение оригинала, но ИМХО это не обязательно. Было бы еще проще и немного быстрее, если бы он не использовал трюк num / num2, но просто обновил номер для каждого персонажа.

Исправленная версия (Брайаном) как статическая функция:

    public static unsafe int GetHashCodeIra(string x)
    {
        fixed (char* str = x.ToCharArray())
        {
            const int N = 2; // a power of two controlling number of loop iterations
            char* chPtr = str;
            int num = 0x15051505;
            int num2 = num;
            int* numPtr = (int*)chPtr;
            int count = (x.Length+1) / 2;
            int unrolled_iterations = count >> (N+1); // could be 0 and that's OK
            for (int i = unrolled_iterations; i > 0; i--)
            {  // repeat 2**N times
                {
                    num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];
                    num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[1];
                }
                {
                    num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[2];
                    num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[3];
                }
                {
                    num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[4];
                    num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[5];
                }
                {
                    num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[6];
                    num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[7];
                }
                numPtr += 8;
            }
            if (0 != (count & ((1 << N) )))
            {
                {
                    num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];
                    num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[1];
                }
                {
                    num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[2];
                    num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[3];
                }
                numPtr += 4;
            }
            if (0 != (count & ((1 << (N - 1) ))))
            {
                {
                    num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];
                    num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[1];
                }
                numPtr += 2;
            }
            // repeat N times and finally:
            if (1 == (count & 1))
            {
                {
                    num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];
                    // numPtr += 1;
                }
            }

            return (num + (num2 * 0x5d588b65));
        }
    }