concurrent application not as fast as a singlethreaded

I've implemented a pipeline approach. I'm going to traverse a tree and I need certain values which aren't available beforehand... so I have to traverse the tree in parallel (or before) and once more for every node I want to save values (descendantCount for example).

As such I'm interating through the tree, then from the constructor I'm calling a method which invokes a new Thread started through an ExecutorService. The Callable which is submitted is:

    @Override
    public Void call() throws Exception {
        // Get descendants for every node and save it to a list.
        final ExecutorService executor =
            Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors());
        int index = 0;
        final Map<Integer, Diff> diffs = mDiffDatabase.getMap();
        final int depth = diffs.get(0).getDepth().getNewDepth();
        try {
            boolean first = true;
            for (final AbsAxis axis = new DescendantAxis(mNewRtx, true); index < diffs.size()
                && ((diffs.get(index).getDiff() == EDiff.DELETED && depth < diffs.get(index).getDepth()
                    .getOldDepth()) || axis.hasNext());) {
                if (axis.getTransaction().getNode().getKind() == ENodes.ROOT_KIND) {
                    axis.next();
                } else {
                    if (index < diffs.size() && diffs.get(index).getDiff() != EDiff.DELETED) {
                        axis.next();
                    }

                    final Future<Integer> submittedDescendants =
                        executor.submit(new Descendants(mNewRtx.getRevisionNumber(), mOldRtx
                            .getRevisionNumber(), axis.getTransaction().getNode().getNodeKey(), mDb
                            .getSession(), index, diffs));
                    final Future<Modification> submittedModifications =
                        executor.submit(new Modifications(mNewRtx.getRevisionNumber(), mOldRtx
                            .getRevisionNumber(), axis.getTransaction().getNode().getNodeKey(), mDb
                            .getSession(), index, diffs));
                    if (first) {
                        first = false;
                        mMaxDescendantCount = submittedDescendants.get();
                        // submittedModifications.get();
                    }
                    mDescendantsQueue.put(submittedDescendants);
                    mModificationQueue.put(submittedModifications);
                    index++;
                }
            }

            mNewRtx.close();
        } catch (final AbsTTException e) {
            LOGWRAPPER.error(e.getMessage(), e);
        }
        executor.shutdown();
        return null;
    }

Therefore for every node it's creating a new Callable which traverses the tree for every node and counts descendants and modifications (I'm actually fusing two tree-revisions together). Well, mDescendantsQueue and mModificationQueue are BlockingQueues. At first I've only had the descendantsQueue and traversed the tree once more to get modifications of every node (counting modifications made in the subtree of the current node). Then I thought why not do both in parallel and implement a pipelined approach. Sadly the performance seemed to have decreased everytime I've implemented another multithreaded "step".

Maybe because an XML-tree usually isn't that deep and the Concurrency-Overhead is too heavy :-/

At first I did everything sequential, which was the fastest: - traversing the tree - for ev开发者_如何学Pythonery node traverse the descendants and compute descendantCount and modificationCount

After using a pipelined approach with BlockingQueues it seems the performance has decreased, but I haven't actually made any time measures and I would have to revert many changes to go back :( Maybe the performance increases with more CPUs, because I only have a Core2Duo for testing right now.

best regards,

Johannes

Probably this should help: Amadahl's law, what it basically says it that the increase in productivity depends (inversely proportional) to the percentage of the code which has to be processed by synchronization. Hence even by increasing by increasing more computing resources, it wont end up to the better result. Ideally if the ratio of ( the synchronized part to the total part) is low, then with (number of processors +1) should give the best output (unless you are using network or other I/O in which case you can increase the size of the pool). So just follow it up from the above link and see if it helps

From your description it sounds like you're recursively creating threads, each of which processes one node and then spawns a new thread? Is this correct? If so, I'm not surprised that you're suffering from performance degradation.

A simple recursive descent method might actually be the best way to do this. I can't see how multithreading will gain you any advantages here.