Understanding parallel exists and find

Question

I take a List[Int] and want to search for a value x where x * 10 > 500 in parallel. So exists should return true if the list contains any value of 51 or greater.

def f(x: Int) = {
  println("calculating for " + x)
  Thread.sleep(100 - x)
  println("finished " + x)
  x * 10
}

val res = List.range(1, 100).par.exists(f(_) > 500)

Which gives results:

calculating for 1
calculating for 25
calculating for 50
calculating for 75
calculating for 13
finished 75          // <-- first valid result found: 75 * 10 > 500
finished 50
calculating for 51   // but it kicks off more expensive calculations
finished 25
calculating for 26   
finished 13
calculating for 14   
finished 1
calculating for 2
finished 51
finished 26
calculating for 27   // and more
finished 14
calculating for 15
finished 2
calculating for 3
finished 27
calculating for 28
finished 15
calculating for 16
finished 3
calculating for 4    // and more...
finished 28
calculating for 29
finished 16
calculating for 17
finished 29
calculating for 30
finished 4
calculating for 5
finished 17
calculating for 18
finished 30
finished 5
calculating for 6
finished 18
finished 6
res: Boolean = true

I am using a dual-core machine with Scala 2.9.1.

What's going on here? Is this working as intended? Why doesn't it just send out the message to the other threads to abort mission as soon as the first result is found? This could be quite costly if f is an expensive computation.

find seems to work in a similar way, searching many more values, even though the docs say that the "element may not necessarily be the first such element in the iteration order" and "the choice is nondeterministic".

Answer 1

Why doesn't it just send out the message to the other threads to abort mission as soon as the first result is found?

Because that is not possible. JAVA DOES NOT LET YOU DO THAT. Or, rather, it does, but it is deprecated.

See description of (deprecated) Thread.stop():

This method is inherently unsafe. Stopping a thread with Thread.stop causes it to unlock all of the monitors that it has locked (as a natural consequence of the unchecked ThreadDeath exception propagating up the stack). If any of the objects previously protected by these monitors were in an inconsistent state, the damaged objects become visible to other threads, potentially resulting in arbitrary behavior. Many uses of stop should be replaced by code that simply modifies some variable to indicate that the target thread should stop running. The target thread should check this variable regularly, and return from its run method in an orderly fashion if the variable indicates that it is to stop running. If the target thread waits for long periods (on a condition variable, for example), the interrupt method should be used to interrupt the wait. For more information, see Why are Thread.stop, Thread.suspend and Thread.resume Deprecated?.

In other words, because multithreaded code with locks are inherently broken, they deprecated a perfectly fine method that can be happily used with threads that do not share mutable state and, therefore, need not lock data structures.

Answer 2

I understand the desire, because I thought myself it would be nice, to have such a behaviour - from the intention to use fast exiting code, it looks reasonable to expect it, but of course, how should it be implemented?

In shortcutting expressions, the next call isn't started, if the result is found - that is easy.

But how do you run behind an offired task, and catch it again to stop it? You would need to know which of them has already finished, and might step into a race condition, because while testing, whether it is still running, it might return 'true', but finish immeadeately afterwards.

The function which is called inside exists could start new Threads itself - how should they be stopped from outside in a general way? By providing an optional stop execution-method as second parameter perhaps?