Sliding window with 50% overlap with producer/consumer threads

Question

I have the following scenario in Java:

• 1 producer thread stores event objects into a queue. Blocking it is not an option. It should always just store each element at the end of the queue and exit (so no bounded queues).
• 1 consumer thread waits for the queue to have WINDOW_SIZE number of events in it. It should then retrieve all WINDOW_SIZE events from the queue for processing, but only remove half of them (i.e. WINDOW_SIZE/2), for a 50% overlap.

My question is, which (concurrent) collection would you use to implement this efficiently? The events come in at 100Hz on a resource-limited device (a mobile phone running Android). I thought of using the following, none of which seem to be a proper fit:

1. A ConcurrentLinkedQueue, checking for queue size each time it is modified, and using peek()/poll() in the consumer when WINDOW_SIZE events are available. This seems a bit cumbersome.
2. An ArrayBlockingQueue, again checking for queue size, and using drainTo(). However, that method has the following documentation: "[...] Further, the behavior of this operation is undefined if the specified collection is modified while the operation is in progress. [...]". This seems a bit odd for a concurrent collection.

Here's some example code:

import java.util.Queue;

import com.google.common.collect.Queues;

public class AccelerometerProcessor implements Runnable {

    private static final int WINDOW_SIZE = 128;

    private final Queue<AccelerometerEvent> eventQueue = Queues.newConcurrentLinkedQueue();

    @Override
    public void run() {
        while (!Thread.interrupted()) {
            try {
                synchronized (eventQueue) {
                    while (eventQueue.size() < WINDOW_SIZE) {
                        eventQueue.wait();
                    }

                    // We have WINDOW_SIZE eventQueue, start processing
                }
            } catch (InterruptedException e) {
                // Do nothing
            }
        }
    }

    public void addAccelerometerEvent(AccelerometerEvent accelerometerEvent) {
        synchronized (eventQueue) {
            eventQueue.add(accelerometerEvent);
            eventQueue.notifyAll();
        }
    }
}

I'm using Google Guava also, by the way, so if there's a nice collection in there I haven't heard about, please refer me.

So: Any good ideas how to solve this efficiently and cleanly?

Answer 1

If you're always going to consume WINDOW_SIZE/2 events en bloc, why doesn't the producer thread (you said there's only one) fill an array of size WINDOW_SIZE/2 and pass it to the queue once it's full?