CODEWITHSUNDEEP
javaandroidmultithreadingconcurrencyqueue
Oliver Hausler
Oliver Hausler

Reputation: 4987

Is ConcurrentLinkedQueue a good choice if poll does not necessarily return the first item?

I have the use-case, where a queue holds UploadItem(s). The queue must be thread-safe. UploadItem has a method canUpload(). UploadItems are added to the queue at the tail, but peek() and poll() must return the first UploadItem where canUpload() is true. This may be the item at the head or a newer item. Essentially, I want items to be ignored until they are ready for upload, and I want the queue to return the oldest item that's ready.

To solve the job, I have extended a ConcurrentLinkedQueue and I have overridden peek() and poll(). I have synchronized the overriden methods and I am using an iterator to retrieve the first valid item.

public class UploadQueue extends ConcurrentLinkedQueue<UploadItem> {

    public UploadQueue() {}

    @Override public synchronized UploadItem peek() {
        for (UploadItem item : this) {
            if (item.canUpload()) {
                return item;
            }
        }
        return null;
    }

    @Override public synchronized UploadItem poll() {
        for (UploadItem item : this) {
            if (item.canUpload()) {
                remove(item);

                return item;
            }
        }
        return null;
    }

}

Is this a good implementation or can this be done more efficient? Does using the iterator to retrieve items have any adverse effects? I can't pick items using an index and get() so it seems I must use the iterator. I can't track items in an internal variable either, because they are linked and changed by outside functions.

This will be run on Android and Android still uses Java 6. In face of Lock-Free Concurrent Linked List in Java and ConcurrentLinkedQueue$Node remains in heap after remove(), is there any risk that some Android phones may still have the Java memory leak? Does anybody know if Java is typically updated/patched on Android (within its major version)?

Upvotes: 0

Views: 1226

Answers (2)

Stephen C
Stephen C

Reputation: 719239

Is this a good implementation or can this be done more efficient?

Those two criteria are not mutually exclusive.

And furthermore, without knowing how costly canUpload is, how large the queue will get, and how long the entries remain in the "not uploadable" state, it is not possible to say whether efficiency is likely to be an issue.

However, it is certainly possible to do this more efficiently. For example, if you can arrange that the transition from "not uploadable" to "uploadable" triggers an event of some kind, then you could arrange that the event handler adds the UploadItem to the queue.

And it may be that a round-robin scan of a collection of UploadItem objects will be more efficient than scanning from the start of the queue each time. Other possible strategies may work better too.

But these alternative approaches may also change the order in which uploads occur ... if that is an issue for you.

Does using the iterator to retrieve items have any adverse effects?

The iterator for a ConcurrentLinkedQueue is weakly consistent. This means that you are not guaranteed to see entries that were added after an iteration commences. That probably isn't a problem for your use-case. (I don't imagine it matters a lot if downloads occasionally get deferred to the next cycle of queue polling.)

This will be run on Android and Android still uses Java 6. In face of Lock-Free Concurrent Linked List in Java and ConcurrentLinkedQueue$Node remains in heap after remove(), is there any risk that some Android phones may still have the Java memory leak?

Those questions don't indicate a long-term memory leak to me. If there is a leak, it looks like it is likely to be cleared when the thread discards the iterator ... or something like that.

On the other hand, those Q&A's were written about Oracle / OpenJDK Java, not the Apache Harvest / Android clean-room reimplementation.

Does anybody know if Java is typically updated/patched on Android (within its major version)?

You can't generalize.

First, the Android implementation of the Java libraries are a different codebase to the standard Oracle / OpenJDK codebase. So updates / patches to the latter are not applicable to the former.

Second, even if updates / patches are made to the standard Android distros, there is no guarantee that 1) the phone manufacturers will pick them up, 2) they will hit the phone company distribution channels, or 3) individual smartphone owners will apply them.

Upvotes: 1

user207421
user207421

Reputation: 310980

Use a PriorityQueue with a Comparator that compares first on canUpload and then on reverse order of date.

Upvotes: 0

Related Questions