Confused newbie: vector::erase()

[Sybolt de Boer]

Just out of curiosity: assuming executeMove(), isAttacked(), rollback()
don't modify the vector m, can anyone explain to me why generateLegalMoves()
gives a runtime error on occasion, and generateLegalMoves2() doesn't?
TIA, Sybolt

void
MoveGenerator::generateLegalMoves(std::vector<Move> &m)
{
generateMoves(m);
int n = m.end() - m.begin(), i = 0;

while (i < n) {
executeMove(m);

if (isAttacked(&d_pieceArray[toMove() ^ COLOR][0])) {
--n;
m = m[n];
} else ++i;

rollback();
}

if (n != (m.end() - m.begin()))
m.erase(m.begin() + i, m.end());

}

void
MoveGenerator::generateLegalMoves2(std::vector<Move> &m)
{
generateMoves(m);
std::vector<Move>::iterator i = m.begin();

while (i < m.end()) {
executeMove(*i);

if (isAttacked(&d_pieceArray[toMove() ^ COLOR][0])) {
i = m.erase(i);
} else ++i;

rollback();
}
}

PS: I'm using gcc-4.1 on linux for what that's worth

 

[Jakob Bieling]

Just out of curiosity: assuming executeMove(), isAttacked(),
rollback() don't modify the vector m, can anyone explain to me why
generateLegalMoves() gives a runtime error on occasion, and
generateLegalMoves2() doesn't?

void
MoveGenerator::generateLegalMoves(std::vector<Move> &m)
{
generateMoves(m);
int n = m.end() - m.begin(), i = 0;

Why not use 'm.size ()' here?

while (i < n) {
executeMove(m);

if (isAttacked(&d_pieceArray[toMove() ^ COLOR][0])) {
--n;
m = m[n];
} else ++i;

rollback();
}

if (n != (m.end() - m.begin()))

.. and here.

m.erase(m.begin() + i, m.end());

}

In this snippet the (possibly compiler-generated) assignment operator
gets called.

void
MoveGenerator::generateLegalMoves2(std::vector<Move> &m)
{
generateMoves(m);
std::vector<Move>::iterator i = m.begin();

while (i < m.end()) {
executeMove(*i);

if (isAttacked(&d_pieceArray[toMove() ^ COLOR][0])) {
i = m.erase(i);
} else ++i;

rollback();
}
}

Here you delete directly.

My guess is that 'Move' contains at least one pointer to dynamically
allocated memory and you do not deep-copy the memory its pointing to. So
when you call erase in the first snippet, you try deleting the same memory
more than once, because more than one object hold the same pointer. If that
does not help, try creating a minimal but compilable example, that
demonstrates your problem.

I would prefer the second version over the first one, tho, since it is
more to the point.


hth

 

[Alf P. Steinbach]

* Sybolt de Boer:

Just out of curiosity: assuming executeMove(), isAttacked(), rollback()
don't modify the vector m, can anyone explain to me why generateLegalMoves()
gives a runtime error on occasion, and generateLegalMoves2() doesn't?
TIA, Sybolt

void
MoveGenerator::generateLegalMoves(std::vector<Move> &m)
{
generateMoves(m);
int n = m.end() - m.begin(), i = 0;

while (i < n) {
executeMove(m);

if (isAttacked(&d_pieceArray[toMove() ^ COLOR][0])) {
--n;
m = m[n];
} else ++i;

rollback();
}

if (n != (m.end() - m.begin()))
m.erase(m.begin() + i, m.end());

}

Here you have the possibility of self-assignment, e.g. [m0] = m[0].

Self-assignment can do bad things if the type's assignment operator is
implemented under the assumption that self-assignment never happens.

void
MoveGenerator::generateLegalMoves2(std::vector<Move> &m)
{
generateMoves(m);
std::vector<Move>::iterator i = m.begin();

while (i < m.end()) {
executeMove(*i);

if (isAttacked(&d_pieceArray[toMove() ^ COLOR][0])) {
i = m.erase(i);
} else ++i;

rollback();
}
}

Here you don't (in practice) have the possibility of self-assignment,
but this algorithm is O(n^2) time, which is bad.

 

[Sybolt de Boer]

Just out of curiosity: assuming executeMove(), isAttacked(),
rollback() don't modify the vector m, can anyone explain to me why
generateLegalMoves() gives a runtime error on occasion, and
generateLegalMoves2() doesn't?

void
MoveGenerator::generateLegalMoves(std::vector<Move> &m)
{
generateMoves(m);
int n = m.end() - m.begin(), i = 0;

Why not use 'm.size ()' here?
agreed

while (i < n) {
executeMove(m);

if (isAttacked(&d_pieceArray[toMove() ^ COLOR][0])) {
--n;
m = m[n];
} else ++i;

rollback();
}

if (n != (m.end() - m.begin()))

.. and here.

m.erase(m.begin() + i, m.end());

}

