Cache line align

Idea by Lucas Breasch
I believe your TT clusters are misaligned. What you want is for TT clusters (16*4=64 bytes) to hold on a singe cache line, right? But it's not what operator new[] does, not even if you do something like: ptr = new TTCluster[n] and sizeof(TTCluster)=64. operator new[] only aligns correctly for built-in types, but it can't do 64-byte alignment.

So your TT clusters are typically spread across 2 contiguous cache lines of 64-bytes. I suppose that's why you prefetch 2 cache lines instead of 1 ?

After a lot of googling around, I came to the conclusion that there's no portable way to allocate arbitrarly aligned memory. Not even in C++11 (only the C11 standard solves this problem). But you can hack around it:

void *aligned_malloc( size_t size, int align )
{
    void *mem = malloc( size + (align-1) + sizeof(void*) );
    char *amem = ((char*)mem) + sizeof(void*);
    amem += align - ((uintptr)amem & (align - 1));
    ((void**)amem)[-1] = mem;
    return amem;
}

void aligned_free( void *mem )
{
    free( ((void**)mem)[-1] );
}

On POSIX there's posix_memalign(), which is nice because you de-allocate with a simple free(). But it seems not to be well supported by other UNIX-like systems (Mac OSX, BSD). And, more importantly, it has no equivalent in Windows.

Regarding expected speed gain, it surely depends much on how you test it. With many search threads competing for the cache memory, you are currently loading twice more cache lines for TT than necessary. So fixing this should improve speed, although the gain probably depends much on hash size and number of threads. At least it worked in DiscoCheck.