shortest_path with weights slower in parallel mode
Hi, I was testing some running times of shortest path calculations and realized that there is some problem with parallel implementation of Dijkstra (I guess that is used when weights are positive?). Maybe locally compiled version would perform better but I have no time to test that.
Code I used for testing for testing:
import graph_tool.all as gt
import random
import time
print(gt.show_config())
g = gt.random_graph(100000, lambda: (3,3))
g.properties[('e', 'cost')] = g.new_ep("double")
for e in g.edges():
g.ep.cost[e] = random.random()
def run_me(num=1000):
for _ in range(num):
start = g.vertex(random.randrange(0, 100000))
end = g.vertex(random.randrange(0, 100000))
out = gt.shortest_path(g, start, end, weights=g.ep.cost)
t = time.time()
run_me()
sch = gt.openmp_get_schedule()
th = gt.openmp_get_num_threads()
t1 = time.time() - t
print("Number of threads: {}. Policy {}. Running time: {}".format(th, sch, t1))
gt.openmp_set_schedule("static", 1)
t = time.time()
run_me()
sch = gt.openmp_get_schedule()
th = gt.openmp_get_num_threads()
t1 = time.time() - t
print("Number of threads: {}. Policy {}. Running time: {}".format(th, sch, t1))
gt.openmp_set_schedule("dynamic")
t = time.time()
run_me()
sch = gt.openmp_get_schedule()
th = gt.openmp_get_num_threads()
t1 = time.time() - t
print("Number of threads: {}. Policy {}. Running time: {}".format(th, sch, t1))
gt.openmp_set_num_threads(1)
t = time.time()
run_me()
sch = gt.openmp_get_schedule()
th = gt.openmp_get_num_threads()
t1 = time.time() - t
print("Number of threads: {}. Policy {}. Running time: {}".format(th, sch, t1))
I use Ubuntu with graph tool 2.22 installed from the repository.
Output of gt.show_config()
version: 2.22 (commit 44bf2b92, Thu Mar 2 23:08:39 2017 +0000)
gcc version: 5.3.1
compilation flags: -DNDEBUG -Wdate-time -D_FORTIFY_SOURCE=2 -fopenmp -O3 -fvisibility=default -fvisibility-inlines-hidden -Wno-deprecated -ftemplate-depth-250 -Wall -Wextra -ftemplate-backtrace-limit=0 -flto=4 -ffunction-sections -fdata-sections --std=gnu++14 -Wl,--gc-sections
install prefix: /usr
python dir: /usr/lib/python3/dist-packages
graph filtering: True
openmp: True
uname: Linux machina 4.8.0-58-generic #63~16.04.1-Ubuntu SMP Mon Jun 26 18:08:51 UTC 2017 x86_64
None