Performance of Java Optional

Optional<T> is just a normal generic class which contains a reference of type T. Thus, it adds a single layer of indirection. The method calls themselves won't be very expensive either, since the class is final and so the dynamic dispatch can be avoided.

The only place where you could have performance problems is when working with very large numbers of such instances, but even then the performance of something like a Stream<Optional<String>> is not bad at all. However, when working with large amounts of primitive values, you'll find a performance hit using Stream<Integer> (or Integer[]) versus the primitive specialization IntStream (or int[]) due to this layer of indirection requiring very frequent instantiation of Integer objects. However, this is a penalty that we already know and do pay when using things like ArrayList<Integer>.

You would obviously experience the same hit with Stream<OptionalInt> / OptionalInt[], since an OptionalInt is basically a class with an int field and a boolean flag for presence (unlike with Optional<T> which can make do with only the T field) and thus quite similar to Integer although bigger in size. And of course, a Stream<Optional<Integer>> would add two levels of indirection, with the corresponding double performance penalty.

I did some performance testing using an algorithm that heavily uses null checks as well as access to a potentially nullable field. I implemented a simple algorithm that removes the middle element from the single linked list.

First I implemented two classes of linked list node: safe - with Optional and unsafe - without.

Safe Node

class Node<T> {
    private final T data;
    private Optional<Node<T>> next = Optional.empty();

    Node(T data) {

        this.data = data;
    }

    Optional<Node<T>> getNext() {
        return next;
    }

    void setNext(Node<T> next) { setNext(Optional.ofNullable(next)); }

    void setNext(Optional<Node<T>> next ) { this.next = next; }
}

Unsafe Node

class NodeUnsafe<T> {
    private final T data;
    private NodeUnsafe<T> next;

    NodeUnsafe(T data) {
        this.data = data;
    }

    NodeUnsafe<T> getNext() {
        return next;
    }

    void setNext(NodeUnsafe<T> next) {
        this.next = next;
    }
}

Then I implemented two similar methods with the only difference - first uses Node<T> and the second uses NodeUsafe<T>

class DeleteMiddle {
    private static <T> T getLinkedList(int size, Function<Integer, T> supplier, BiConsumer<T, T> reducer) {
        T head = supplier.apply(1);
        IntStream.rangeClosed(2, size).mapToObj(supplier::apply).reduce(head,(a,b)->{
            reducer.accept(a,b);
            return b;
        });
        return head;
    }

    private static void deleteMiddle(Node<Integer> head){
        Optional<Node<Integer>> oneStep = Optional.of(head);
        Optional<Node<Integer>> doubleStep = oneStep;
        Optional<Node<Integer>> prevStep = Optional.empty();

        while (doubleStep.isPresent() && doubleStep.get().getNext().isPresent()){
            doubleStep = doubleStep.get().getNext().get().getNext();
            prevStep = oneStep;
            oneStep = oneStep.get().getNext();
        }

        final Optional<Node<Integer>> toDelete = oneStep;
        prevStep.ifPresent(s->s.setNext(toDelete.flatMap(Node::getNext)));
    }

    private static void deleteMiddleUnsafe(NodeUnsafe<Integer> head){
        NodeUnsafe<Integer> oneStep = head;
        NodeUnsafe<Integer> doubleStep = oneStep;
        NodeUnsafe<Integer> prevStep = null;

        while (doubleStep != null && doubleStep.getNext() != null){
            doubleStep = doubleStep.getNext().getNext();
            prevStep = oneStep;
            oneStep = oneStep.getNext();
        }
        if (prevStep != null) {
            prevStep.setNext(oneStep.getNext());
        }
    }

    public static void main(String[] args) {
        int size = 10000000;
        Node<Integer> head = getLinkedList(size, Node::new, Node::setNext);
        Long before = System.currentTimeMillis();
        deleteMiddle(head);
        System.out.println("Safe: " +(System.currentTimeMillis() - before));

        NodeUnsafe<Integer> headUnsafe = getLinkedList(size, NodeUnsafe::new, NodeUnsafe::setNext);
        before = System.currentTimeMillis();
        deleteMiddleUnsafe(headUnsafe);
        System.out.println("Unsafe: " +(System.currentTimeMillis() - before));
    }
}

Comparison of two several runs with different size of the list shows that approach with code that uses Optionalat the best is twice slower than one with nullables. With small lists it is 3 times slower.