In this snippet the (possibly compiler-generated) assignment operator
gets called.

assignment operator is not overloaded.

void
MoveGenerator::generateLegalMoves2(std::vector<Move> &m)
{
generateMoves(m);
std::vector<Move>::iterator i = m.begin();

while (i < m.end()) {
executeMove(*i);

if (isAttacked(&d_pieceArray[toMove() ^ COLOR][0])) {
i = m.erase(i);
} else ++i;

rollback();
}
}

Here you delete directly.
My guess is that 'Move' contains at least one pointer to dynamically
allocated memory and you do not deep-copy the memory its pointing to. So
when you call erase in the first snippet, you try deleting the same memory
more than once, because more than one object hold the same pointer. If
that does not help, try creating a minimal but compilable example, that
demonstrates your problem.

'Move' contains no pointers, only integer types, and 2 bitfields to keep it
within wordsize. Replacing bitfields with integer types does not change
behaviour. Removing self-assignment by using a temporary does not change
behaviour. Isolating the problem is a problem: it happens maybe once in
many thousands (30K-100K) iterations. I am trying to understand if this is
a compiler/library issue, my general lack of understanding, or simply a
good-old off_by_one (offByOne )

I would prefer the second version over the first one, tho, since it is
more to the point.

Second version works, but I would prefer not to copy excessively in critical
path.

hth

Thanks for your response

 

[Sybolt de Boer]

* Sybolt de Boer:

Just out of curiosity: assuming executeMove(), isAttacked(), rollback()
don't modify the vector m, can anyone explain to me why
generateLegalMoves() gives a runtime error on occasion, and
generateLegalMoves2() doesn't?
TIA, Sybolt

void
MoveGenerator::generateLegalMoves(std::vector<Move> &m)
{
generateMoves(m);
int n = m.end() - m.begin(), i = 0;

while (i < n) {
executeMove(m);

if (isAttacked(&d_pieceArray[toMove() ^ COLOR][0])) {
--n;
m = m[n];
} else ++i;

rollback();
}

if (n != (m.end() - m.begin()))
m.erase(m.begin() + i, m.end());

}

Here you have the possibility of self-assignment, e.g. [m0] = m[0].

Self-assignment can do bad things if the type's assignment operator is
implemented under the assumption that self-assignment never happens.

Removing possible self-assignment by using a temporary does not change
behaviour.

void
MoveGenerator::generateLegalMoves2(std::vector<Move> &m)
{
generateMoves(m);
std::vector<Move>::iterator i = m.begin();

while (i < m.end()) {
executeMove(*i);

if (isAttacked(&d_pieceArray[toMove() ^ COLOR][0])) {
i = m.erase(i);
} else ++i;

rollback();
}
}

Here you don't (in practice) have the possibility of self-assignment,
but this algorithm is O(n^2) time, which is bad.

Yes, I would prefer to avoid that. Thanks for your response,

Sybolt

 

[Jakob Bieling]

Jakob Bieling wrote:

'Move' contains no pointers, only integer types, and 2 bitfields to
keep it within wordsize. Replacing bitfields with integer types does
not change behaviour. Removing self-assignment by using a temporary
does not change behaviour. Isolating the problem is a problem: it
happens maybe once in many thousands (30K-100K) iterations. I am
trying to understand if this is a compiler/library issue, my general
lack of understanding, or simply a good-old off_by_one (offByOne )

Can you maybe pin-point the line that is causing the crash? If this bug
appears so rarely, you might also have your bug elsewhere. That is, another
function could be writing over array bounds, corrupting your vector now and
then (thus your bug is so difficult to reproduce) by overwriting some of the
vectors memory.

Second version works, but I would prefer not to copy excessively in
critical path.

After reading (and after some minutes also understanding ) Alf's
reply, I should revise my statement, even tho I do find the second version
more readable. I did not even compare the complexity of both versions.

hth

 

[Sybolt de Boer]

Can you maybe pin-point the line that is causing the crash? If this
bug
appears so rarely, you might also have your bug elsewhere. That is,
another function could be writing over array bounds, corrupting your
vector now and then (thus your bug is so difficult to reproduce) by
overwriting some of the vectors memory.



After reading (and after some minutes also understanding ) Alf's
reply, I should revise my statement, even tho I do find the second version
more readable. I did not even compare the complexity of both versions.

hth

After finding out about GLIBCXX_DEBUG flag I was able to get a more useful
backtrace. The problem was not in generateLegalMoves(), but in the caller:
the subsequent call to std::sort() bombed with the first, and not with the
second version. It appears I ran into:

http://www.cocoabuilder.com/archive/message/xcode/2005/11/23/1426

Move:perator< wasn't as strict a strict-weak-ordering, as a
strict-weak-ordering is supposed to be, and under rare conditions,
std::sort implementation can write beyond vector boundaries. For reasons
still unknown to me, the second version somehow managed to not trigger this
bug. Regards,

Sybolt