Interesting Links – 2017/Apr/26

Yes, it’s been a while, I’ve been busy and I’m the only curator of this content:

… and just because I have a weird sense of humor:

randomUser> This code would run really well if it didn't keep waiting for the PRNG to determine the sign of a random number.

LinkedList vs. ArrayList

Recently, The Java Programmer published “Difference between ArrayList and LinkedList in Java“, asserting different cases of when to prefer one List implementation over another. It’s a link full of conventional wisdom, and while it has some good information, it’s also wrong.
Here’s the channel’s factoid on LinkedList, as of 2017/Apr/25 (prior to it having been changed to point to the page you’re reading):

LinkedList is almost always slower than ArrayList/ArrayDeque. It might be best to use ArrayList/ArrayDeque to start. But if you have an actual performance problem, you can compare the two for your specific case. Otherwise, just use ArrayDeque. (It too has O(1) performance for insert-at-beginning, and unlike LinkedList is actually fast).

Implementation

The “Difference” page says that ArrayList uses an internal array to represent stored objects, while a LinkedList uses a doubly-linked list internally. In this, it’s correct.

Searching

The next point of comparison is entitled “Searching.” Here’s what it says about ArrayList:

An elements can be retrieved or accessed in O(1) time. ArrayList is faster because it uses array data structure and hence index based system is used to access elements.

And about LinkedList:

An element can be accessed in O(N) time. LinkedList is slower because it uses doubly linked list and for accessing an element it iterates from start or end (whichever is closer).

First off, in the interest of honesty, the last bit of information – that it iterates from either forward or backward, depending on which is closer – was a surprise to me (although it’s perfectly logical.) It’s also accurate.
However, this isn’t searching – it’s element access. Access and searching are different things; it’s get(42) vs. list.contains(matchingObject). This is important; contains() will have O(N) time for either List implementation, whereas ArrayList will have O(1) for get(), and LinkedList will have O(N) for get().
The thing is: LinkedList is not only O(N) for get() but the nature of the internal implementation makes it slower than one might think, because of cache locality. In an ArrayList, the element references are stored sequentially in memory; a LinkedList potentially splatters the references all over the heap. (This is not entirely likely, but it’s possible.) Thus, a LinkedList not only has O(N) performance for indexed access (where the ArrayList has O(1)), but the O(N) is worse than one might expect.
For accessing elements, there’s no situation apart from accessing the first or last element where a LinkedList competes with an ArrayList‘s speed.

Note that programming hates absolutes. It’s fully possible to create situations in which that last claim is not entirely true… but they’re rare and unlikely.

Insertion

About ArrayList:

Normally the insertion time is O(1). But in case array is full then array is resized by copying elements to new array, which makes insertion time O(N).

And about LinkedList:

Insertion of an element in LinkedList is faster, it takes O(1) time.

