Jednym ze sposobów przyspieszenia działania jest uwzględnienie specjalnych przypadków. Funkcja z wejściami o zmiennej wielkości ma specjalne przypadki na podstawie rozmiaru.
Idąc równolegle ma sens tylko wtedy, gdy koszt będzie równoległy jest mniejszy niż zysk, a do tego rodzaju obliczeń jest prawdopodobne że ciąg musiałby być dość duża, aby przezwyciężyć koszt z rozwidlone gwint równoległy. Ale wdrożenie tego nie jest trudne; w zasadzie potrzebny jest do tego test. Długość przekraczająca empirycznie ustalony próg , a następnie rozwidlenie wielu wątków w celu obliczenia skrótów na podciągach, z ostatnim krokiem komponującym subhashy z końcowym hashem w . Implementacja pozostawiona dla czytelnika.
Nowoczesne procesory mają również instrukcje SIMD, które mogą przetwarzać od do 32 (lub 64) bajtów w pojedynczej instrukcji. To pozwoliłoby ci przetworzyć ciąg w 32 (16-bitowych znakach) w jednej-dwóch instrukcjach SIMD na porcję; a następnie złożyć 64-bajtowy wynik na jeden hashcode na końcu. Prawdopodobnie będzie to wyjątkowo szybkie dla ciągów o dowolnej rozsądnej wielkości. Wdrożenie tego z C# jest trudniejsze, ponieważ nie oczekuje się, że maszyna wirtualna zapewni łatwy (lub przenośny) dostęp do instrukcji SIMD, której potrzebujesz. Implementacja pozostała również dla czytelnika. EDYCJA: Kolejna odpowiedź sugeruje, że system Mono zapewnia dostęp do instrukcji SIMD z .
Powiedziawszy to, pokazana realizacja jest dość głupia. Kluczową obserwacją jest to, że pętla sprawdza limit dwa razy przy każdej iteracji. Można rozwiązać ten problem, sprawdzając z wyprzedzeniem przypadki stanu końcowego, i wykonując pętlę, która wykonuje poprawną liczbę iteracji. Można zrobić lepiej, używając Duffs device , aby przejść do rozwiniętej pętli iteracji N. To pozbywa się nadmiaru sprawdzania limitu pętli dla iteracji N-1. Ta modyfikacja byłaby bardzo łatwa i na pewno warta wysiłku wdrożenia.
EDYCJA: Można również połączyć pomysł SIMD i pomysł rozwijania pętli, aby umożliwić przetwarzanie wielu fragmentów 8/16 znaków w kilku instrukcjach SIMD.
Dla języków, które nie mogą przeskoczyć do pętli, można wykonać ekwiwalent urządzenia Duff, po prostu odrywając początkowe przypadki. Strzał w jak przekodować oryginalnego kodu z wykorzystaniem pętli obierania podejście jest następujące:
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));
}
}
Nie skompilowany lub przetestowane ten kod, ale pomysł ma rację. To zależy od kompilatora wykonującego rozsądne stałe składanie i arytmetyki adresu.
Próbowałem to zakodować, aby zachować dokładną wartość mieszania oryginału, , ale IMHO, które tak naprawdę nie jest wymagane. Byłoby jeszcze prostsze i odrobinę szybsze, gdyby nie użyto num/num2 stunt, ale po prostu zaktualizowano num dla każdej postaci.
wersji poprawiono (Brian) jako funkcja statycznego:
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));
}
}
Wiele rdzeni lub procesorów graficznych może zwiększać prędkość tylko z ciągami * HUGE *. – Guillaume
Wypróbowałeś któryś ze swoich pomysłów (numer 1 nie byłby zbyt trudny do zakodowania)? Jeśli tak, opublikuj to, co znalazłeś ... –
Jakiś konkretny powód, aby go potrzebować, aby zwrócić to samo? Algorytm "GetHashCode" jest zdefiniowany przez implementację dla wszystkich typów zgodnie z ECMA-335, a w celu ponownego zastosowania 'GetHashCode' dla łańcucha znaków, używasz już innej implementacji CLR. –