Spark-Enabled Cost-Distance - #1999

I think the reference in the doc string is sufficient pointing back to Mr Geo, the type names should probably just be CostDistance

I see the loop version does a count to force the execution and cache the RDD. Is it possible to avoid this foreach with a similar method, where this accumulator is moved to the map, that RDD persisted, and the RDD counted to force execution? Perhaps not the best optimization, but your opinion on this would probably help me understand the logic better.

The foreach is strictly for the side-effects (to set the accumulator).

Gotcha, but it causes a double iteration of the RDD. The accumulator could be set in the map, and then the map executed with caching, so that the RDD transformation is cached and iterated over once, and the accumulator value is set.

Oh right

Have you benchmarked the single-threaded case for this change? It would be good to get numbers to prove this method works faster/just as fast.

I have not run any benchmarks, but (informally) I did not detect any noticeable speed difference.

That having been said, it is possible (even likely) that there is a difference, because the changes that I made were very self-consciously deoptimizations.

That was necessary because the previous algorithm seemed to avoid putting elements into the priority queue whenever it could. That was laudable in the single-threaded case, but in order to maintain coherence in the case were points need to be transferred from some adjacent tile to the present one, I think that it makes sense to have one and only one place for points to enter (to ensure that points coming in from adjacent tiles and ponits that were already in the tile are treated exactly the same).

After getting the basics working, I then took another pass an re-added some mild optimizations. Generally speaking, I am pretty comfortable with were the single-threaded version is.

Discussion point, not a change request: What would it take to create an option to pass in an RDD of points? I'm curious if there are use cases for this, and if it would be possible with the current algorithm.

I think that there would be some mechanical changes needed in order to support an RDD of points, probably the friction layer and the points would need to be joined (either logically or literally) as the first step.

As a practical matter, I do not think that supporting RDDs of points would add any real capability. If someone really did have so many points that they do not fit into memory on one machine and some appreciable percentage of those points have unique projections into the raster, then it is likely that the raster layer is so large (in terms of pixels) that this algorithm would run out of driver memory before even reaching the second iteration (driver memory requirements are a function of the total layer size -- this is unavoidable because propagation across tile boundaries must be coordinated by the driver).

On the other hand, if someone has a source RDD whose points can be clustered (or otherwise reduced) into a fairly small list, then that would be viable option (but that would be unrelated to this work).

Unnecessary parentheses.

@param frictionTile

cfor here would be a bit faster (according to benchmarks on aspect-tif.tif):

cfor(0)(_ < points.length, _ + 1) { i =>
  val (col, row) = points(i)
  q.add((col, row, frictionTile.getDouble(col, row), 0.0))
}

Unnecessary parentheses here too, and in methods below.

@param neighborCost

accumulator.value.nonEmpty

Eh, dirty cast here, you can use pattern match on Bounds[K], and to throw Exception (for example) on EmptyBounds

instead of the direct implicitly call, it is possible to write smth like:

val KeyBounds(minKey: SpatialKey, maxKey: SpatialKey) = bounds
val (minKeyCol, minKeyRow) = minKey

everywhere below can be changed, as there are lots of direct implicitly calls and tuple._{1/2} usages. I'll omit all comments below about the same thing.

it's possible just to upcast DoubleArrayTile up to Tile:

(k, cost: Tile)

to avoid the direct implicitly call it's possible provide explicit type:

val (key: SpatialKey, tile: Tile) = kv

Why don't to use just cfor? It's a common dep for the whole raster package. A bit less ugly ^^'.

Here cfor can be used too

I totally forgot about it, but @echeipesh noticed these locks and reminded about it. @jamesmcclain, have you considered any java concurrent collection usage here, instead of synchronized everywhere?

The most appropriate structure that I found was CopyOnWriteArrayList. The documentation for that class says the following:

This is ordinarily too costly, but may be more efficient than alternatives when traversal operations vastly outnumber mutations, and is useful when you cannot or don't want to synchronize traversals, yet need to preclude interference among concurrent threads. The "snapshot" style iterator method uses a reference to the state of the array at the point that the iterator was created. This array never changes during the lifetime of the iterator, so interference is impossible and the iterator is guaranteed not to throw ConcurrentModificationException. The iterator will not reflect additions, removals, or changes to the list since the iterator was created. Element-changing operations on iterators themselves (remove, set, and add) are not supported. These methods throw UnsupportedOperationException.

(I am pointing in particular to the first sentence.)

I do not think that a synchronized concurrent data structure is warranted here since there is only one place for new data to go (the end of the list).