{"action":"created","issue":{"url":"https://api.github.com/repos/mrocklin/distributed/issues/6","labels_url":"https://api.github.com/repos/mrocklin/distributed/issues/6/labels{/name}","comments_url":"https://api.github.com/repos/mrocklin/distributed/issues/6/comments","events_url":"https://api.github.com/repos/mrocklin/distributed/issues/6/events","html_url":"https://github.com/mrocklin/distributed/issues/6","id":112029999,"number":6,"title":"Tune update_state","user":{"login":"mrocklin","id":306380,"avatar_url":"https://avatars.githubusercontent.com/u/306380?v=3","gravatar_id":"","url":"https://api.github.com/users/mrocklin","html_url":"https://github.com/mrocklin","followers_url":"https://api.github.com/users/mrocklin/followers","following_url":"https://api.github.com/users/mrocklin/following{/other_user}","gists_url":"https://api.github.com/users/mrocklin/gists{/gist_id}","starred_url":"https://api.github.com/users/mrocklin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mrocklin/subscriptions","organizations_url":"https://api.github.com/users/mrocklin/orgs","repos_url":"https://api.github.com/users/mrocklin/repos","events_url":"https://api.github.com/users/mrocklin/events{/privacy}","received_events_url":"https://api.github.com/users/mrocklin/received_events","type":"User","site_admin":false},"labels":[],"state":"closed","locked":false,"assignee":null,"milestone":null,"comments":3,"created_at":"2015-10-18T17:10:45Z","updated_at":"2015-10-19T03:57:46Z","closed_at":"2015-10-18T17:46:53Z","body":"The `Executor.submit` function can be used *many times* within for loops while building up a complex computation.  This can be a powerful way to write down strange computations with a simple API.  If possible we'd like to make this fast, even for large numbers of submit calls.  Unfortunately this is currently somewhat costly, limiting our ability to build up computations directly in this way.\r\n\r\nI suspect that most of the cost is in `distributed/scheduler.py:update_state` which is run after any `submit`, `map`, or `get` call.  The `update_state` function updates the scheduler's runtime state with a new graph.  In the case of `submit` this new graph is very small (just one key-value pair) but the function is often called many times.  At the moment this function depends somewhat on the size of the current internal graph, and not just on the new graph being added.  This can cause significant slowdowns when using submit repeatedly on already large internal graphs.\r\n\r\n### Some solutions\r\n\r\n1.  Don't use `submit` willy-nilly, and instead ask the user to build up the graphs externally with a tool like `dask.do` and submit those in larger chunks instead.\r\n2.  Batch many submit calls into larger graphs internally on the scheduler side.  This can probably help to keep down `update_state` overhead\r\n3.  Tune `update_state` so that it is linear in the size of the input graph, and somewhat speedy.\r\n\r\nIf possible I'd like to make `update_state` fast.  It will probably be important if we have long-running schedulers in the future with large internal graphs.  We might as well push a bit on this early so that we can rely on it later.\r\n\r\n### Small benchmark script\r\n\r\n```python\r\nfrom distributed.scheduler import update_state\r\nfrom operator import add\r\nfrom time import time\r\n\r\ndef bench_update_state(n):\r\n    dsk = {}\r\n    dependencies = {}\r\n    dependents = {}\r\n\r\n    waiting = {}\r\n    waiting_data = {}\r\n\r\n    held_data = set()\r\n    in_memory = set()\r\n    processing = set()\r\n    released = set()\r\n\r\n    update_state(dsk, dependencies, dependents, held_data,\r\n                 in_memory, processing, released,\r\n                 waiting, waiting_data, {('y', 0): 0}, {('y', 0)})\r\n\r\n    for i in range(n):\r\n        new_dsk = {('x', i): i, ('y', i): (add, ('y', i - 1), ('x', i))}\r\n        new_keys = {('y', i)}\r\n        update_state(dsk, dependencies, dependents, held_data,\r\n                     in_memory, processing, released,\r\n                     waiting, waiting_data, new_dsk, new_keys)\r\n\r\nif __name__ == '__main__':\r\n    import sys\r\n    n = int(sys.argv[1])\r\n    start = time()\r\n    bench_update_state(n)\r\n    end = time()\r\n    print(\"%4f seconds\" % (end - start))\r\n```\r\n\r\n### Non-linear costs\r\n\r\nBy running this script at higher values of n we see non-linear costs:\r\n\r\n```\r\nmrocklin@notebook:~/workspace/distributed$ python bench_update_state.py 10\r\n0.001004 seconds\r\nmrocklin@notebook:~/workspace/distributed$ python bench_update_state.py 100\r\n0.011575 seconds\r\nmrocklin@notebook:~/workspace/distributed$ python bench_update_state.py 1000\r\n0.155894 seconds\r\nmrocklin@notebook:~/workspace/distributed$ python bench_update_state.py 10000\r\n15.132474 seconds\r\n```\r\n\r\n### Most of the cost in the `update_state` function itself\r\n\r\nIf you run this with the profiler\r\n\r\n    $ python -m cProfile -o p.out bench_update_state.py  10000\r\n    $ pip install snakeviz\r\n    $ snakeviz p.out\r\n\r\nYou'll find that about 2.7 seconds is spent within `keys_outside_frontier` and the rest of the time is spent within the `update_state` function itself.\r\n\r\ncc @eriknw, in case he wants to resurrect his tuning skills and dive into the scheduler's guts."},"comment":{"url":"https://api.github.com/repos/mrocklin/distributed/issues/comments/149092101","html_url":"https://github.com/mrocklin/distributed/issues/6#issuecomment-149092101","issue_url":"https://api.github.com/repos/mrocklin/distributed/issues/6","id":149092101,"user":{"login":"eriknw","id":2058401,"avatar_url":"https://avatars.githubusercontent.com/u/2058401?v=3","gravatar_id":"","url":"https://api.github.com/users/eriknw","html_url":"https://github.com/eriknw","followers_url":"https://api.github.com/users/eriknw/followers","following_url":"https://api.github.com/users/eriknw/following{/other_user}","gists_url":"https://api.github.com/users/eriknw/gists{/gist_id}","starred_url":"https://api.github.com/users/eriknw/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/eriknw/subscriptions","organizations_url":"https://api.github.com/users/eriknw/orgs","repos_url":"https://api.github.com/users/eriknw/repos","events_url":"https://api.github.com/users/eriknw/events{/privacy}","received_events_url":"https://api.github.com/users/eriknw/received_events","type":"User","site_admin":false},"created_at":"2015-10-19T03:57:46Z","updated_at":"2015-10-19T03:57:46Z","body":"Just got this ping.  Hurray for profiling and benchmarking!  This makes me think I should add snakeviz support and Jupyter integration to `benchtoolz`.\r\n> As seems to be a common theme, the solution to speed up schedulers seems to be \"add more state.\r\n\r\nSeconded!"}}