# AI Tetris-like game

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.

• 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. – Martin York May 6 '16 at 19:41

## First Pass:

void Board::traverse (Tile *t, Neighbours neighbours)
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

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