Václav Pech

Speculative calculations

Today a condensed post on a simple yet useful experimental concept from the next GPars version - speculative calculations.

A problem to solve

Imagine you need to perform a long-running task like calculating a time-expensive function or reading data from a file, database or internet. In adition to that, you know of several good ways (e.g. functions or urls) to achieve your goal. However, they are not all equal. Although they return back the same (as far as your needs are concerned) result, they may all take different amount of time to complete and some of them may even fail (due to e.g. network issues). And what's even worse, no-one is going to tell you up-front, which path (algorithm, url, file) will give you the solution first nor which paths lead to no solution at all. Shall I run quick sort or merge sort on my list? Which url will work best? Is this service available at its primary location or should I use the backup one?

Speculations to the rescue (for some)

GPars speculations give you the option to try all the available alternatives in parallel and so get the result from the fastest successful path, silently ignoring the slow or broken ones. This is what the speculate() methods on GParsPool and GParsExecutorsPool() can do.

def numbers = ...
def quickSort = ...
def mergeSort = ...
def sortedNumbers = speculate(quickSort, mergeSort)

Here we're performing both quick sort and merge sort concurrently, while getting the result of the faster one. Given the parallel resources available these days on mainstream hardware, on many setups running the two functions in parallel will not have dramatic impact on the speed of calculation of either one, and so we get the result in about the same time as if we ran solely the faster of the two calculations. And we get the result sooner than when running the slower one. Yet we didn't have to know up-front, which of the two sorting algorithms would perform better on our data. Thus we speculated.

Similarly, downloading a document from multiple network sources of different speed and reliability would somewhat look like this:

import static groovyx.gpars.GParsPool.speculate
import static groovyx.gpars.GParsPool.withPool

def alternative1 = {
    'http://www.dzone.com/links/index.html'.toURL().text
}

def alternative2 = {
    'http://www.dzone.com/'.toURL().text
}

def alternative3 = {
    'http://www.dzzzzzone.com/'.toURL().text  //wrong url
}

def alternative4 = {
    'http://dzone.com/'.toURL().text
}

withPool(4) {
    println speculate([alternative1, alternative2, alternative3, alternative4]).contains('groovy')
}

To become a concurrent speculator, checkout the recent GPars 0.11 snapshot and consider reading the snapshot user guide. We're looking forward to your feedback on the project mailinglist.

Posted at 06:19AM Sep 03, 2010 by Vaclav Pech in Groovy  |  Comments[6]