0

I have a bottleneck function in my code which effectively boils down to :

import networkx as nx
class my_class:
    def __init__(self):
        self.graph = nx.complete_graph(50)  # placeholder for large nx graph
        self.my_dict = {}

    # triggered by event automatically, cannot change trigger
    def slow_function(self, event):
        source = event.source
        dest = event.dest

        # how to speed up this function?
        def bottleneck_function():
            reasonably_fast_obj = reasonably_fast('myfoo')
            self.path_calulator(source, dest, reasonably_fast_obj)

    def path_calulator(self, source, dest, weight):
        return nx.shortest_simple_paths(self.graph, source, dest, weight)


class reasonably_fast:
    def __init__(self, foo):
        self.foo = foo

The main cause is the networkx method which takes a significant amount of time for a large graph.

The slow_function is triggered in such a way that it may be called again before the previous call is finished (due to delay). What is an appropriate way to speed up the task?

Can it be made faster using multiple threads?

Note: I can only use python 2.7 due to some limitations

Edit Here is what I have so far:

import networkx as nx
from multiprocessing import Pool as ThreadPool
from itertools import islice
import random

G = nx.barabasi_albert_graph(10, 5)
G.number_of_edges()  # prints 25

def nx_function():
src, dst = random.sample(range(0,9), 2)
return list(islice(nx.shortest_simple_paths(G, source=src, target=dst), 5))

%timeit nx_function gives 10000000 loops, best of 3: 22.1 ns per loop

def simple():
    for i in range(10):
        nx_function()

%timeit simple gives 100 loops, best of 3: 1.94 ms per loop

def parallelized():
    pool = ThreadPool(4)
    for i in range(10):
        pool.apply_async(func=nx_function)
    pool.close()
    pool.join()

%timeit paralelized gives 10 loops, best of 3: 196 ms per loop

It seems as if the overhead from multiprocessing makes this useless. Is there any other way to speed up this code?

Niloy Saha
  • 444
  • 2
  • 4
  • 14
  • 1
    Generally, threads are to be avoided, due to https://wiki.python.org/moin/GlobalInterpreterLock. – CristiFati Apr 27 '18 at 15:45
  • if the major part of the time is spent in `networkx`, and if this library uses compiled native code, the GIL doesn't apply and threads can be used. – Jean-François Fabre Apr 27 '18 at 15:46
  • @Jean-FrançoisFabre The GIL still applies unless the C code explicitly releases it. NetworkX is all python though. – Stop harming Monica Apr 27 '18 at 15:58
  • Networkx uses a modified DFS to calculate the paths (all_shortest_paths) which cannot be significantly improved AFAIK. However, since I'm making multiple such calls, I should be able run them in parallel right? Now the question is, should I go for threading or multiprocessing? Is it correct to assume that since the bulk of the time is used in running the shortest path algorithm, this is a CPU-bound task and hence, multiprocessing would be more appropriate? – Niloy Saha Apr 27 '18 at 16:34
  • 1
    https://stackoverflow.com/questions/18114285/what-are-the-differences-between-the-threading-and-multiprocessing-modules – Carlos Apr 27 '18 at 20:05

0 Answers0