Is a concurrency approach a good idea for speeding a long iteration?

Question

I have an app that does an iteration to create points on a graph over time. While I'm gathering data for each point across the x-axis I also must execute a recursive lookup which effectually means I have a loop inside another loop. This is not scaling too well. I don't see a lot of examples of using a "divide and conquer" solution on iterations. I was thinking of using Java's Executor concurrency framework to run each loop in it's own thread, await the answers, gather the results and return them. The initial test results I'm getting don't seem that much faster. I know I should show some code but what I want to know first is if this approach has merit compared to better methods that I may not be familiar with. Thanks in advance!

Adding some groovyish/javaish pseudo code to assist thinking about this:

class Car {
    id
    model 
    make
    weight
}

for (number in listOfImportantCarIDs) {
    Car car = carsMap.get(number) // find the car we care about
    String maker = car.make //get it's 'parent' 

    // get amount of all related cars
    Iterator<Car> allcars = carsMap.values().iterator();
    while (allcars.hasNext()) {
        Car aCar = alldocs.next();
        if (maker.equals(aCar.make)) {
            totalCarCount++;  // increment total related cars 
            BigDecimal totalWeightofAllCars = totalWeightofAllCars.add(aCar.getWeight()); // add weight to total

            // a ghetto cache to prevent double  counting
            countedMaufacturers.add(make); 
        }     
    }
}

Answer 1

i don't think concurrency can make your application faster. it can help you to run multiple task in your application, but it won't make them faster.

my experience: try to get rid of recursive calls, that's the best way to make the app faster.

Answer 2

If the task for computing the y value for each x value is completely atomic for each x value, then I would think this is a good fit for an executor service. Most performance questions simply require measure, even after great lengths of reasoning about the solution. The optimal number of threads for CPU bound problems is p or p+1, keep that in mind.

Have you looked at a Dynamic Programming approach? Is it applicable for your problem? Essentially, recursion means you are solving the same problem over and over again but for slightly smaller input values. When running multiple iterations of the same recursive algorithm a program tends to often re-solve the same exact problem. Instead, a dynamic programming approach might store the solution in a cache and reference the cache before calculation the solution a second time.

Without knowing your exact problem, it is difficult to give an exact answer.

Answer 3

It depends on what's making your loops slow. Are they executing database queries? Accessing a hard disk? Otherwise doing something that causes them to wait around for an external I/O operation? In that case, your best bet is to start adding threads until you stop seeing returns on them, you basically have to tune it.

If they're slow simply because of raw processing taking place in memory in Java, then you could try adding a thread per CPU core on your machine, but probably won't see much benefit beyond that.

Answer 4

Hi, "a loop inside another loop" that should ring bells ;). The outer loop is always waiting for the inner one. So this is a serial execution and using threads wont change a bit. Unless each loop writes the result to a central service which can be consulted by a following event (loop) on your x-axis. So the service would be stateful...

Answer 5

If your "Source" data isn't modified by your algorithm or each iteration only operates on it's own data (doesn't change nearby data) it could give you a (max) 2x speed boost on a dual-core.

That's not a great solution and as the time grows for your current solution, this will grow at 1/2 which is still quite expensive if you are in a double-nested loop. O(X^2/2) still pretty much equals O(X^2).

If you can find a way to optimize your algorithm that has a much higher potential of real success and much less of a potential for an amazing amount of time sunk into bug fixing.

Answer 6

Can each point along the X-axis be computed in parallel? If so, that's your opportunity for performance improvements via multi-threading.

The Fork-Join framework will make this kind of program simple. You can get an early access version, or imitate it yourself to some extent.

Answer 7

Using threads will speed up your application by some small constant factor, at the price of significant added complexity for inter-thread communication. If a better algorithm exists, that can save you orders of magnitude. Therefore, I strongly recommend that you first verify that there indeed isn't a sub-quadratic algorithm to solve your problem.

Perhaps if you detailed the problem you are trying to solve and your current solution, we could assist here.

Edit: Goodness, finding a much better algorithm isn't hard at all:

for (Car car : cars {
    Stats s = stats.get(car.maker);
    if (s == null) {
        s = new Stats();
        stats.put(car.maker, s);
    }
    stats.count++;
    stats.totalWeight+=car.weight;
}

for (Car car in importantCars) {
    stats.get(car.maker);
}

There really is no need to iterate, for each important car, over all cars just to find those with identical maker ...