{"action":"created","comment":{"url":"https://api.github.com/repos/amplab/keystone/pulls/comments/52401519","id":52401519,"diff_hunk":"@@ -0,0 +1,355 @@\n+package workflow\n+\n+import breeze.linalg.{max, DenseVector, DenseMatrix}\n+import nodes.util.Cacher\n+import pipelines.Logging\n+import workflow.AutoCacheRule.{GreedyCache, NaiveCache, CachingStrategy}\n+\n+case class Profile(ns: Long, mem: Long) {\n+  def +(p: Profile) = Profile(this.ns + p.ns, this.mem + p.mem)\n+}\n+\n+case class SampleProfile(scale: Long, profile: Profile)\n+\n+class AutoCacheRule(cachingMode: CachingStrategy) extends Rule with Logging {\n+\n+  /**\n+   * Get the node weights: estimates for how many passes an instruction will make over its input dependencies\n+   */\n+  def getNodeWeights(instructions: Seq[Instruction]): Map[Int, Int] = {\n+    instructions.zipWithIndex.map {\n+      case (TransformerApplyNode(transformer, _), i) => instructions(transformer) match {\n+        case node: WeightedNode => (i, node.weight)\n+        case _ => (i, 1)\n+      }\n+      case (EstimatorFitNode(estimator, _), i) => instructions(estimator) match {\n+        case node: WeightedNode => (i, node.weight)\n+        case _ => (i, 1)\n+      }\n+      case (_, i) => (i, 1)\n+    }.toMap\n+  }\n+\n+  /**\n+   * Get a map representing the immediate children for each instruction\n+   * Note: This doesn't capture how many times each child depended on the instruction\n+   */\n+  def getImmediateChildrenByInstruction(instructions: Seq[Instruction]): Map[Int, Seq[Int]] = {\n+    instructions.indices.map(i => (i, WorkflowUtils.getImmediateChildren(i, instructions))).toMap\n+  }\n+\n+  /**\n+   * Get an estimate for how many times each instruction will be executed, assuming\n+   * the given set of instructions have their outputs cached\n+   */\n+  def getRuns(instructions: Seq[Instruction], cache: Set[Int], nodeWeights: Map[Int, Int]): Map[Int, Int] = {\n+    val immediateChildrenByInstruction = getImmediateChildrenByInstruction(instructions)\n+\n+    instructions.indices.foldRight(Map[Int, Int]()) { case (i, runsByIndex) =>\n+      if (immediateChildrenByInstruction(i).isEmpty) {\n+        runsByIndex + (i -> 1)\n+      }\n+      else {\n+        val runs = immediateChildrenByInstruction(i).map(j => if (cache.contains(j)) {\n+          nodeWeights(j)\n+        } else {\n+          nodeWeights(j) * runsByIndex(j)\n+        }).sum\n+        runsByIndex + (i -> runs)\n+      }\n+    }\n+  }\n+\n+  def generalizeProfiles(newScale: Long, sampleProfiles: Seq[SampleProfile]): Profile = {\n+    def getModel(inp: Iterable[(Long, String, Long)]): Double => Double = {\n+      val observations = inp.toArray\n+\n+      //Pack a data matrix with observations\n+      val X = DenseMatrix.ones[Double](observations.length, 2)\n+      observations.zipWithIndex.foreach(o => X(o._2, 0) = o._1._1.toDouble)\n+      val y = DenseVector(observations.map(_._3.toDouble))","path":"src/main/scala/workflow/AutoCacheRule.scala","position":70,"original_position":70,"commit_id":"a0a2dbc051e2211b2d3497454bd63dff992dca57","original_commit_id":"a0a2dbc051e2211b2d3497454bd63dff992dca57","user":{"login":"shivaram","id":143893,"avatar_url":"https://avatars.githubusercontent.com/u/143893?v=3","gravatar_id":"","url":"https://api.github.com/users/shivaram","html_url":"https://github.com/shivaram","followers_url":"https://api.github.com/users/shivaram/followers","following_url":"https://api.github.com/users/shivaram/following{/other_user}","gists_url":"https://api.github.com/users/shivaram/gists{/gist_id}","starred_url":"https://api.github.com/users/shivaram/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/shivaram/subscriptions","organizations_url":"https://api.github.com/users/shivaram/orgs","repos_url":"https://api.github.com/users/shivaram/repos","events_url":"https://api.github.com/users/shivaram/events{/privacy}","received_events_url":"https://api.github.com/users/shivaram/received_events","type":"User","site_admin":false},"body":"On the above note, it'll be good to add a note on what we are solving for in the line below. ","created_at":"2016-02-10T01:00:25Z","updated_at":"2016-02-10T01:00:25Z","html_url":"https://github.com/amplab/keystone/pull/224#discussion_r52401519","pull_request_url":"https://api.github.com/repos/amplab/keystone/pulls/224","_links":{"self":{"href":"https://api.github.com/repos/amplab/keystone/pulls/comments/52401519"},"html":{"href":"https://github.com/amplab/keystone/pull/224#discussion_r52401519"},"pull_request":{"href":"https://api.github.com/repos/amplab/keystone/pulls/224"}}},"pull_request":{"url":"https://api.github.com/repos/amplab/keystone/pulls/224","id":58510971,"html_url":"https://github.com/amplab/keystone/pull/224","diff_url":"https://github.com/amplab/keystone/pull/224.diff","patch_url":"https://github.com/amplab/keystone/pull/224.patch","issue_url":"https://api.github.com/repos/amplab/keystone/issues/224","number":224,"state":"open","locked":false,"title":"Auto caching rule","user":{"login":"tomerk","id":676357,"avatar_url":"https://avatars.githubusercontent.com/u/676357?v=3","gravatar_id":"","url":"https://api.github.com/users/tomerk","html_url":"https://github.com/tomerk","followers_url":"https://api.github.com/users/tomerk/followers","following_url":"https://api.github.com/users/tomerk/following{/other_user}","gists_url":"https://api.github.com/users/tomerk/gists{/gist_id}","starred_url":"https://api.github.com/users/tomerk/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tomerk/subscriptions","organizations_url":"https://api.github.com/users/tomerk/orgs","repos_url":"https://api.github.com/users/tomerk/repos","events_url":"https://api.github.com/users/tomerk/events{/privacy}","received_events_url":"https://api.github.com/users/tomerk/received_events","type":"User","site_admin":false},"body":"Added auto-caching rules w/ aggressive naive, and greedy profiling strategies\r\n@etrain \r\n@shivaram ","created_at":"2016-02-06T04:09:11Z","updated_at":"2016-02-10T01:00:25Z","closed_at":null,"merged_at":null,"merge_commit_sha":"74e437bd1557dfe1f1a9f30aec8af2c4673c69af","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/amplab/keystone/pulls/224/commits","review_comments_url":"https://api.github.com/repos/amplab/keystone/pulls/224/comments","review_comment_url":"https://api.github.com/repos/amplab/keystone/pulls/comments{/number}","comments_url":"https://api.github.com/repos/amplab/keystone/issues/224/comments","statuses_url":"https://api.github.com/repos/amplab/keystone/statuses/a0a2dbc051e2211b2d3497454bd63dff992dca57","head":{"label":"tomerk:auto-cache-new","ref":"auto-cache-new","sha":"a0a2dbc051e2211b2d3497454bd63dff992dca57","user":{"login":"tomerk","id":676357,"avatar_url":"https://avatars.githubusercontent.com/u/676357?v=3","gravatar_id":"","url":"https://api.github.com/users/tomerk","html_url":"https://github.com/tomerk","followers_url":"https://api.github.com/users/tomerk/followers","following_url":"https://api.github.com/users/tomerk/following{/other_user}","gists_url":"https://api.github.com/users/tomerk/gists{/gist_id}","starred_url":"https://api.github.com/users/tomerk/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tomerk/subscriptions","organizations_url":"https://api.github.com/users/tomerk/orgs","repos_url":"https://api.github.com/users/tomerk/repos","events_url":"https://api.github.com/users/tomerk/events{/privacy}","received_events_url":"https://api.github.com/users/tomerk/received_events","type":"User","site_admin":false},"repo":{"id":36905160,"name":"keystone","full_name":"tomerk/keystone","owner":{"login":"tomerk","id":676357,"avatar_url":"https://avatars.githubusercontent.com/u/676357?v=3","gravatar_id":"","url":"https://api.github.com/users/tomerk","html_url":"https://github.com/tomerk","followers_url":"https://api.github.com/users/tomerk/followers","following_url":"https://api.github.com/users/tomerk/following{/other_user}","gists_url":"https://api.github.com/users/tomerk/gists{/gist_id}","starred_url":"https://api.github.com/users/tomerk/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tomerk/subscriptions","organizations_url":"https://api.github.com/users/tomerk/orgs","repos_url":"https://api.github.com/users/tomerk/repos","events_url":"https://api.github.com/users/tomerk/events{/privacy}","received_events_url":"https://api.github.com/users/tomerk/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/tomerk/keystone","description":"Simplifying robust end-to-end machine learning on Apache Spark.","fork":true,"url":"https://api.github.com/repos/tomerk/keystone","forks_url":"https://api.github.com/repos/tomerk/keystone/forks","keys_url":"https://api.github.com/repos/tomerk/keystone/keys{/key_id}","collaborators_url":"https://api.github.com/repos/tomerk/keystone/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/tomerk/keystone/teams","hooks_url":"https://api.github.com/repos/tomerk/keystone/hooks","issue_events_url":"https://api.github.com/repos/tomerk/keystone/issues/events{/number}","events_url":"https://api.github.com/repos/tomerk/keystone/events","assignees_url":"https://api.github.com/repos/tomerk/keystone/assignees{/user}","branches_url":"https://api.github.com/repos/tomerk/keystone/branches{/branch}","tags_url":"https://api.github.com/repos/tomerk/keystone/tags","blobs_url":"https://api.github.com/repos/tomerk/keystone/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/tomerk/keystone/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/tomerk/keystone/git/refs{/sha}","trees_url":"https://api.github.com/repos/tomerk/keystone/git/trees{/sha}","statuses_url":"https://api.github.com/repos/tomerk/keystone/statuses/{sha}","languages_url":"https://api.github.com/repos/tomerk/keystone/languages","stargazers_url":"https://api.github.com/repos/tomerk/keystone/stargazers","contributors_url":"https://api.github.com/repos/tomerk/keystone/contributors","subscribers_url":"https://api.github.com/repos/tomerk/keystone/subscribers","subscription_url":"https://api.github.com/repos/tomerk/keystone/subscription","commits_url":"https://api.github.com/repos/tomerk/keystone/commits{/sha}","git_commits_url":"https://api.github.com/repos/tomerk/keystone/git/commits{/sha}","comments_url":"https://api.github.com/repos/tomerk/keystone/comments{/number}","issue_comment_url":"https://api.github.com/repos/tomerk/keystone/issues/comments{/number}","contents_url":"https://api.github.com/repos/tomerk/keystone/contents/{+path}","compare_url":"https://api.github.com/repos/tomerk/keystone/compare/{base}...{head}","merges_url":"https://api.github.com/repos/tomerk/keystone/merges","archive_url":"https://api.github.com/repos/tomerk/keystone/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/tomerk/keystone/downloads","issues_url":"https://api.github.com/repos/tomerk/keystone/issues{/number}","pulls_url":"https://api.github.com/repos/tomerk/keystone/pulls{/number}","milestones_url":"https://api.github.com/repos/tomerk/keystone/milestones{/number}","notifications_url":"https://api.github.com/repos/tomerk/keystone/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/tomerk/keystone/labels{/name}","releases_url":"https://api.github.com/repos/tomerk/keystone/releases{/id}","deployments_url":"https://api.github.com/repos/tomerk/keystone/deployments","created_at":"2015-06-05T01:29:58Z","updated_at":"2016-01-21T20:52:37Z","pushed_at":"2016-02-09T18:51:10Z","git_url":"git://github.com/tomerk/keystone.git","ssh_url":"git@github.com:tomerk/keystone.git","clone_url":"https://github.com/tomerk/keystone.git","svn_url":"https://github.com/tomerk/keystone","homepage":"http://keystone-ml.org/","size":17008,"stargazers_count":0,"watchers_count":0,"language":"Scala","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":true,"forks_count":1,"mirror_url":null,"open_issues_count":0,"forks":1,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"amplab:master","ref":"master","sha":"7b6683d62ec39b4ffde04a29fc5274c56e5c38d7","user":{"login":"amplab","id":1438454,"avatar_url":"https://avatars.githubusercontent.com/u/1438454?v=3","gravatar_id":"","url":"https://api.github.com/users/amplab","html_url":"https://github.com/amplab","followers_url":"https://api.github.com/users/amplab/followers","following_url":"https://api.github.com/users/amplab/following{/other_user}","gists_url":"https://api.github.com/users/amplab/gists{/gist_id}","starred_url":"https://api.github.com/users/amplab/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/amplab/subscriptions","organizations_url":"https://api.github.com/users/amplab/orgs","repos_url":"https://api.github.com/users/amplab/repos","events_url":"https://api.github.com/users/amplab/events{/privacy}","received_events_url":"https://api.github.com/users/amplab/received_events","type":"Organization","site_admin":false},"repo":{"id":33748726,"name":"keystone","full_name":"amplab/keystone","owner":{"login":"amplab","id":1438454,"avatar_url":"https://avatars.githubusercontent.com/u/1438454?v=3","gravatar_id":"","url":"https://api.github.com/users/amplab","html_url":"https://github.com/amplab","followers_url":"https://api.github.com/users/amplab/followers","following_url":"https://api.github.com/users/amplab/following{/other_user}","gists_url":"https://api.github.com/users/amplab/gists{/gist_id}","starred_url":"https://api.github.com/users/amplab/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/amplab/subscriptions","organizations_url":"https://api.github.com/users/amplab/orgs","repos_url":"https://api.github.com/users/amplab/repos","events_url":"https://api.github.com/users/amplab/events{/privacy}","received_events_url":"https://api.github.com/users/amplab/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/amplab/keystone","description":"Simplifying robust end-to-end machine learning on Apache Spark.","fork":false,"url":"https://api.github.com/repos/amplab/keystone","forks_url":"https://api.github.com/repos/amplab/keystone/forks","keys_url":"https://api.github.com/repos/amplab/keystone/keys{/key_id}","collaborators_url":"https://api.github.com/repos/amplab/keystone/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/amplab/keystone/teams","hooks_url":"https://api.github.com/repos/amplab/keystone/hooks","issue_events_url":"https://api.github.com/repos/amplab/keystone/issues/events{/number}","events_url":"https://api.github.com/repos/amplab/keystone/events","assignees_url":"https://api.github.com/repos/amplab/keystone/assignees{/user}","branches_url":"https://api.github.com/repos/amplab/keystone/branches{/branch}","tags_url":"https://api.github.com/repos/amplab/keystone/tags","blobs_url":"https://api.github.com/repos/amplab/keystone/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/amplab/keystone/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/amplab/keystone/git/refs{/sha}","trees_url":"https://api.github.com/repos/amplab/keystone/git/trees{/sha}","statuses_url":"https://api.github.com/repos/amplab/keystone/statuses/{sha}","languages_url":"https://api.github.com/repos/amplab/keystone/languages","stargazers_url":"https://api.github.com/repos/amplab/keystone/stargazers","contributors_url":"https://api.github.com/repos/amplab/keystone/contributors","subscribers_url":"https://api.github.com/repos/amplab/keystone/subscribers","subscription_url":"https://api.github.com/repos/amplab/keystone/subscription","commits_url":"https://api.github.com/repos/amplab/keystone/commits{/sha}","git_commits_url":"https://api.github.com/repos/amplab/keystone/git/commits{/sha}","comments_url":"https://api.github.com/repos/amplab/keystone/comments{/number}","issue_comment_url":"https://api.github.com/repos/amplab/keystone/issues/comments{/number}","contents_url":"https://api.github.com/repos/amplab/keystone/contents/{+path}","compare_url":"https://api.github.com/repos/amplab/keystone/compare/{base}...{head}","merges_url":"https://api.github.com/repos/amplab/keystone/merges","archive_url":"https://api.github.com/repos/amplab/keystone/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/amplab/keystone/downloads","issues_url":"https://api.github.com/repos/amplab/keystone/issues{/number}","pulls_url":"https://api.github.com/repos/amplab/keystone/pulls{/number}","milestones_url":"https://api.github.com/repos/amplab/keystone/milestones{/number}","notifications_url":"https://api.github.com/repos/amplab/keystone/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/amplab/keystone/labels{/name}","releases_url":"https://api.github.com/repos/amplab/keystone/releases{/id}","deployments_url":"https://api.github.com/repos/amplab/keystone/deployments","created_at":"2015-04-10T20:16:11Z","updated_at":"2016-02-03T17:23:01Z","pushed_at":"2016-02-09T19:25:55Z","git_url":"git://github.com/amplab/keystone.git","ssh_url":"git@github.com:amplab/keystone.git","clone_url":"https://github.com/amplab/keystone.git","svn_url":"https://github.com/amplab/keystone","homepage":"http://keystone-ml.org/","size":17177,"stargazers_count":289,"watchers_count":289,"language":"Scala","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":true,"forks_count":59,"mirror_url":null,"open_issues_count":43,"forks":59,"open_issues":43,"watchers":289,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/amplab/keystone/pulls/224"},"html":{"href":"https://github.com/amplab/keystone/pull/224"},"issue":{"href":"https://api.github.com/repos/amplab/keystone/issues/224"},"comments":{"href":"https://api.github.com/repos/amplab/keystone/issues/224/comments"},"review_comments":{"href":"https://api.github.com/repos/amplab/keystone/pulls/224/comments"},"review_comment":{"href":"https://api.github.com/repos/amplab/keystone/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/amplab/keystone/pulls/224/commits"},"statuses":{"href":"https://api.github.com/repos/amplab/keystone/statuses/a0a2dbc051e2211b2d3497454bd63dff992dca57"}}}}