Hello Tiago,
Thanks a lot for swift update. I timed the 2.22 against commit
bf174831 (compiled with CXXFLAGS=-O3). That does not give an accurate drill
On my typical ~7e6 vertices graph, for a typical search that reach about 1e5 vertices, the improvement is about 20%. We have 83ms (average over 100 runs) for the 2.22 release versus 69ms for commit bf174831. Interestingly, the bf174831 version is more stable with std = 4ms versus 6ms for the 2.22 release.
What I understand from the
boost thread is that we could have only initialization for the whole lifespan of the program. If I get it right, their proposal would, prior to a search, to "re-set" the values from distances vector and predecessors vector only for the reached vertices of the last search. I think it worth a try because, from what I timed the python side of initialization could cost around 18ms (5ms for distance map, 13ms for predecessor map) see timeit snipet below.
import timeit
# pred map
timeit.timeit(setup='import numpy as np; x=np.zeros(int(7e6),dtype="int64")', stmt='x[:] = np.arange(7e6)', number=1000)/1000
# distances
timeit.timeit(setup='import numpy as np; x=np.zeros(int(7e6),dtype="int64")', stmt='x[:] = np.inf)', number=1000)/1000
I did the above timings on a modern work station, to switch to a cloud provider induces a non negligible overhead (+63% for the distances / +469% for the pred map).
What do you think ?
F.