Intro

Garbage collection (GC) was invented to reduce the burden of memory management - one you’d be (painfully?) familiar with if you ever programmed in a language requiring manual memory management like C++.

The premise was that you could let the runtime manage memory so the developer can spend more time on the core application concerns.

GC was in fact invented back in the 1950s for LISP, as such there has been decades of research on this topic. Modern GC algorithms like ZGC or C4 are very good, however, there can be niche situations where even these cannot offer an acceptable SLA.

Generally, GC-less programming techniques are mostly employed on the application hot-path, the latency-sensitive part of the code which gets called after program initialization.

We look at some example techniques below.

Reusable object

It goes without saying, if you want GC-less code, then you need to allocate less! But how do you achieve that if you are programming, for example, an event processing application where events are modeled as objects?

You can avoid generating new objects simply by reusing them for the lifecycle of your application. This is very straightforward for objects which have a static size:

public interface CancelRequest {
    public long getAccountID();
    public UUID orderToCancel();
}

The above interface implies that a CancelRequest will be made up of a long and a UUID - which are 8+16=24 bytes long. Once allocated, this request will always take up 24 bytes on the heap + object header overhead.

As the object is mutable, you can simply write into it from your input layer, process it and then use it again for the next time a request of the same type comes in.

Variable sized objects

Of course, it gets more tricky. Some objects are inherently a non-fixed size, usually because they contain collections.

With these, we want to pre-size to a target size as early as we can, and where we cannot, allow them to inflate to their steady-state size and never compress them back down.

Consider the following example. We allow clients to send a cancel request with a variable number of order IDs.

We can presize the ordersToCancel list to a maximum size, or, simply allow it to increase to the maximum during the lifetime of the application. The reset would simply “clear” the collection - but not resize it down (see for example java.util.ArrayList.clear())

public interface CanceAlllRequest {
    public long getAccountID();
    public List<UUID> ordersToCancel();
    void reset();
}

This fundamentally relies on the notion of the underlying data structure being wrapped - think about how an java.util.ArrayList wraps an array, but contains a variable called private int size because the size of the ArrayList is not the same as the size of the array which is backing it.

The underlying array can continue to grow until it reaches a steady state.

It’d be prudent to have validation stopping it from growing forever - e.g. in our example, we could have validation enforcing an upper bound number of orders which can be canceled in one request.

Collections of objects

The above example missed an important dimension - while we are reusing the same backing array in e.g. an ArrayList when we clear() it, the clear() function will null out any references stored in the array.

This would mean that objects being pointed to by the collection may then be garbage collected (assuming no other references to them exist), not desirable in a GC free app.

If we have a collection of mutable objects which we want to reuse, we have to write a custom collection class.

It would look something like:

public interface Clearable {
    void clear();
}

public class ReusableList<T extends Clearable> implements Clearable {
    // Only contains elements which are currently being used.
    private final List<T> usedElements = new ArrayList<T>();

    // Always contains all elements
    private final List<T> elementCache = new ArrayList<>();

    private final Supplier<T> objFactory;
    private final int numToPreallocate;

    public ReusableList(Supplier<T> objFactory) {
        this(objFactory, 10);
    }

    public ReusableList(Supplier<T> objFactory, int numToPreallocate) {
        this.objFactory = objFactory;
        this.numToPreallocate = numToPreallocate;
    }

    public T getNext() {
        preallocateItemsIfNeeded();
        return elementCache.get(usedElements.size());
    }

    public T get(int idx) {
        return usedElements.get(idx);
    }

    private void preallocateItemsIfNeeded() {
        if (usedElements.size() == elementCache.size()) {
            for (int i = 0; i < numToPreallocate; i++) {
                elementCache.add(objFactory.get());
            }
        }
    }

    @Override
    public void clear() {
        for (int i = 0; i < usedElements.size(); i++) {
            usedElements.get(i).clear();
        }
        usedElements.clear();
    }

    public int size() {
        return usedElements.size();
    }
}

You would only put mutable objects into this collection (hence they are Clearable). As you can see, calling clear() never causes references to be eligible for GC. Within the ReusableList, the references are always live in elementCache. We simply reuse the same memory in the future.

An example class which would work with this collection type (yes I have done away with many best practices like having getters / setters to give a more terse demonstration):

public class Person implements Clearable {
    public final StringBuilder firstName = new StringBuilder();
    public final StringBuilder lastName = new StringBuilder();
    public final ReusableList<Person> familyMembers = new ReusableList<>(Person::new);

    @Override
    public void clear() {
        firstName.setLength(0);
        lastName.setLength(0);
        familyMembers.clear();
    }
}

