Random memory accesses are expensive?

During optimizing my connect four game engine I reached a point where further improvements only can be minimal because much of the CPU-time is used by the instruction TableEntry te = mTable[idx + i] in the following code sample.

TableEntry getTableEntry(unsigned __int64 lock)
{
    int idx = (lock & 0xFFFFF) * BUCKETSIZE;
    for (int i = 0; i < BUCKETSIZE; i++)
    {
        TableEntry t开发者_运维知识库e = mTable[idx + i]; // bottleneck, about 35% of CPU usage
        if (te.height == NOTSET || lock == te.lock)
            return te;
    }
    return TableEntry();
}

The hash table mTable is defined as std::vector<TableEntry> and has about 4.2 mil. entrys (about 64 MB). I have tried to replace the vectorby allocating the table with new without speed improvement.

I suspect that accessing the memory randomly (because of the Zobrist Hashing function) could be expensive, but really that much? Do you have suggestions to improve the function?

Thank you!

Edit: BUCKETSIZE has a value of 4. It's used as collision strategy. The size of one TableEntry is 16 Bytes, the struct looks like following:

struct TableEntry
{                                       // Old New
    unsigned __int64 lock;              //   8   8
    enum { VALID, UBOUND, LBOUND }flag; //   4   4
    short score;                        //   4   2
    char move;                          //   4   1
    char height;                        //   4   1
                                        // -------
                                        //  24  16 Bytes
    TableEntry() : lock(0LL), flag(VALID), score(0), move(0), height(-127) {}
};

Summary: The function originally needed 39 seconds. After making the changes jdehaan suggested, the function now needs 33 seconds (the program stops after 100 seconds). It's better but I think Konrad Rudolph is right and the main reason why it's that slow are the cache misses.

You are making copies of your table entry, what about using TableEntry& as a type. For the default value at the bottom a static default TableEntry() will also do. I suppose that is where you lose much time.

const TableEntry& getTableEntry(unsigned __int64 lock)
{
    int idx = (lock & 0xFFFFF) * BUCKETSIZE;
    for (int i = 0; i < BUCKETSIZE; i++)
    {
        // hopefuly now less than 35% of CPU usage :-)
        const TableEntry& te = mTable[idx + i];
        if (te.height == NOTSET || lock == te.lock)
            return te;
    }
    return DEFAULT_TABLE_ENTRY;
}

How big is a table entry? I suspect it's the copy that is expensive not the memory lookup.

Memory accesses are quicker if they are contiguous because of cache hits, but it seem you are doing this.

The point about copying the TableEntry is valid. But let’s look at this question:

I suspect that accessing the memory randomly (…) could be expensive, but really that much?

In a word, yes.

Random memory access with an array of your size is a cache killer. It will generate lots of cache misses which can be up to three orders of magnitude slower than access to memory in cache. Three orders of magnitude – that’s a factor 1000.

On the other hand, it actually looks as though you are using lots of array elements in order, even though you generated your starting point using a hash. This speaks against the cache miss theory, unless your BUCKETSIZE is tiny and the code gets called very often with different lock values from the outside.

I have seen this exact problem with hash tables before. The problem is that continuous random access to the hashtable touch all of the memory used by the table (both the main array and all of the elements). If this is large relative to your cache size you will thrash. This manifests as the exact problem you are encountering: That instruction which first references new memory appears to have a very high cost due to the memory stall.

In the case I worked on, a further issue was that the hash table represented a rather small part of the key space. The "default" value (similar to what you call DEFAULT_TABLE_ENTRY) applied to the vast majority of keys so it seemed like the hash table was not heavily used. The problem was that although default entries avoided many inserts, the continuous action of searching touched every element of the cache over and over (and in random order). In that case I was able to move the values from the hashed data to live with the associated structure. It took more overall space because even keys with the default value had to explicitly store the default value, but the locality of reference was vastly improved and the performance gain was huge.

Use pointers

TableEntry* getTableEntry(unsigned __int64 lock) {
int idx = (lock & 0xFFFFF) * BUCKETSIZE;

TableEntry* max = &mTable[idx + BUCKETSIZE];
for (TableEntry* te = &mTable[idx]; te < max; te++)
{
    if (te->height == NOTSET || lock == te->lock)
        return te;
}
return DEFAULT_TABLE_ENTRY; }