the multiprocess program in python seems get slowly after run for a while

Question

I wrote a multiprocessing program in python. It can illustrate as follow:

nodes = multiprocessing.Manager().list()

lock = multiprocess.Lock()
def get_elems(node):
    #get elements by send requests
def worker():
    lock.acquire()
    node = nodes.pop(0)
    lock.release()
    elems = get_elems(node)

    lock.acquire()
        for elem in elems:
            nodes.append(node)
    lock.release()
if __name__ == "__main__":
    node = {"name":"name", "group":0}
    nodes.append(node)
    processes = [None for i in xrange(10)]
    for i in xrange(10):
        processes[i] = multiprocessing.Process(target=worker)
        processes[i].start()
    for i in xrange(10):
        processes[i].join()

At the beginning of the program run, it seems everything is okay. After run for a while. the speed of the program slow down. The phenomenon also exist when use multithreading. And I saw there is a Global Interpreter Lock in Python, So I change to multiprocessing. But still have this phenomenon. The complete code is in here. I have tried Cython, still have this phenomenon. Is there something wrong in my code? Or is there a birth defects in python about parallel?

To my mind, too many lock operations will definitely slow your code down. Using global variables is not really good too. — ForceBru, Apr 18 '15 at 15:11
Multiprocessing doesn't provide satisfactory results if inter-process communication overhead between the processors is high. Loops are the places where most of the computation time is spent. Try to optimize those areas. Also, why don't you try pipe-lining? — V Sree Harissh, Apr 18 '15 at 15:34
excuse my ignorance, but is `nodes.extend(node)` working at all? Doesn't it require an iterable? Maybe you need `nodes.append(node)`, if I understand your code correctly (i.e. you are trying to add an element to the list as it is, not adding its subelements as new list elements) — Pynchia, Apr 18 '15 at 16:21
or maybe, you might want to correct `nodes.extend(node)` with `nodes.extend(elems)` ? I am bettin gon this an posting it as an answer... — Pynchia, Apr 18 '15 at 16:31
@Pynchia I want to append some nodes which meet some condition in to `nodes`. I have edit the code. Sorry for the misleading. — stamaimer, Apr 19 '15 at 04:07

Javier · Accepted Answer · 2015-04-18T15:44:33.260

2

I'm not sure it's the actual cause but, you are popping from the beginning of an increasingly longer list. That's expensive. Try to use a collections.deque.

Update: Read the linked code. You should use a Queue, as suggested in the comments to this post, and threads. You do away with locks using the Queue. The workers are IO bound so threads are appropriate.

edited Apr 18 '15 at 15:44

answered Apr 18 '15 at 15:10

Javier

2,752
15
30

1

Instead of collections.deque, try [multiprocessing.Queue](https://docs.python.org/2/library/multiprocessing.html#multiprocessing.Queue), which is multiprocess safe, so you don't need most of the locks anymore. – Lie Ryan Apr 18 '15 at 15:35
1

For a FIFO, it's undeniably better. I don't know why he's using a list... Also, a deque would also only work with threads and not as IPC and the Manager doesn't have a deque. – Javier Apr 18 '15 at 15:39
1

@Javier You can create a custom `Manager` that exposes a `deque`, if the problem really calls for one. See [this answer](http://stackoverflow.com/a/27345949/2073595) – dano Apr 18 '15 at 15:47
Ah, by using a proxy! Good catch! Thanks @dano! – Javier Apr 18 '15 at 16:35
@Javier As you see in the linked code, I have three variable to share between subprocesses. Every process need write to `nodes`, `links` and `tasks`(append to them), and every process need to read from `tasks`(pop from it) . I change the `tasks` to `multiprocessing.Queue()` and remain the `nodes` and `links` to `multiprocessing.Manager().list()`. The variable `links` store the relation between `node` which represent by index. I can't get the index of element in Queue, that's why i use list instead of queue before. The performance after change is improved, but still slow down. – stamaimer Apr 19 '15 at 06:05
I think the cost of time maybe in append to the list which is a increasingly longer list – stamaimer Apr 19 '15 at 14:07
Appending is O(1), meaning it has fixed cost, but searching in a list (`nodes.index(node)`) is O(n), meaning it's linearly more expensive with size. Can you change nodes to be a dict with the node as the key and the value as the ID, if needed? – Javier Apr 19 '15 at 15:08
@Javier the append will take more time when the list [increasingly](http://stackoverflow.com/questions/2473783/is-there-a-way-to-circumvent-python-list-append-becoming-progressively-slower). I also focus on that line `nodes.index(node)`. And I think this line `if tmpu in nodes` also time cost. And I find [this](http://stackoverflow.com/questions/364621/python-get-position-in-list) and [this](http://stackoverflow.com/questions/946860/using-pythons-list-index-method-on-a-list-of-tuples-or-objects). what's your opinion about the fastest way to check if list contains a specify element? – stamaimer Apr 19 '15 at 16:02
Appending to the list doesn't slow down with size. Measure it by changing the initial size (1000): `python2 -m timeit -s 'a=range(1000)' 'a.append(10)'` – Javier Apr 19 '15 at 16:34
The best way is not to use a list, use a dict! If you must use a list, then sort it and use binary search: http://stackoverflow.com/questions/212358/binary-search-in-python otherwise it will be O(n). – Javier Apr 19 '15 at 16:38

the multiprocess program in python seems get slowly after run for a while

1 Answers1