J'essaie d'écrire un solveur pour un casse-tête particulier. Il essaie de trouver une solution en essayant chaque mouvement possible un à la fois jusqu'à ce qu'il trouve une solution. La première version a essayé de la résoudre en profondeur en essayant continuellement des mouvements jusqu'à ce qu'elle échoue, puis en revenant en arrière, mais cela s'est avéré être trop lent. Je l'ai réécrit pour avoir la largeur d'abord en utilisant une structure de file d'attente, mais j'ai des problèmes avec la gestion de la mémoire.Manque de mémoire .. Comment?
Voici les parties pertinentes:
int main(int argc, char *argv[])
{
...
int solved = 0;
do {
solved = solver(queue);
} while (!solved && !pblListIsEmpty(queue));
...
}
int solver(PblList *queue) {
state_t *state = (state_t *) pblListPoll(queue);
if (is_solution(state->pucks)) {
print_solution(state);
return 1;
}
state_t *state_cp;
puck new_location;
for (int p = 0; p < puck_count; p++) {
for (dir i = NORTH; i <= WEST; i++) {
if (!rules(state->pucks, p, i)) continue;
new_location = in_dir(state->pucks, p, i);
if (new_location.x != -1) {
state_cp = (state_t *) malloc(sizeof(state_t));
state_cp->move.from = state->pucks[p];
state_cp->move.direction = i;
state_cp->prev = state;
state_cp->pucks = (puck *) malloc (puck_count * sizeof(puck));
memcpy(state_cp->pucks, state->pucks, puck_count * sizeof(puck)); /*CRASH*/
state_cp->pucks[p] = new_location;
pblListPush(queue, state_cp);
}
}
}
free(state->pucks);
return 0;
}
Quand je le lance, je reçois l'erreur:
ice(90175) malloc: *** mmap(size=2097152) failed (error code=12)
*** error: can't allocate region
*** set a breakpoint in malloc_error_break to debug
Bus error
L'erreur se produit autour de l'itération 93000. D'après ce que je peux dire, le message d'erreur provient de l'échec de malloc, et l'erreur de bus provient du memcpy après celui-ci.
J'ai du mal à croire que je manque de mémoire, puisque chaque état de jeu est seulement ~ 400 octets. Pourtant, cela semble être ce qui se passe, vu que le moniteur d'activité signale qu'il utilise 3,99 Go avant qu'il ne se bloque. J'utilise http://www.mission-base.com/peter/source/ pour la structure de la file d'attente (c'est une liste chaînée). Il est clair que je fais quelque chose de stupide. Aucune suggestion?
Vous vous contredisez de trois façons. 1. 400 octets, 2. 3.99GB, 3. 93000 * puck_count * sizeof (puck) allocations (c'est beaucoup plus de 400 octets). Quel est le comportement que vous observez réellement? Oubliez-vous de «libérer» la mémoire lorsque vous en avez fini avec elle? –
chaque état de jeu est d'environ 400 octets, mais il en fait beaucoup de copies, apparemment assez pour remplir 4 Go de RAM. Je ne libère pas tout l'ancien souvenir (je libère de vieilles cartes de puck, mais c'est tout), mais c'est parce que j'en ai besoin pour suivre les mouvements effectués jusqu'ici. – maxdj
@maxdj: Alors, comment expliquez-vous la contradiction # 3? –