Severe performance regression in pathfinding::directed::dijkstra

[ptesarik]

An attempt to upgrade pathfinding to version 4 results in a severe performance regression in Dijkstra's algorithm for rapidquilt.

I have reference setup (based on an actual real-world case), where pathfinding 3.0.14 finishes in reasonable time:

real    0m21,407s
user    0m21,330s
sys     0m0,094s

But pathfinding 4.13.0 takes ages:

real    7m10,000s
user    7m9,897s
sys     0m0,094s

Reverting commit 808b951 restores good performance.

[ptesarik]

To reproduce the issue, unpack issue639.tar.gz and run rapidquilt push in the unpacked directory.

[samueltardieu]

Thanks for the report, the analysis, and the reproduction package. Since it does not change any functionality, I'll revert the commit and issue a new release (I'll post it there) until I can investigate it further.

[ptesarik]

FWIW I have also extracted a self-contained reproducer:
https://gist.github.com/ptesarik/42e8e42f3034e93a61f7289fb92aaeb4

[samueltardieu]

pathfinding 4.13.1 has just been released and backs this patch out. I'll investigate further, I'll keep this issue open.