Are random memory accesses expensive?

Question

During the optimization of my connected four game engine, I reached a point where further improvements can be minimal, since most of the CPU time is used by the TableEntry te = mTable[idx + i] command in the following code example.

 TableEntry getTableEntry(unsigned __int64 lock) { int idx = (lock & 0xFFFFF) * BUCKETSIZE; for (int i = 0; i < BUCKETSIZE; i++) { TableEntry te = mTable[idx + i]; // bottleneck, about 35% of CPU usage if (te.height == NOTSET || lock == te.lock) return te; } return TableEntry(); } 

The mTable hash table mTable defined as std::vector<TableEntry> and has about 4.2 million records (about 64 MB). I tried replacing vector by highlighting the new table without increasing speed.

I suspect random access to memory (due to the Zobbrist Hashing feature ) can be expensive, but really so much? Do you have suggestions for improving the function?

Thanks!

Edit: BUCKETSIZE is 4. It is used as a strategy. The size of one TableEntry is 16 bytes, the structure is as follows:

 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 initially took 39 seconds. After making the changes suggested by jdehaan, the function now takes 33 seconds (the program stops after 100 seconds). This is better, but I think Conrad Rudolph is right, and the main reason he is slow is cache misses.

Answer 1

TableEntry copy TableEntry valid. But let's look at this question:

I suspect random access to memory (...) can be expensive, but really so much?

In a word, yes .

Random access to memory with an array of your size is a cache killer. It will generate many misses in the cache, which can be up to three orders of magnitude less than access to memory in the cache. Three orders of magnitude is a factor of 1000.

On the other hand, it actually looks like you are using a lot of array elements in order, even if you created the starting point using a hash. This is a theory of skipping caching if your BUCKETSIZE not tiny and your code is often called with different lock values ​​from the outside.

Answer 2

You are making copies of your table entry as using TableEntry& as a type. For the default value below, the static default value of TableEntry() will be executed. I suppose this is where you lose a lot of 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; } 

Answer 3

How big is the entry in the table? I suspect this is an expensive copy, not a memory search.

Accessing memory is faster if they are adjacent due to a cache hit, but it looks like you are doing it.

Answer 4

I have seen this exact problem with hash tables before. The problem is that continuous random access to the hash table affects all the memory used by the table (both the main and all elements). If this is large in relation to the size of your cache, you will stick around. This appears as the exact problem you are facing: this instruction, which first refers to new memory, seems to have a very high cost due to lack of memory.

When I was working, another problem was that the hash table was a small part of the key space. The default value (similar to what you call DEFAULT_TABLE_ENTRY ) applies to the vast majority of keys, so it seemed that the hash table was not heavily used. The problem was that while the default entries avoided many insertions, the continuous search action touched each cache element again and again (and in random order). In this case, I managed to move the values ​​from the hashed data in order to live with the corresponding structure. This took up more general space, because even keys with a default value should have explicitly kept the default value, but the locality of the links improved significantly and the performance gain was huge.

Answer 5

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; }