{"action":"created","comment":{"url":"https://api.github.com/repos/ContinuumIO/dask/pulls/comments/33626752","id":33626752,"diff_hunk":"@@ -1,9 +1,182 @@\n Optimization\n-------------\n+============\n \n-Small optimizations of the task dependency graph can significantly improve\n-performance in different contexts.  The ``dask.optimize`` module contains\n-several utility functions to transform graphs in a variety of useful ways.\n+Small optimizations performed on the dask graph before calling the scheduler\n+can significantly improve performance in different contexts. The\n+``dask.optimize`` module contains several functions to transform graphs in a\n+variety of useful ways. In most cases, users won't need to interact with these\n+functions directly - specialized subsets of these transforms are done\n+automatically in the dask collections (``dask.array``, ``dask.bag``, and\n+``dask.dataframe``). However, users working with custom graphs or computations\n+may find that applying these methods results in substantial speedups.\n+\n+In general, there are two goals when doing graph optimizations\n+\n+1. Simplify computation\n+2. Improve parallelism\n+\n+Simplifying computation can be done on a graph level by removing unnecessary\n+tasks (``cull``), or on a task level by replacing expensive operations with\n+cheaper ones (``RewriteRule``). Parallelism can be improved by reducing\n+inter-task communication, whether by fusing many tasks into one (``fuse``), or\n+by inlining cheap operations (``inline``, ``inline_functions``).\n+\n+Below, we show an example walking through the use of some of these to optimize\n+a task graph.\n+\n+Example\n+-------\n+\n+Suppose you had a custom dask graph for doing a word counting task.\n+\n+.. code-block:: python\n+\n+    >>> from __future__ import print_function\n+\n+    >>> def print_and_return(string):\n+            print(string)\n+            return string\n+\n+    >>> format_str = 'word list has {0} occurrences of {1}, out of {2} words'\n+\n+    >>> dsk = {'words': 'apple orange apple pear orange pear pear',\n+               'nwords': (len, (str.split, 'words')),\n+               'val1': 'orange',\n+               'val2': 'apple',\n+               'val3': 'pear',\n+               'count1': (str.count, 'words', 'val1'),\n+               'count2': (str.count, 'words', 'val2'),\n+               'count3': (str.count, 'words', 'val3'),\n+               'out1': (format_str.format, 'count1', 'val1', 'nwords'),\n+               'out2': (format_str.format, 'count2', 'val2', 'nwords'),\n+               'out3': (format_str.format, 'count3', 'val3', 'nwords'),\n+               'print1': (print_and_return, 'out1'),\n+               'print2': (print_and_return, 'out2'),\n+               'print3': (print_and_return, 'out3')}\n+\n+.. image:: images/optimize_dask1.png\n+   :width: 30 %\n+   :alt: The original dask\n+\n+Here we're counting the occurence of the words ``'orange``, ``'apple'``, and\n+``'pear'`` in the list of words, formatting an output string reporting the\n+results, printing the output, then returning the output string.\n+\n+To perform the computation, we pass the dask and the desired output keys to a\n+scheduler ``get`` function.\n+\n+.. code-block:: python\n+\n+    >>> from dask.multiprocessing import get\n+\n+    >>> results = get(dsk, ['print1', 'print2'])\n+    word list has 3 occurrences of pear, out of 7 words\n+    word list has 2 occurrences of apple, out of 7 words\n+    word list has 2 occurrences of orange, out of 7 words\n+\n+    >>> results\n+    ('word list has 2 occurrences of orange, out of 7 words',\n+     'word list has 2 occurrences of apple, out of 7 words')\n+\n+As can be seen above, the schedulers computed the whole graph before returning\n+just a few of the outputs. This is because the schedulers will always compute\n+all tasks, even if we only requested a few of the output keys. Before we pass\n+the dask to ``get``, we need to remove the unnecessary tasks from the graph. To\n+do this, we can use the ``cull`` function.\n+\n+.. code-block:: python\n+\n+    >>> from dask.optimize import cull\n+    >>> dsk1 = cull(dsk, ['print1', 'print2'])\n+    >>> results = get(dsk1, ['print1', 'print2'])\n+    word list has 2 occurrences of apple, out of 7 words\n+    word list has 2 occurrences of orange, out of 7 words\n+\n+.. image:: images/optimize_dask2.png\n+   :width: 30 %\n+   :alt: After culling\n+\n+Looking at the task graph above, there are multiple accesses to constants such\n+as ``'val1'`` or ``'val2'`` in the dask. These can be inlined into the tasks to\n+improve efficiency using the ``inline`` function.\n+\n+.. code-block:: python\n+\n+    >>> from dask.optimize import inline\n+    >>> dsk2 = inline(dsk1)\n+    >>> results = get(dsk2, ['print1', 'print2'])\n+    word list has 2 occurrences of apple, out of 7 words\n+    word list has 2 occurrences of orange, out of 7 words\n+\n+.. image:: images/optimize_dask3.png\n+   :width: 20 %\n+   :alt: After inlining\n+\n+Now we have two sets of *almost* linear task chains. The only link between them\n+is the word counting function. For cheap operations like this, the\n+serialization cost may be larger than the actual computation, so it may be\n+faster to do the computation more than once, rather than passing the results to\n+all nodes. To perform this function inlining, the ``inline_functions`` function\n+can be used.\n+\n+.. code-block:: python\n+\n+    >>> from dask.optimize import inline_functions\n+    >>> dsk3 = inline_functions(dsk2)","path":"docs/source/optimize.rst","position":129,"original_position":129,"commit_id":"0cf137f9a3ddd0fb36949173080601b7d88b591e","original_commit_id":"0cf137f9a3ddd0fb36949173080601b7d88b591e","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},"body":"This might be missing the list of functions included below.","created_at":"2015-06-30T21:37:10Z","updated_at":"2015-06-30T21:37:10Z","html_url":"https://github.com/ContinuumIO/dask/pull/381#discussion_r33626752","pull_request_url":"https://api.github.com/repos/ContinuumIO/dask/pulls/381","_links":{"self":{"href":"https://api.github.com/repos/ContinuumIO/dask/pulls/comments/33626752"},"html":{"href":"https://github.com/ContinuumIO/dask/pull/381#discussion_r33626752"},"pull_request":{"href":"https://api.github.com/repos/ContinuumIO/dask/pulls/381"}}},"pull_request":{"url":"https://api.github.com/repos/ContinuumIO/dask/pulls/381","id":38925863,"html_url":"https://github.com/ContinuumIO/dask/pull/381","diff_url":"https://github.com/ContinuumIO/dask/pull/381.diff","patch_url":"https://github.com/ContinuumIO/dask/pull/381.patch","issue_url":"https://api.github.com/repos/ContinuumIO/dask/issues/381","number":381,"state":"open","locked":false,"title":"[WIP] Optimization Docs","user":{"login":"jcrist","id":2783717,"avatar_url":"https://avatars.githubusercontent.com/u/2783717?v=3","gravatar_id":"","url":"https://api.github.com/users/jcrist","html_url":"https://github.com/jcrist","followers_url":"https://api.github.com/users/jcrist/followers","following_url":"https://api.github.com/users/jcrist/following{/other_user}","gists_url":"https://api.github.com/users/jcrist/gists{/gist_id}","starred_url":"https://api.github.com/users/jcrist/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jcrist/subscriptions","organizations_url":"https://api.github.com/users/jcrist/orgs","repos_url":"https://api.github.com/users/jcrist/repos","events_url":"https://api.github.com/users/jcrist/events{/privacy}","received_events_url":"https://api.github.com/users/jcrist/received_events","type":"User","site_admin":false},"body":"Fixes #328.\r\n\r\nTodo:\r\n- [x] Prose example using top-level functions\r\n- [ ] Prose example using rewrite rules\r\n- [ ] Cleanup docstrings for optimization functions\r\n- [ ] Document array specific optimizations\r\n- [ ] Document bag specific optimizations\r\n- [ ] Document dataframe specific optimiations","created_at":"2015-06-30T21:22:34Z","updated_at":"2015-06-30T21:37:10Z","closed_at":null,"merged_at":null,"merge_commit_sha":"13e2b65f9886958eefc260e3b8673ef36b37d966","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/ContinuumIO/dask/pulls/381/commits","review_comments_url":"https://api.github.com/repos/ContinuumIO/dask/pulls/381/comments","review_comment_url":"https://api.github.com/repos/ContinuumIO/dask/pulls/comments{/number}","comments_url":"https://api.github.com/repos/ContinuumIO/dask/issues/381/comments","statuses_url":"https://api.github.com/repos/ContinuumIO/dask/statuses/0cf137f9a3ddd0fb36949173080601b7d88b591e","head":{"label":"jcrist:optimize_docs","ref":"optimize_docs","sha":"0cf137f9a3ddd0fb36949173080601b7d88b591e","user":{"login":"jcrist","id":2783717,"avatar_url":"https://avatars.githubusercontent.com/u/2783717?v=3","gravatar_id":"","url":"https://api.github.com/users/jcrist","html_url":"https://github.com/jcrist","followers_url":"https://api.github.com/users/jcrist/followers","following_url":"https://api.github.com/users/jcrist/following{/other_user}","gists_url":"https://api.github.com/users/jcrist/gists{/gist_id}","starred_url":"https://api.github.com/users/jcrist/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jcrist/subscriptions","organizations_url":"https://api.github.com/users/jcrist/orgs","repos_url":"https://api.github.com/users/jcrist/repos","events_url":"https://api.github.com/users/jcrist/events{/privacy}","received_events_url":"https://api.github.com/users/jcrist/received_events","type":"User","site_admin":false},"repo":{"id":32761805,"name":"dask","full_name":"jcrist/dask","owner":{"login":"jcrist","id":2783717,"avatar_url":"https://avatars.githubusercontent.com/u/2783717?v=3","gravatar_id":"","url":"https://api.github.com/users/jcrist","html_url":"https://github.com/jcrist","followers_url":"https://api.github.com/users/jcrist/followers","following_url":"https://api.github.com/users/jcrist/following{/other_user}","gists_url":"https://api.github.com/users/jcrist/gists{/gist_id}","starred_url":"https://api.github.com/users/jcrist/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jcrist/subscriptions","organizations_url":"https://api.github.com/users/jcrist/orgs","repos_url":"https://api.github.com/users/jcrist/repos","events_url":"https://api.github.com/users/jcrist/events{/privacy}","received_events_url":"https://api.github.com/users/jcrist/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/jcrist/dask","description":"Minimal task scheduling abstraction","fork":true,"url":"https://api.github.com/repos/jcrist/dask","forks_url":"https://api.github.com/repos/jcrist/dask/forks","keys_url":"https://api.github.com/repos/jcrist/dask/keys{/key_id}","collaborators_url":"https://api.github.com/repos/jcrist/dask/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/jcrist/dask/teams","hooks_url":"https://api.github.com/repos/jcrist/dask/hooks","issue_events_url":"https://api.github.com/repos/jcrist/dask/issues/events{/number}","events_url":"https://api.github.com/repos/jcrist/dask/events","assignees_url":"https://api.github.com/repos/jcrist/dask/assignees{/user}","branches_url":"https://api.github.com/repos/jcrist/dask/branches{/branch}","tags_url":"https://api.github.com/repos/jcrist/dask/tags","blobs_url":"https://api.github.com/repos/jcrist/dask/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/jcrist/dask/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/jcrist/dask/git/refs{/sha}","trees_url":"https://api.github.com/repos/jcrist/dask/git/trees{/sha}","statuses_url":"https://api.github.com/repos/jcrist/dask/statuses/{sha}","languages_url":"https://api.github.com/repos/jcrist/dask/languages","stargazers_url":"https://api.github.com/repos/jcrist/dask/stargazers","contributors_url":"https://api.github.com/repos/jcrist/dask/contributors","subscribers_url":"https://api.github.com/repos/jcrist/dask/subscribers","subscription_url":"https://api.github.com/repos/jcrist/dask/subscription","commits_url":"https://api.github.com/repos/jcrist/dask/commits{/sha}","git_commits_url":"https://api.github.com/repos/jcrist/dask/git/commits{/sha}","comments_url":"https://api.github.com/repos/jcrist/dask/comments{/number}","issue_comment_url":"https://api.github.com/repos/jcrist/dask/issues/comments{/number}","contents_url":"https://api.github.com/repos/jcrist/dask/contents/{+path}","compare_url":"https://api.github.com/repos/jcrist/dask/compare/{base}...{head}","merges_url":"https://api.github.com/repos/jcrist/dask/merges","archive_url":"https://api.github.com/repos/jcrist/dask/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/jcrist/dask/downloads","issues_url":"https://api.github.com/repos/jcrist/dask/issues{/number}","pulls_url":"https://api.github.com/repos/jcrist/dask/pulls{/number}","milestones_url":"https://api.github.com/repos/jcrist/dask/milestones{/number}","notifications_url":"https://api.github.com/repos/jcrist/dask/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/jcrist/dask/labels{/name}","releases_url":"https://api.github.com/repos/jcrist/dask/releases{/id}","created_at":"2015-03-23T22:11:35Z","updated_at":"2015-03-28T16:10:40Z","pushed_at":"2015-06-30T21:19:43Z","git_url":"git://github.com/jcrist/dask.git","ssh_url":"git@github.com:jcrist/dask.git","clone_url":"https://github.com/jcrist/dask.git","svn_url":"https://github.com/jcrist/dask","homepage":"http://dask.pydata.org","size":6826,"stargazers_count":0,"watchers_count":0,"language":"Python","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"ContinuumIO:master","ref":"master","sha":"d9e9c87c23c4159a3963fc83182371c42fdd0b5e","user":{"login":"ContinuumIO","id":1158637,"avatar_url":"https://avatars.githubusercontent.com/u/1158637?v=3","gravatar_id":"","url":"https://api.github.com/users/ContinuumIO","html_url":"https://github.com/ContinuumIO","followers_url":"https://api.github.com/users/ContinuumIO/followers","following_url":"https://api.github.com/users/ContinuumIO/following{/other_user}","gists_url":"https://api.github.com/users/ContinuumIO/gists{/gist_id}","starred_url":"https://api.github.com/users/ContinuumIO/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ContinuumIO/subscriptions","organizations_url":"https://api.github.com/users/ContinuumIO/orgs","repos_url":"https://api.github.com/users/ContinuumIO/repos","events_url":"https://api.github.com/users/ContinuumIO/events{/privacy}","received_events_url":"https://api.github.com/users/ContinuumIO/received_events","type":"Organization","site_admin":false},"repo":{"id":28782747,"name":"dask","full_name":"ContinuumIO/dask","owner":{"login":"ContinuumIO","id":1158637,"avatar_url":"https://avatars.githubusercontent.com/u/1158637?v=3","gravatar_id":"","url":"https://api.github.com/users/ContinuumIO","html_url":"https://github.com/ContinuumIO","followers_url":"https://api.github.com/users/ContinuumIO/followers","following_url":"https://api.github.com/users/ContinuumIO/following{/other_user}","gists_url":"https://api.github.com/users/ContinuumIO/gists{/gist_id}","starred_url":"https://api.github.com/users/ContinuumIO/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ContinuumIO/subscriptions","organizations_url":"https://api.github.com/users/ContinuumIO/orgs","repos_url":"https://api.github.com/users/ContinuumIO/repos","events_url":"https://api.github.com/users/ContinuumIO/events{/privacy}","received_events_url":"https://api.github.com/users/ContinuumIO/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/ContinuumIO/dask","description":"Task scheduling and blocked algorithms for parallel processing","fork":false,"url":"https://api.github.com/repos/ContinuumIO/dask","forks_url":"https://api.github.com/repos/ContinuumIO/dask/forks","keys_url":"https://api.github.com/repos/ContinuumIO/dask/keys{/key_id}","collaborators_url":"https://api.github.com/repos/ContinuumIO/dask/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/ContinuumIO/dask/teams","hooks_url":"https://api.github.com/repos/ContinuumIO/dask/hooks","issue_events_url":"https://api.github.com/repos/ContinuumIO/dask/issues/events{/number}","events_url":"https://api.github.com/repos/ContinuumIO/dask/events","assignees_url":"https://api.github.com/repos/ContinuumIO/dask/assignees{/user}","branches_url":"https://api.github.com/repos/ContinuumIO/dask/branches{/branch}","tags_url":"https://api.github.com/repos/ContinuumIO/dask/tags","blobs_url":"https://api.github.com/repos/ContinuumIO/dask/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/ContinuumIO/dask/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/ContinuumIO/dask/git/refs{/sha}","trees_url":"https://api.github.com/repos/ContinuumIO/dask/git/trees{/sha}","statuses_url":"https://api.github.com/repos/ContinuumIO/dask/statuses/{sha}","languages_url":"https://api.github.com/repos/ContinuumIO/dask/languages","stargazers_url":"https://api.github.com/repos/ContinuumIO/dask/stargazers","contributors_url":"https://api.github.com/repos/ContinuumIO/dask/contributors","subscribers_url":"https://api.github.com/repos/ContinuumIO/dask/subscribers","subscription_url":"https://api.github.com/repos/ContinuumIO/dask/subscription","commits_url":"https://api.github.com/repos/ContinuumIO/dask/commits{/sha}","git_commits_url":"https://api.github.com/repos/ContinuumIO/dask/git/commits{/sha}","comments_url":"https://api.github.com/repos/ContinuumIO/dask/comments{/number}","issue_comment_url":"https://api.github.com/repos/ContinuumIO/dask/issues/comments{/number}","contents_url":"https://api.github.com/repos/ContinuumIO/dask/contents/{+path}","compare_url":"https://api.github.com/repos/ContinuumIO/dask/compare/{base}...{head}","merges_url":"https://api.github.com/repos/ContinuumIO/dask/merges","archive_url":"https://api.github.com/repos/ContinuumIO/dask/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/ContinuumIO/dask/downloads","issues_url":"https://api.github.com/repos/ContinuumIO/dask/issues{/number}","pulls_url":"https://api.github.com/repos/ContinuumIO/dask/pulls{/number}","milestones_url":"https://api.github.com/repos/ContinuumIO/dask/milestones{/number}","notifications_url":"https://api.github.com/repos/ContinuumIO/dask/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/ContinuumIO/dask/labels{/name}","releases_url":"https://api.github.com/repos/ContinuumIO/dask/releases{/id}","created_at":"2015-01-04T18:50:00Z","updated_at":"2015-06-30T21:36:35Z","pushed_at":"2015-06-30T21:22:35Z","git_url":"git://github.com/ContinuumIO/dask.git","ssh_url":"git@github.com:ContinuumIO/dask.git","clone_url":"https://github.com/ContinuumIO/dask.git","svn_url":"https://github.com/ContinuumIO/dask","homepage":"http://dask.pydata.org","size":9764,"stargazers_count":106,"watchers_count":106,"language":"Python","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":26,"mirror_url":null,"open_issues_count":56,"forks":26,"open_issues":56,"watchers":106,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/ContinuumIO/dask/pulls/381"},"html":{"href":"https://github.com/ContinuumIO/dask/pull/381"},"issue":{"href":"https://api.github.com/repos/ContinuumIO/dask/issues/381"},"comments":{"href":"https://api.github.com/repos/ContinuumIO/dask/issues/381/comments"},"review_comments":{"href":"https://api.github.com/repos/ContinuumIO/dask/pulls/381/comments"},"review_comment":{"href":"https://api.github.com/repos/ContinuumIO/dask/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/ContinuumIO/dask/pulls/381/commits"},"statuses":{"href":"https://api.github.com/repos/ContinuumIO/dask/statuses/0cf137f9a3ddd0fb36949173080601b7d88b591e"}}}}