The ReusableList class is only for demonstration - there are many missing features for example:

• Bound on number of items
• Return / clear specific items rather than whole collection

Strings and other immutable objects

So how do we deal with Strings? Strings are immutable in many runtimes and certainly so in Java and are usually backed by a char[] or byte[].

The answer is to use a StringBuilder.

Both String and StringBuilder extend CharSequence, which is useful if we want to avoid exposing StringBuilder on an interface (e.g. because the client should only read)

Generally, the pattern would be to write into a StringBuilder whenever we deserialize an event entering our application. Once done with the event, we can reuse the StringBuilder - either clearing it just before event processing starts or right after.

Where a String represents something that should actually be a primitive (e.g. we are parsing a textual representation of a number), we can write an allocation free parser by processing each character individually and adding to an accumulator variable.

To illustrate this - the below is a function where we are parsing a number from a ByteBuffer which points at a CSV. We want to parse the text representation of a long and then stop when we reach the “,” denominator.

    private long parseLongFromCSV(ByteBuffer cb) {
        long ret = 0;
        char c;
        do {
            c = (char) cb.get();
            if (c == ',') {
                break;
            }
            int digit = charToDigit(c);
            ret *= 10;
            ret += digit;
        } while (cb.hasRemaining());

        return ret;
    }

Flyweights

Reusable objects are great and are especially useful when we are storing some state.

We may for example receive an Order which does not immediately fill - so we have to keep it around until it does.

However, some objects are inherently extremely short-lived - a prime example is an object representing an event that has just hit our application.

If you imagine an event as a sequence of bytes coming in via e.g. a network call, once we have processed those bytes we generally don’t need to access them again.

This type of data is very suited to being processed using a Flyweight. A great introduction to these is on the Mechanical Sympathy blog: Compact Off-Heap Structures/Tuples In Java

In short - we expose an interface as we would for any object, but the implementation does not contain any fields as such. It only contains a reference to e.g. a memory location or ByteBuffer, and put / get methods resolve the the exact memory location and read data.

Primitive autoboxing and collections

As you may be aware, primitive types cannot be used as type parameters for generic classes.

This is mostly because generics are only enforced at compile time - at runtime, the types are lost and is the equivalent of simply using Object everywhere.

For example, the following:

List<Person> list = new ArrayList<Person>();
list.add(new Person());
Person a = list.get(0);

gets converted at runtime to:

List list = new ArrayList();
list.add(new Person());
Person a = (Person) list.get(0);

The last line in particular is important - we had to cast (Person) list.get(0) because the get returns an Object. As a primitive is not an Object, is it not possible for us to use primitives in e.g. collections.

This is a problem as for example containers of numbers are common. The answer to this is for Java to use Autoboxing - e.g. an int gets autoboxed into a java.lang.Integer. However, this can introduce a lot of pressure on the garbage collector and we certainly don’t want these to be allocated on the hot path of a GC free application.

So instead we use primitive collections. There are 2 main implementations of these.

The first approach, somebody can template and then autogenerate specialisations of classes. An example of this is to have a template of List, and autogenerate an IntList, LongList, BooleanList etc… Linking to what we said earlier, the get(..) method return type would now be int, long, boolean etc depending on which class we are looking at rather than just Object.

A good example of this approach is e.g. Eclipse collections IntList

The second approach is to to write a completely specialised class for a given primitive type and thus try to expose any special performance tricks for a given type - for example back a BooleanList with a BitSet (and thus only take 1 bit per boolean) - an example is BooleanArrayList

Some great collections to look at are:

• Eclipse Collections. Formerly maintained by Goldman Sachs, very comprehensive library
• Agrona Collections. Worked on by the extremely strong team at real-logic, generally very optimised but you have to know what you’re doing and be aware of subtleties! Read the docs before using.
• fastUtil - I haven’t used this much but have heard good things about it
• trove4j - very popular primitive collections library, now deprecated.

Autoboxing cache in the JVM

It is worth noting that in the JVM we have a cache for autoboxing. This means that in some cases it is possible to use standard JDK collections without constant object allocation even when autoboxing.

The implementation of the JVM is free to cache autoboxed objects (and infact in many JVMs this is a parameter you can tune), however, as per the Java Language Spec, you can rely the cache having some int numbers, both booleans and most characters:

If the value p being boxed is an integer literal of type int between -128 and 127 inclusive (§3.10.1), or the boolean literal true or false (§3.10.3), or a character literal between ‘\u0000’ and ‘\u007f’ inclusive (§3.10.4), then let a and b be the results of any two boxing conversions of p. It is always the case that a == b.

You can also have a look at the implementation in the JDK - see java.lang.Integer.IntegerCache