Incomplete data is provided here. For one thing, the author conflates mutation with “insertion.” There are two different kinds of additive list mutations (where data is added to a List): insertion (meaning that elements are prepended to other elements) and addition (where an element “follows” the last element in the list prior to mutation.)
Where the elements go as part of the additive mutation is really important, and it’s also important to note that the claim of LinkedList‘s O(1) time is very much a single type of insertion.
For an ArrayList, a list append (i.e., calling add(), which adds the provided element at the end of the list) has O(N) performance, but typically has O(1) performance. The O(N) complexity is because the internal array size might be exceeded by the addition of the element, in which case a new internal array is allocated, and the array references are copied over to the new internal array, and then the new element is appended. Thus, in the worst case, it is O(N), but this is misleading because:

  1. It’s fairly rare (the list resizes with a formula of currentSize*1.5 (the actual line is int newCapacity = oldCapacity + (oldCapacity >> 1);, if you’re interested.)
  2. Java’s blits are very, very, very fast; Java uses the blit mechanism constantly, and let’s be real, modern CPUs are really good at this anyway.

So is it actually O(N), then? … given what conventional Big O notation means, yes, it is; it’s just that O(N) is a lot less expensive than one might think in this case. And typically, the add() will be O(1) in actuality.
But what about LinkedList?
Insertion at the beginning or the end of the list is, in fact, O(1). This is even the common case (add(Object) calls linkLast(Object) by default.) However, if positional notation is used at all (i.e., add(int, Object) you degrade to O(N), because the LinkedList has to find the position at which the new element has to be inserted – and finding that position is O(N).
So what’s the conclusion? ArrayList does in fact have O(N) performance for adds, but it’s close enough to O(1) in real world conditions that we can colloquially speak of it being likely as fast as LinkedList‘s similar case… and if we add any kind of positional insertion, ArrayList‘s degradation under the worst case is far better than LinkedList‘s degradation.
As usual, we can create situations under which this is not the case (for example, if we always insert after the first position in a LinkedList, which will “search” one element and only that element) but these are fairly rare.

Deletion

Let’s see about ArrayList:

Deletion of an element is slower as all the elements have to be shifted to fill the space created by deleted element.

And LinkedList:

Deletion of an element is faster in LinkedList because no elements shifting are required.

Well, um, no.
Here, the author is confusing complexity – big O notation – with speed, for ArrayList. (He or she is wrong about LinkedList in any event.)
For an ArrayList, deleting an element by index is indeed O(N) because the JVM does have to blit the elements after the removed element (it has to shift them all in the internal array.)
However, for a LinkedList, it also has to find the elements around the element to remove – and if you recall, accessing a specific element for a LinkedList is an O(N) complexity itself. Even though the removal is simple (it’s simply relinking the nodes before and after the removed element), actually finding those nodes is O(N), thus deletion is O(N) for LinkedList – and slower than ArrayList, to boot.

Memory and Initial Capacity

The author says that an ArrayList has a default internal capacity of 10. This is incorrect for Java 8. See this code.
For the rest of it, the author is correct; a LinkedList is “empty” (there are no linked nodes internally); an ArrayList has capacity references in the internal list, while a LinkedList has a chain of objects, which will have higher memory consumption, but that’s not likely to matter unless your lists are huge.

The Comparison’s Conclusion

  • As search or get operation is faster in ArrayList so it is used in the scenario where more search or get operations are required.
  • As insertion or deletion of an element is faster in LinkedList so it is used in the scenario where more insertion and deletion operations are required.

The thing that the conclusion is missing is that “insertion and deletion” operations in LinkedList typically involve searches and gets – which are terrible for LinkedList – and therefore for even the operations that LinkedList is potentially better, ArrayList will typically perform better.
The factoid stands. If you need a List, use ArrayList first, then ArrayDeque if your access patterns demand… use LinkedList only after exhausting other possibilities.

Immutability in Java

Recently in ##java, we had a discussion on what constitutes “immutability” and how to implement it in java properly. Immutability is a core concept for functional programming, and as mainstream languages and ecosystems “catch up” with the safer, less error-prone ideas from functional programming, immutability is wanted in Java projects as well.

What is immutability?

Asking programmers for their definition of immutability, you will usually receive an answer such as this:

An object is immutable if its state never changes.

In this article we will look at different interpretations of that statement and see how to implement it in java.

Unmodifiable vs. Immutable

An unmodifiable object is an object that cannot be mutated. This does not mean it cannot change through other means:

List<String> inner = new ArrayList<>();
inner.add("foo");
List<String> unmodifiable = Collections.unmodifiableList(inner);
System.out.println(unmodifiable); // [foo]
inner.add("bar");
System.out.println(unmodifiable); // [foo, bar]

Unmodifiable objects are generally not considered “truly” immutable. An immutable version of the code above (using Guava‘s ImmutableList) would be:

List<String> inner = new ArrayList<>();
inner.add("foo");
List<String> immutable = ImmutableList.copyOf(inner);
System.out.println(immutable); // [foo]
inner.add("bar");
System.out.println(immutable); // [foo]

Polymorphism

Designing an immutable class to be extended is tricky business. The base class must either relax its immutability or make basically all of its methods final which makes polymorphism basically useless. Relaxing immutability guarantees will often lead to only an unmodifiable class:

public class Vec2 {
    private final int x;
    private final int y;
    public Vec2(int x, int y) {
        this.x = x;
        this.y = y;
    }
    public int getX() { return x; }
    public int getY() { return y; }
    @Override public int hashCode() { return getX() * 31 + getY(); }
    @Override public boolean equals(Object o) { ... }
}

This class appears immutable at first glance, but is it really?

public class MutableVec2 extends Vec2 {
    // redundant fields because super fields are private and final
    private int x;
    private int y;
    public MutableVec2(int x, int y) {
        super(x, y);
        this.x = x;
        this.y = y;
    }
    @Override public int getX() { return x; }
    @Override public int getY() { return y; }
    public void setX(int x) { this.x = x; }
    public void setY(int y) { this.y = y; }
}

We’ve suddenly introduced mutability, and not just that, we also override the two getters, so users of the original “immutable” Vec2 class cannot rely on instances of Vec2 never changing state when using them. This makes Vec2 effectively unmodifiable only, not immutable. Immutable classes should be final.
Limited polymorphism is possible when necessary, for example through a package-private constructor so immutability can be strictly controlled. This is error-prone and should be reserved for exceptional cases.

Defensive copies

Immutability itself does not require immutability on class members (in most definitions). However, in many cases where immutability is used, making sure that members also stay unmodified is desired. This can be done through “defensive copies”:

public class ImmutableClass {
    private final List<String> list;
    public ImmutableClass(List<String> list) {
        this.list = Collections.unmodifiableList(new ArrayList<>(list));
        // when using guava:
        //this.list = ImmutableList.copyOf(list);
    }
    // getter, equals, hashCode
}

Internal state

Internal mutable state is allowed in immutable classes. One use case of this is caching. In OpenJDKs java.lang.String class, which is immutable, the hashCode is cached using this method:

public class String {
    ...
    private int hash; // defaults to 0. not explicitly initialized to avoid race condition (see section below)
    @Override
    public int hashCode() {
        int h = hash;
        if (h == 0) {
            hash = h = computeHashCode();
        }
        return h;
    }
}

(This isn’t the actual implementation but it’s the same principle. Want to see this as implemented in an actual Java runtime library? Here it is.)
To users of this class, the internal state is never visible – they do not see a change in behavior. Because of this, the class still counts as immutable.

Concurrency

Java concurrency is a fickle beast, and immutability is an important tool to avoid the shared mutable state that makes concurrency so difficult. However, immutability has to be implemented carefully to work reliably in concurrent applications.
On top of the basic “state never changes” requirement we must introduce two more requirements: (from Java Concurrency In Practice. Read it, it’s a great book.)

  • All fields must be final.
  • The this reference must never escape the constructor. This is called “proper construction”.

To explore why these requirements are necessary, we will take an example straight from the Java Language Specification:

final class MaybeImmutable {
    private int x;
    public MaybeImmutable(int x) {
        this.x = x;
    }
    public int getX() { return x; }
    // the two threads
    static MaybeImmutable sharedField; // this field isn't volatile
    static void thread1() {
        sharedField = new MaybeImmutable(5);
    }
    static void thread2() {
        MaybeImmutable tmp = sharedField;
        if (tmp != null) {
            System.out.println(tmp.getX()); // could be 5... but could also be 0!
        }
    }
}

At first glance the MaybeImmutable class appears immutable – it does not provide any API to modify its state. The problem with this class is that the field x is not final. Let’s take a look at what both threads do:

// thread1
tmp = allocate MaybeImmutable
tmp.x = 5
write sharedField = tmp
// thread2
read tmp = sharedField
check tmp != null
print tmp.x

In this case, the constructor call is “just” setting the field. If you’re already familiar with the java memory model, you will notice that there is no happens-before ordering between those two threads! This makes the following execution order legal:

// thread1
tmp = allocate MaybeImmutable
write sharedField = tmp
tmp.x = 5
// thread2
// same as above

In that case, thread2 could legally print out “0”.
(Reordering is only one reason why this could happen – caches are another, for example.)
This fact makes our MaybeImmutable class not immutable: From thread2, the state of the same exact instance of MaybeImmutable can change over time. How can we fix this? By making the field x final. Looking at the JLS, this guarantees that when we can see the MyImmutable instance in the sharedField, we can also see the correctly initialized x field. thread2 will always print out 5, as we’d expect.
This visibility guarantee is only given if our class does not leak its this reference before construction is complete, which brings us to our second requirement (“proper construction”):

final class NotImmutable {
    public static NotImmutable instance;
    private final int x;
    public NotImmutable(int x) {
        this.x = x;
        instance = this;
    }
    public int getX() { return x; }
    static void thread1() {
        new NotImmutable(5);
    }
    static void thread2() {
        NotImmutable tmp = instance;
        if (tmp != null) {
            System.out.println(tmp.getX()); // could still be 0!
        }
    }
}

Even though the x field is final in this case, thread2 can see an instance of NotImmutable before its constructor completes, meaning it can still see 0 as the value of x.
Interestingly, setting the x field to volatile in doesn’t help in either example (NotImmutable or MaybeImmutable). The guarantees of final fields are actually different than those of volatile fields here. This is covered in Aleksey ShipilĂ«v’s article “Close Encounters of The Java Memory Model Kind.” This article, together with “Java Memory Model Pragmatics,” is a great resource to learn more about the Java memory model.

Builders

Immutable classes, especially those with many fields, can be difficult to construct – the Java language lacks named parameters. This can be made somewhat easier through the builder pattern, which the following example demonstrates (though only with a single field):

public class ImmutableClass {
    private final String url;
    private ImmutableClass(String url) {
        this.url = url;
    }
    public String getX() {
        return url;
    }
    public static class Builder {
        private String url;
        public Builder url(String url) {
            this.url = url;
            return this;
        }
        public ImmutableClass build() {
            return new ImmutableClass(url);
        }
    }
}
ImmutableClass myInstance = new ImmutableClass.Builder().url("https://yawk.at/").build();

This pattern provides an easy way of constructing very large immutable classes – builders are infinitely more readable than constructor calls such as new ImmutableClass("GET", 6, true, true, false, 5, null). Most IDEs also include utilities to quickly generate such builders.

Lombok

The wonderful project lombok provides a very easy way of writing immutable classes in a few lines of code via the @Value annotation:

@Value
public class ImmutableClass {
    private final String url;
}

This makes the fields private final (if they aren’t already), generates getters and a constructor, and makes the class final. As an added bonus it also generates an equals and hashCode for you. On top of that, you can use the @Builder annotation to also let it generate a builder for you, and the experimental @Wither annotation to generate copy mutators.
To see what kind of code Lombok can generate you can either view the examples on their website or use my javap pastebin to see decompiled lombok-generated code (make sure to select “Procyon” on the bottom-right).

Serialization

Immutable classes do not follow the traditional Java bean layout: They do not have a zero-argument constructor and they do not have setters. This makes serialization using reflection difficult. There are solutions, though – an immutable class constructor can be annotated with serialization-framework-specific annotations to give the framework information on which parameter corresponds to which object property.
We will look at the jackson-databind annotations first:

public final class Vec2 {
    private final int x;
    private final int y;
    @JsonCreator
    public Vec2(@JsonProperty("x") int x, @JsonProperty("y") int y) {
        this.x = x;
        this.y = y;
    }
    public int getX() { return x; }
    public int getY() { return y; }
}

A more framework-agnostic solution exists using the java.beans.ConstructorProperties annotation (not present in android) which is supported by Jackson since version 2.7.0:

public final class Vec2 {
    private final int x;
    private final int y;
    @ConstructorProperties({ "x", "y" })
    public Vec2(int x, int y) {
        this.x = x;
        this.y = y;
    }
    public int getX() { return x; }
    public int getY() { return y; }
}

This annotation is also generated on Lombok constructors by default making serializing Lombok-generated immutable classes hassle-free with jackson 2.7+.
Gson takes another approach to deserialization of objects without a zero-argument constructor: sun.misc.Unsafe provides a method to allocate an instance of a class without calling its constructor. Gson then proceeds to reflectively set fields of the immutable object. However, Unsafe is unsupported API and the OpenJDK project is attempting to phase out the class and may remove it entirely in a future JDK version, so this solution should be avoided.
Immutability in Java is not as simple in Java as it might appear at first but with the right tools and patterns, it can be very beneficial to your code base, making your application easier to read, debug and extend and making parallelism much simpler. Be careful of accidentally adding mutability and make use of tools like Lombok to reduce boilerplate associated with immutable classes in Java.