The queue that got slower as it drained

import java.util.*;

/**
 * Root cause: `backlog.remove(0)` on an ArrayList is O(n), not O(1).
 *
 * ArrayList keeps its elements contiguously. Removing index 0 has to shift
 * every remaining element down one slot, which it does with System.arraycopy —
 * exactly what the thread dump showed. One poll of a 30,000-element backlog
 * moves 29,999 elements.
 *
 * Draining the whole backlog that way moves 29,999 + 29,998 + ... + 0, which is
 * n(n-1)/2 ≈ 450 million element moves for 30,000 jobs. That is the collapse.
 * It is pure CPU inside arraycopy: no locks, no GC, no I/O — which is precisely
 * why every other hypothesis was ruled out and the incidents got closed as
 * "transient load". It recovered on its own because the cost falls as the
 * backlog shrinks.
 *
 * Why it hid for two years: at a few hundred jobs, n^2/2 is a few tens of
 * thousands of moves — genuinely free. The bug did not appear under load; it
 * was always there and only became visible when n grew. Nothing about the code
 * changed.
 *
 * Why not LinkedList: it would make head removal genuinely O(1) and would fix
 * this. But you would then pay a Node allocation per job (~24 bytes of overhead
 * each, so ~700 KB of pure overhead for this backlog) plus GC churn, and any
 * indexed access anywhere else in the class becomes O(n).
 *
 * ArrayDeque is the right answer. It is a circular array: removing from the head
 * moves a head index instead of moving elements, so nothing is shifted and
 * nothing is allocated per element. Its own Javadoc says it is "likely to be
 * faster than LinkedList when used as a queue". It has been available since
 * Java 6.
 *
 * The one thing to be careful about: ArrayDeque is not a List, so if the
 * surrounding code indexes into the backlog you have to change that too. Here
 * it only polls, so the swap is direct.
 */
public class Solution {

    static final int JOBS = 30_000;

    /** Same instrumentation, so the two runs are comparable. */
    static final class InstrumentedList<E> extends ArrayList<E> {
        long elementsMoved;

        @Override
        public E remove(int index) {
            elementsMoved += size() - index - 1;
            return super.remove(index);
        }
    }

    public static void main(String[] args) {
        // THE FIX: a queue, used as a queue.
        Deque<String> backlog = new ArrayDeque<>();
        for (int i = 0; i < JOBS; i++) backlog.addLast("job-" + i);

        System.out.println("jobs queued      = " + JOBS);

        int processed = 0;
        String first = null;
        String last = null;
        long start = System.nanoTime();
        while (!backlog.isEmpty()) {
            String job = backlog.pollFirst();   // O(1), shifts nothing
            if (processed == 0) first = job;
            last = job;
            processed++;
        }
        long millis = (System.nanoTime() - start) / 1_000_000;

        System.out.println("jobs processed   = " + processed);
        System.out.println("first job out    = " + first + "   (FIFO expects job-0)");
        System.out.println("last job out     = " + last);
        System.out.println("elements moved   = 0   (head index advances instead)");
        System.out.println("wall clock       = " + millis + "ms");

        // Proof of the diagnosis: the original shape, measured.
        InstrumentedList<String> old = new InstrumentedList<>();
        for (int i = 0; i < JOBS; i++) old.add("job-" + i);
        while (!old.isEmpty()) old.remove(0);
        System.out.println("the old way moved = " + old.elementsMoved + " elements");
        System.out.println("expected n(n-1)/2 = " + ((long) JOBS * (JOBS - 1) / 2));

        boolean fifo = "job-0".equals(first);
        boolean allProcessed = processed == JOBS;
        System.out.println(fifo && allProcessed ? "PASS" : "FAIL");
    }
}