What's the best strategy for use in concurrent applications?

[smattheis]

First of all, thanks for sharing the source code of your research work, which I think demonstrates, in combination with your papers, an exemplary attitude for conducting and publishing research work!

My question: As far as I understand, this implementation is not thread-safe. Is this correct? If so, what's the best way to use this library in concurrent applications, e.g., global lock or is this data structure kind of reactive and enables transactional modifications?

Further, is the library's implementation of iterators thread-safe? If iterators are thread-safe, I would use a fine-grained synchronization like this (pseudo)-code:

public Set<T> query(...) {
    Iterator<T> it = null;
    Set<T> result = new HashSet<T>();
    synchronized (tree) {
        it = tree.query(...);
    }
    while (it.hasNext()) {
        result.add(it.next());
    }
    return result;
}

... otherwise this: (... which must, by the way, be similar to what would be required in the implementation of the iterators for storing a snapshot of the query result, if they are thread-safe but the data structure is not. The questions is just, what can I presume?)

public class ThreadsafeTree {
    private PHTree tree = new PHTree(...);

    public synchronized Set<T> query(...) {
        Iterator<T> it = tree.query(...);
        Set<T> result = new HashSet<T>();
        while (it.hasNext()) {
            result.add(it.next());
        }
        return result;
    }
    ...
}

[tzaeschke]

Well, thanks for you interest in my research :-).

Read only access (queries etc.) can be done concurrently by any number of threads without synchronization.

However, once you start updating the tree (insert, remove, update), you need to synchronize everything. Iterators also do not create a copy of the result set, so iterating over the result needs to be synchronized. There is a possible (untested) optimisation here, that is, you may be able to drop the readlock between calls to next(). This could be useful if you are iterating over very large result sets and would like to perform updates on the tree in the meantime. However, this is untested and there is not guarantee that it works. If you try that, let me know if it works or not, I may be able to fix this without compromising single-threaded performance.

I updated the README (near the bottom) with a section about concurrency. This should cover most of the details.

Please let me know if you any comments or if anything is unclear.

[tzaeschke]

Btw, to reduce garbage collection effort, it can make sense to create the query object only once with PhQuery<T> it = tree.query(...); and then call it.reset(...) whenever you need to perform a query.

Query objects are rather complex and can consists of 100 objects or so.