[
https://issues.apache.org/jira/browse/SPARK-9952?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Josh Rosen updated SPARK-9952:
------------------------------
Priority: Critical (was: Major)
> Fix N^2 loop when DAGScheduler.getPreferredLocsInternal accesses cacheLocs
> --------------------------------------------------------------------------
>
> Key: SPARK-9952
> URL: https://issues.apache.org/jira/browse/SPARK-9952
> Project: Spark
> Issue Type: Improvement
> Components: Scheduler
> Affects Versions: 1.5.0
> Reporter: Josh Rosen
> Assignee: Josh Rosen
> Priority: Critical
>
> In Scala, Seq.fill always returns 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):
> {code}
> val numItems = 100000
> val s = Seq.fill(numItems)(1)
> for (i <- 0 until numItems) s(i)
> {code}
> It turns out that we had a loop like this in DAGScheduler code. 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.
> We can easily fix this by replacing Seq with Array in this code.
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscr...@spark.apache.org
For additional commands, e-mail: issues-h...@spark.apache.org
