Multithreading -- matching instances

I want to run two XPath-Expressions concurrently on two revisions of a database which both return results from an Iterator/Iterable and match resulting nodes with nodes in a List.

I think the best thing is to run both queries in two threads from an executorservice and save results from both threads in a BlockingQueue, whereas another Thread is going to sort the results from the BlockingQueue or actually saves the incoming nodes or nodeKeys in the right position.

Then it's trivial to get the intersection of the resulting sorted List and another sorted List.

Any other suggestions? I'm also free to use whatever technology I like (preferably Java). Guava is in the classpath, but I already thought about using Actors from Akka.

Edit: An additional related question would b开发者_JS百科e if it's faster to use InsertionSort in a pipeline manner (to process the generated XPath results right when they are received) or to wait until the whole result has been generated and use QuickSort or MergeSort. I think InsertionSort should be preferable regardless of the resulting number of elements.

In general I hope sorting and then computing the intersection of two lists is faster than O(n^2) for the search of each item in the XPath result list, even if the list is divided by the number of CPU processors available.

Edit: I've currently implemented the first part:

final ExecutorService executor = Executors.newFixedThreadPool(2);
final AbsTemporalAxis axis =
    new NextRevisionAxis.Builder(mSession).setRevision(mRevision)
        .setIncludeSelf(EIncludeSelf.YES).build();
for (final IReadTransaction rtx : axis) {
    final ListenableFuture<Void> future =
        Futures.makeListenable(executor.submit(new XPathEvaluation(rtx, mQuery)));
    future.addListener(new Runnable() {
        @Override
        public void run() {
            try {
                mSemaphore.acquire();
            } catch (final InterruptedException e) {
                LOGWRAPPER.error(e.getMessage(), e);
            }
        }
    }, executor);
}
executor.shutdown();

final ExecutorService sameThreadExecutor = MoreExecutors.sameThreadExecutor();
sameThreadExecutor.submit(new XPathResult());
sameThreadExecutor.shutdown();
return null;

The semaphore is initialized to 2 and in XPathEvaluation the resulting nodeKeys are added to a LinkedBlockingQueue.

Then I'm going to sort the XPathResults denoted with the comment, which isn't implemented yet:

private final class XPathResult implements Callable<Void> {
    @Override
    public Void call() throws AbsTTException, InterruptedException {
        while (true) {
            final long key = mQueue.take();
            if (key == -1L) {
                break;
            }
            if (mSemaphore.availablePermits() == 0) {
                mQueue.put(-1L);
            }

            // Do InsertionSort.
        }

        return null;
    }
}

Without any JavaDoc, but I think at least it should work, what do you think? Do you have any preferable solutions or do I have made some mistakes so far?

kind regards,

Johannes

Are you sure you need to do this concurrently? Can't you just build the two lists consecutively and after that perform your sorting/intersecting? - That would take a lot of complexity from the subject.

I assume that intersecting cannot be done until both lists are filled completely, am I correct? Then, no queue or synchronization would be needed, just fill two lists/sets and, once done, process both full lists.

But maybe I'm not quite getting your point...