The best data structure to use is a native array due to its better cache locality. The key challenge is to allow it to grow without generating garbage. This can be achieved by storing the previous array in a SoftReference:
int newSize = int (growthFactor * this.array.length); E[] oldArray = this.array; this.array = (E[]) new Object[newSize]; // copy from oldArray to this.array (if necessary) // nullify any object left on oldArray (if necessary) oldArrays.add(new SoftReference<E[]>(oldArray)); You can try implementing this approach yourself as an exercise, or you can use CoralPool, which is an open-source garbage-free solution optimized for performance. For a deeper dive into writing garbage-free Java code, check out this video.
On a side note, using java.util.LinkedList is not ideal because, like many other Java collections, it generates a significant amount of garbage. This creates a contradiction: you’re trying to minimize garbage using an object pool, but the pool itself contributes to garbage creation. Clearly, that's not an efficient approach. Run the code below to observe how much garbage it generates:
final LinkedList<Object> list = new LinkedList<>(); final Object object = new Object(); final Random random = new Random(); long start = System.currentTimeMillis(); for(int i = 0; i < 50_000; i++) { int toAdd = random.nextInt(1_000) + 1; int toRemove = random.nextInt(1_000) + 1; for(int x = 0; x < toAdd; x++) list.add(object); for(int x = 0; x < toRemove; x++) if (!list.isEmpty()) list.removeLast(); } long time = System.currentTimeMillis() - start; System.out.println("List size: " + list.size() + " after " + time + " millis");
$ java -verbose:gc -cp . TestLinkedList [0.003s][info][gc] Using G1 [0.034s][info][gc] GC(0) Pause Young (Normal) (G1 Evacuation Pause) 25M->1M(388M) 0.796ms [0.043s][info][gc] GC(1) Pause Young (Normal) (G1 Evacuation Pause) 29M->1M(388M) 1.587ms [0.060s][info][gc] GC(2) Pause Young (Normal) (G1 Evacuation Pause) 61M->2M(388M) 2.989ms [0.082s][info][gc] GC(3) Pause Young (Normal) (G1 Evacuation Pause) 78M->3M(388M) 4.149ms [0.107s][info][gc] GC(4) Pause Young (Normal) (G1 Evacuation Pause) 111M->1M(820M) 1.293ms [0.149s][info][gc] GC(5) Pause Young (Normal) (G1 Evacuation Pause) 137M->2M(820M) 2.541ms List size: 38609 after 166 millis
Regarding this comment:
Having softly-refed objects doesn't delay a GC; it means that objects which are softly-refed might not be collected if the GC was able to free enough non-refed and weakly-refed objects. The typical use case is for caching the result of an expensive computation - by making the cache a soft-ref, you're telling the JVM that it is okay to throw out the cache (during a GC), if doing so allows you to avoid an OOM error. In your pool you are making the E-arrays garbage when you resize the array. This is a weird approach for a pool which wants "grow without generating garbage"
Below is a Java code that proves that GC is delayed by using a SoftReference, in other words, GC will only happen if your application comes to a point that it is about to crash with an OutOfMemoryError. That's exactly the feature we want for our pool.
import java.lang.ref.SoftReference; import java.util.List; import java.util.ArrayList; public class SoftReferenceTest { static volatile boolean keepAllocating = true; public static class MyObject { private final int index; public final byte[] data = new byte[1024 * 1024]; public MyObject(int index) { this.index = index; } @Override public void finalize() { System.out.println("\nGarbage collected => " + index + " thread=" + Thread.currentThread()); // If EVEN then you are a SoftReference being collected if (index % 2 == 0) keepAllocating = false; // STOP LOOP DOWN BELOW } } public static void main(String[] args) throws InterruptedException { List<SoftReference<MyObject>> oldObjects = new ArrayList<>(); for(int i = 0; i < 4; i++) { MyObject myObject = new MyObject(i); if (i % 2 == 0) { // only add EVEN objects as SoftReferences oldObjects.add(new SoftReference<MyObject>(myObject)); } // ODD objects will go out-of-scope and be collected by the gc } // Force the GC and notice that the even objects are NOT collected System.out.println("Forcing the GC..."); System.gc(); Thread.sleep(100); // Now start allocating memory like crazy to force the // SoftReference to be collected List<byte[]> list = new ArrayList<>(1024); int counter = 0; int totalMemory = 0; int memoryToAllocate = 1024 * 128; System.out.println(); while(keepAllocating) { list.add(new byte[memoryToAllocate]); System.out.print("\r"); System.out.print(counter++); totalMemory += memoryToAllocate; System.out.print(" "); System.out.print(totalMemory); Thread.sleep(10); } } } Output:
$ java -Xms64m -Xmx64m -cp . SoftReferenceTest Forcing the GC... Garbage collected => 3 thread=Thread[#10,Finalizer,8,system] Garbage collected => 1 thread=Thread[#10,Finalizer,8,system] 384 50462720 <== App is running but SoftReference is not collected Garbage collected => 2 thread=Thread[#10,Finalizer,8,system] Garbage collected => 0 thread=Thread[#10,Finalizer,8,system] Note that we have successfully avoided the GC until the very end when the JVM was about to run out of memory.
384 50462720 => 50Mb when our max heap size was 64Mb Now run the test again, but this time with a larger max heap size:
$ java -Xms128m -Xmx128m -cp . SoftReferenceTest Forcing the GC... Garbage collected => 1 thread=Thread[#10,Finalizer,8,system] Garbage collected => 3 thread=Thread[#10,Finalizer,8,system] 847 111149056 <== App is running but SoftReference is not collected Garbage collected => 0 thread=Thread[#10,Finalizer,8,system] Garbage collected => 2 thread=Thread[#10,Finalizer,8,system] This time, because the JVM had more memory, it waited to collect the SoftReference until 111Mb of memory were allocated instead of only 50Mb.
847 111149056 => 111Mb when our max heap size was 128Mb That proves that a SoftReference is delayed until the JVM is about to run out of memory.
Note that if your application comes to a point that it is running out of memory and it is about to crash, of course it is much better to GC and try to avoid the OOM crash. That's exactly the purpose of the SoftReference and that's why we choose to use it for the pool.
Disclaimer: I'm one of the developers of the open-source project CoralPool.