AI Tetris-like game

Question

I was thinking to rewrite my Python code to C++ since it contains quite a lot of simple loops. I was stunned to find out that this critical part of code (the code below) is about 5 times slower than the Python code, and I'm hoping you could help me figure out why.

The context is some kind of game similar to Tetris, where I'm recursing** through the board and visiting each tile (and then its neighbours if not yet visited) during a traverse.

C++

void Board::traverse (Tile *t, Neighbours neighbours)
 {
 t->visited = true;
 COO coo = make_pair(t->i, t->j);
 Buddies buddies = neighbours[coo];
 if (t->color != '0' && t->color != '.')
 {
 for (uint i = 0; i < buddies.size(); i++)
 {
 Tile *buddy = &this->field[buddies[i]];
 if (buddy->visited && buddy->color == t->color)
 {
 if (buddy->chainId == -1)
 {
 buddy->chainId = this->chains.size();
 this->chains[buddy->chainId].push_back(*buddy);
 }
 t->chainId = buddy->chainId;
 this->chains[t->chainId].push_back(*t);
 break;
 }
 }
 if (t->chainId == -1)
 {
 t->chainId = this->chains.size();
 this->chains[t->chainId].push_back(*t);
 }
 }
 for (uint i = 0; i < buddies.size(); i++)
 {
 if (!this->field[buddies[i]].visited)
 {
 this->traverse(&this->field[buddies[i]], neighbours);
 }
 }
 }

Python

class Board():
 def __init__(self, s):
 self.field = []
 self.chains = {}
 self.heights = None
 self.score = 0
 self.step = 1
 def traverse(self, t=None):
 t.visited = True
 buddies = neighbours[(t.i, t.j)]
 if t.color != '0' and t.color != '.':
 for i, j in buddies:
 if self.field[i][j].visited and self.field[i][j].color == t.color:
 if self.field[i][j].chain_id is None:
 self.field[i][j].chain_id = len(self.chains)
 self.chains[self.field[i][j].chain_id] = [self.field[i][j]]
 t.chain_id = self.field[i][j].chain_id
 self.chains[t.chain_id].append(t)
 break
 if t.chain_id is None:
 t.chain_id = len(self.chains)
 self.chains[t.chain_id] = [t]
 for i, j in buddies:
 if not self.field[i][j].visited:
 self.traverse(self.field[i][j])

---

** The reason for this recursing is that we are not looking for simple line clear but a "line" could be seen as 4 or more blocks adjacent; making recursion through connected nodes more logical. A chain in this context is a group of connected nodes of the same color.

• Loki Astari: It's hard to tell you don't provide the type information on a lot of objects. But one thing that is majorly different between the languages is names. In pythong a name is a reference to an object. In C++ objects are named and distinct (thus when pushing them you are making copies (which can be expensive)). In these cases you should be passing pointers or references depending on the situation. Can you post the class definition of Board COO Budies and anything else relevant.

Answer 1

First Pass:

void Board::traverse (Tile *t, Neighbours neighbours)
 ^^^^ Pointers are bad idea.
 They make resource management hard to 
 reason about as pointers have no
 ownership semantics. Prefer a reference
 if it can not be nullptr.
void Board::traverse (Tile *t, Neighbours neighbours)
 ^^^^^^^^^^^^^^^^^^^^^ 
 Here you are passing neighbours by value.
 This means you are making a copy of the
 object. Prefer const reference.
 // What is the type of COO
 // is there a better way to create it?
 COO coo = make_pair(t->i, t->j);
 // Here you are copy the content of `neighbours[coo]`
 // into buddies. Do you need a copy or can we just
 // use a reference to the original value.
 Buddies buddies = neighbours[coo];
 // Prefer a reference to a pointer.
 Tile *buddy = &this->field[buddies[i]];
 // Here you are making a copy of buddy.
 // Do you really need another copy?
 this->chains[buddy->chainId].push_back(*buddy);
 // Again you are copy the value of tile into chains.
 this->chains[t->chainId].push_back(*t);
 // Another copy of tiles is being put here.
 this->chains[t->chainId].push_back(*t);
 // And you are copying neighbours into the
 // recursive call here.
 this->traverse(&this->field[buddies[i]], neighbours);

Use of this

Your use of this is not idiomatic.

this->chains[t->chainId].push_back(*t);

Its much easier to write:

chains[t->chainId].push_back(*t);

The only reason to use this is to disambiguate the use of shadowed variables. But shadowed variables is an error waiting to happen. So it is best to avoid shadowed variables entirely (even turn on your errors to make sure they don't happen)

-Wall -Wextra -Wshadow -Werror

• Morwenn: If I'm not mistaken, -Wshadow isn't enabled by either of -Wall and -Wextra. It needs to be specified separately.
• PascalVKooten: This has been a great answer! I've learned a lot from it, thank you. The speed improvement (with also -O2) was quite huge.