One way to make a function go faster is to take special cases into account.
A function with variable size inputs has special cases based on size.
Going parallel only makes sense when the the cost of going parallel
is smaller than the gain, and for this kind of computation it is likely
that the string would have to be fairly large to overcome the cost
of forking a parallel thread. But implementing that isn't hard;
basically you need a test for this.Length exceeding an empirically
determined threshold, and then forking multiple threads to compute
hashes on substrings, with a final step composing the subhashes into
a final hash. Implementation left for the reader.
Modern processors also have SIMD instructions, which can process up
to 32 (or 64) bytes in a single instruction. This would allow you
to process the string in 32 (16 bit character) chunks in one-two
SIMD instructions per chunk; and then fold the 64 byte result into
a single hashcode at the end. This is likely to be extremely fast
for strings of any reasonable size. The implementation of this
from C# is harder, because one doesn't expect a virtual machine
to provide provide easy (or portable) access to the SIMD instructions
that you need. Implementation also left for the reader.
EDIT: Another answer suggests that Mono system does provide
SIMD instruction access.
Having said that, the particular implementation exhibited is pretty stupid.
The key observation is that the loop checks the limit twice on every iteration.
One can solve that problem by checking the end condition cases in advance,
and executing a loop that does the correct number of iterations.
One can do better than that by using
Duffs device
to jump into an unrolled loop of N iterations. This gets rid of
the loop limit checking overhead for N-1 iterations. That modification
would be very easy and surely be worth the effort to implement.
EDIT: You can also combine the SIMD idea and the loop unrolling idea to enable processing many chunks of 8/16 characters in a few SIMD instrucions.
For languages that can't jump into loops, one can do the equivalent of
Duff's device by simply peeling off the initial cases. A shot at
how to recode the original code using the loop peeling approach is the following:
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));
}
}
I haven't compiled or tested this code, but the idea is right.
It depends on the compiler doing reasonable constant folding
and address arithmetic.
I tried to code this to preserve the exact hash value of the original,
but IMHO that isn't really a requirement.
It would be even simpler and a tiny bit faster if it didn't use
the num/num2 stunt, but simply updated num for each character.
Corrected version (by Brian) as a static function:
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));
}
}