unsafe loop not as fast as id like

[colin]

Hi, I have a binary sorted tree wich I find my app is spending most of its time in
so I decided to try speed it up a bit ...

I tested converting it from classes to an indexed array of structs so I could use
unsafe pointers, however although it is definatly faster it only manages
about 90 million iterations per second, wich doesnt seem a lot
on my AMD64 3200+ cpu

I have played around with the data size, and made sure ive kept
it within the cpu cache, as it goes a lot slower if I increase
the data size above about 1Mb.

this is just a test, so the tree simply has nodes of 3 ints,
one for the value, and a high and low index.

using randomised data and no tree balancing its slower than the dictionary class,
but with balancing should improve marginaly.
however dictionary class requires a key and value,
and doesnt allow duplicate entries so needs 2 operations and handling for duplicates
so I assumed there was some room for improvment.

public int Find(int hash)
{
int index = 0;
searchItemCnt++;
unsafe
{
fixed (IndexedBinaryTreeNode* nodeArrayPtr = &NodeArray[0])
{
while (true)
{
IndexedBinaryTreeNode* node = nodeArrayPtr + index;
searchNodeCnt++;
if (hash < node->intValue)
{
if (node->_LowerNode < 0)
return -1;
index = node->_LowerNode;
}
else if (hash node->intValue)
{
if (node->_HigherNode < 0)
return -1;
index = node->_HigherNode;
}
else
{
return index;
}
}
}
}
}

I thought unsafe code would go faster ..

is there any other options I should know about ?
ive turned off overflow check and run it in release from
outside the debugger.

other than that I may consider using a lower level language,
although I imagine there may well already be such implementations available.
or am I expecting too much?

thanks
Colin