{"action":"created","issue":{"url":"https://api.github.com/repos/apache/spark/issues/8178","labels_url":"https://api.github.com/repos/apache/spark/issues/8178/labels{/name}","comments_url":"https://api.github.com/repos/apache/spark/issues/8178/comments","events_url":"https://api.github.com/repos/apache/spark/issues/8178/events","html_url":"https://github.com/apache/spark/pull/8178","id":100878468,"number":8178,"title":"[SPARK-9952] Fix N^2 loop when DAGScheduler.getPreferredLocsInternal accesses cacheLocs","user":{"login":"JoshRosen","id":50748,"avatar_url":"https://avatars.githubusercontent.com/u/50748?v=3","gravatar_id":"","url":"https://api.github.com/users/JoshRosen","html_url":"https://github.com/JoshRosen","followers_url":"https://api.github.com/users/JoshRosen/followers","following_url":"https://api.github.com/users/JoshRosen/following{/other_user}","gists_url":"https://api.github.com/users/JoshRosen/gists{/gist_id}","starred_url":"https://api.github.com/users/JoshRosen/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/JoshRosen/subscriptions","organizations_url":"https://api.github.com/users/JoshRosen/orgs","repos_url":"https://api.github.com/users/JoshRosen/repos","events_url":"https://api.github.com/users/JoshRosen/events{/privacy}","received_events_url":"https://api.github.com/users/JoshRosen/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":20,"created_at":"2015-08-13T21:52:42Z","updated_at":"2015-08-17T04:34:04Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/apache/spark/pulls/8178","html_url":"https://github.com/apache/spark/pull/8178","diff_url":"https://github.com/apache/spark/pull/8178.diff","patch_url":"https://github.com/apache/spark/pull/8178.patch"},"body":"In Scala, `Seq.fill` always seems to return a List. Accessing a list by index is an O(N) operation. Thus, the following code will be really slow (~10 seconds on my machine):\r\n\r\n```scala\r\nval numItems = 100000\r\nval s = Seq.fill(numItems)(1)\r\nfor (i <- 0 until numItems) s(i)\r\n```\r\n\r\nIt turns out that we had a loop like this in DAGScheduler code, although it's a little tricky to spot. In `getPreferredLocsInternal`, there's a call to `getCacheLocs(rdd)(partition)`.  The `getCacheLocs` call returns a Seq. If this Seq is a List and the RDD contains many partitions, then indexing into this list will cost O(partitions). Thus, when we loop over our tasks to compute their individual preferred locations we implicitly perform an N^2 loop, reducing scheduling throughput.\r\n\r\nThis patch fixes this by replacing `Seq` with `Array`."},"comment":{"url":"https://api.github.com/repos/apache/spark/issues/comments/131676272","html_url":"https://github.com/apache/spark/pull/8178#issuecomment-131676272","issue_url":"https://api.github.com/repos/apache/spark/issues/8178","id":131676272,"user":{"login":"SparkQA","id":8108735,"avatar_url":"https://avatars.githubusercontent.com/u/8108735?v=3","gravatar_id":"","url":"https://api.github.com/users/SparkQA","html_url":"https://github.com/SparkQA","followers_url":"https://api.github.com/users/SparkQA/followers","following_url":"https://api.github.com/users/SparkQA/following{/other_user}","gists_url":"https://api.github.com/users/SparkQA/gists{/gist_id}","starred_url":"https://api.github.com/users/SparkQA/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/SparkQA/subscriptions","organizations_url":"https://api.github.com/users/SparkQA/orgs","repos_url":"https://api.github.com/users/SparkQA/repos","events_url":"https://api.github.com/users/SparkQA/events{/privacy}","received_events_url":"https://api.github.com/users/SparkQA/received_events","type":"User","site_admin":false},"created_at":"2015-08-17T04:34:04Z","updated_at":"2015-08-17T04:34:04Z","body":"**[Test build #41003 timed out](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/41003/console)**     for PR 8178 at commit [`6e5fdc2`](https://github.com/apache/spark/commit/6e5fdc2974c536593a5df6b244537cc6e2c33196)     after a configured wait of `175m`."}}