ArrayDeque microbenchmark

Test.java

import java.util.ArrayDeque;
import java.util.Deque;

class Test {
  static final int LIMIT = 10000;
  static final int BATCH = 100;
  static final int ITERS = 1000;
  public static void main(String[] args) {
    for (int i = 0; i < 20000; ++i) {
       testDLL();
       testAD();
       testBootstrap();
       testBootstrap2();
       testBootstrap3();
    }
    long start = System.nanoTime();
    for (int i = 0; i < ITERS; ++i) {
       testDLL();
    }
    long mid = System.nanoTime();
    for (int i = 0; i < ITERS; ++i) {
       testAD();
    }
    long mid1 = System.nanoTime();
    for (int i = 0; i < ITERS; ++i) {
       testBootstrap();
    }
    long mid2 = System.nanoTime();
    for (int i = 0; i < ITERS; ++i) {
       testBootstrap2();
    }
    long mid3 = System.nanoTime();
    for (int i = 0; i < ITERS; ++i) {
       testBootstrap3();
    }
    long end = System.nanoTime();
    System.out.println("DoublyLinkedList "+(mid-start));
    System.out.println("ArrayDeque       "+(mid1-mid));
    System.out.println("ArrayDequeBoot   "+(mid2-mid1));
    System.out.println("ArrayDequeBoot2  "+(mid3-mid2));
    System.out.println("ArrayDequeBoot3  "+(end-mid3));
    testBootstrap();
  }
  public static void testDLL() {
    DoubleLinkedList<Integer> tasks = new DoubleLinkedList<>();
    DoubleLinkedList<Integer> taskBuffer = new DoubleLinkedList<>();
    tasks.addLast(1);
    int next = 2;
    while (!tasks.isEmpty()) {
      int i = tasks.pop();
      if (i % 5 == 1) {
         for (int j = 0; j < BATCH && next < LIMIT; ++j) {
            taskBuffer.addLast(next++);
         }
      }
      tasks.pushAll(taskBuffer);
    }
  }
  public static void testAD() {
    ArrayDeque<Integer> tasks = new ArrayDeque<>();
    ArrayDeque<Integer> taskBuffer = new ArrayDeque<>();
    tasks.add(1);
    int next = 2;
    while (!tasks.isEmpty()) {
      int i = tasks.pop();
      if (i % 5 == 1) {
         for (int j = 0; j < BATCH && next < LIMIT; ++j) {
            taskBuffer.push(next++);
         }
      }
      while (!taskBuffer.isEmpty()) {
        tasks.push(taskBuffer.pop());
      }
    }
  }
  public static void testBootstrap() {
    ArrayDeque<Integer> tasks = new ArrayDeque<>();
    ArrayDeque<ArrayDeque<Integer>> items = new ArrayDeque<>(); 
    ArrayDeque<Integer> taskBuffer = new ArrayDeque<>();
    tasks.add(1);
    int next = 2;
    while (!tasks.isEmpty()) {
      int i = tasks.pop();
      if (i % 5 == 1) {
         for (int j = 0; j < BATCH && next < LIMIT; ++j) {
            taskBuffer.push(next++);
         }
      }
      if (!taskBuffer.isEmpty()) {
        items.push(taskBuffer);
        taskBuffer = new ArrayDeque<>();
      }
      if (tasks.isEmpty() && !items.isEmpty()) {
        tasks = items.pop();
      }
    }
  }
  public static void testBootstrap2() {
    BootDeque<Integer> tasks = new BootDeque<Integer>();
    ArrayDeque<Integer> taskBuffer = new ArrayDeque<Integer>();
    taskBuffer.push(1);
    tasks.pushBuffer(taskBuffer);
    taskBuffer = new ArrayDeque<Integer>();
    int next = 2;
    while (!tasks.isEmpty()) {
      int i = tasks.pop();
      if (i % 5 == 1) {
         for (int j = 0; j < BATCH && next < LIMIT; ++j) {
            taskBuffer.push(next++);
         }
      }
      if (!taskBuffer.isEmpty()) {
        tasks.pushBuffer(taskBuffer);
        taskBuffer = new ArrayDeque<Integer>();
      }
    }
  }
  static class BootDeque<T> {
    Deque<T> head;
    Deque<Deque<T>> items;

    BootDeque() {
      head = new ArrayDeque<T>();
      items = new ArrayDeque<Deque<T>>();
    }

    public boolean isEmpty() {
      return head.isEmpty() && items.isEmpty();
    }

    public T pop() {
      if (head.isEmpty()) head = items.pop();
      return head.pop();
    }
    public void pushBuffer(Deque<T> buffer) {
      if (!buffer.isEmpty()) {
        if (!head.isEmpty()) {
          items.push(head);
        }
        head = buffer;
      }
    }
  }
  public static void testBootstrap3() {
    ArrayArrayDeque<Integer> tasks = new ArrayArrayDeque<Integer>();
    ArrayDeque<Integer> taskBuffer = new ArrayDeque<Integer>();
    taskBuffer.push(1);
    tasks.pushAll(taskBuffer);
    taskBuffer = new ArrayDeque<Integer>();
    int next = 2;
    while (!tasks.isEmpty()) {
      int i = tasks.pop();
      if (i % 5 == 1) {
         for (int j = 0; j < BATCH && next < LIMIT; ++j) {
            taskBuffer.push(next++);
         }
      }
      if (!taskBuffer.isEmpty()) {
        tasks.pushAll(taskBuffer);
        taskBuffer = new ArrayDeque<Integer>();
      }
    }
  }
}

updated again to make the bounds configurable.

oh, and to fix the BootDeque class a bit, and also to avoid object contruction in the abstracted examples, which actually seems to be the biggest performance hit which I had though was abstraction penalty.