nathansttt / hog2

Pathfinding and search testbed/visualization suite. Current code is in PDB-refactor branch.
MIT License
112 stars 55 forks source link

Bug When Accessing a PDB from a Heuristic Pointer in Parallel #72

Open lior8 opened 11 months ago

lior8 commented 11 months ago

This error was observed for LexPermutationPDB, but assumed to be applicable to MR1PermutationPDB due to similar structure. The error will therefore also be explained using LexPermutationPDB.

  1. When calling LexPermutationPDB through a Heuristic pointer, we call HCost(). This calls HCost() from PDBHeuristic (link).
  2. This in turn calls GetAbstractHash() which is implemented in LexPermutationPDB (link) which then calls GetPDBHash().
  3. In GetPDBHash() (link) uses locsCache and dualCache in index threadID. Note that by calling it through HCost(), we are unable to specify the threadID, which means it defaults to 0 as per its decelration (link).

This means that calling the PDB from a Heuristic pointer always inputs threadID=0, which causes problem when multiple threads are using the PDB, as they all change the same vector at the same time instead of changing their individual vectors.