Hello. The idea to create a collection that allows you to manage an array of information, which is based on the matrix, was born a long time ago. I decided to bring the idea to life after studying the Java programming language. The article focuses on collections that implement the list interface .

Java collections

At the moment we have at our disposal more than enough of both native JDKs and third-party libraries for working with collections:

JDK

• java.util.ArrayList
• java.util.LinkedList

Open source

• Commons Collections
• Commons primitives
• GS Collections
• Guava
• HPPC
• PCJ
• Trove

Base selection

The use of generics principles is suitable for creating a universal collection. The basis of the collection is created by the java.util.AbstractList class. The get and size methods are required to override.

public class FastArray<E> extends AbstractList<E> { @Override public E get(int index) { return null; } @Override public int size() { return 0; } } 

In addition, the body of some methods of the abstract class AbstractList is defined as throw new UnsupportedOperationException() , which causes us to also redefine them to the behavior we need:

  public E set(int index, E element) { throw new UnsupportedOperationException(); } public void add(int index, E element) { throw new UnsupportedOperationException(); } public E remove(int index) { throw new UnsupportedOperationException(); } 

The principle of storing and working with data

The structure of data storage in the collection is presented in the form of one matrix and one array with the type IndexData:

  private Object[][] elementData; private IndexData[] data; 

A two-dimensional array elementData is used to store the list items. A two-dimensional array to the detriment of memory allows you to provide quick access to the list items in the process of reading, writing and deleting quick insert / delete operations in the beginning / middle of the list.

Unlike the standard ArrayList behavior (when adding elements, the contents of the array are copied to the new enlarged array), in FastArray the first dimension of the array has a variable length and changes if necessary, the second dimension of the array has a constant length of 32 elements.

  private static final int CAPACITY = Integer.SIZE; 

That is, it all comes down to the fact that if there is a shortage of storage for elementData, it will be executed:

1. dynamic allocation of memory to the new size of the first dimension of the array
2. copied links to all arrays of the second dimension
3. dynamically created a new array of the second dimension

The IndexData array is required for storing the occupied places and their total number in the second dimension of elementData:

  private static class IndexData { private int data; private int size; private boolean isFull() { return size == CAPACITY; } private void take(final int index) { if (isFree(index)) { data = data | 1 << index; size++; } } private void free(final int index) { if (isTaked(index)) { data = data ^ 1 << index; size--; } } private boolean isTaked(final int index) { return !isFree(index); } private boolean isFree(final int index) { return (data & 1 << index) == 0; } private int getSize() { return size; } private int getIndexLeadingFreeBit() { return CAPACITY - Integer.numberOfLeadingZeros(data); } private int getIndexTrailingFreeBit() { return Integer.numberOfTrailingZeros(data) - 1; } } 

32 places are stored in bits of one 32-bit number. This technique allows you to reduce some cycles when traversing arrays. For example, search for free space on the left or right in the second dimension.

  private int getTakedIndexAt(int data, int number) { int count = 0; int index = -1; number++; do { count += data & 1; index++; } while ((data >>>= 1) != 0 && count != number); return index; } 

This algorithm should find, for example, the fifth place from the beginning. If you have ideas on how to remove the loop from this algorithm, then please indicate them in the comments.

Tests

The FastArray collection begins to show positive results after it exceeds its size of 1000 items. Otherwise, the time to perform operations is significantly increased compared with the results of other collections.

  int count = 100000; for(int i = 0; i < count; i++) list.add(1); for(int i = 0; i < count; i++) list.add(rand.nextInt(count), 10); for(int i = 0; i < count * 2; i++) list.get(rand.nextInt(count)); for(int i = 0; i < count; i++) list.remove(rand.nextInt(list.size())); 

Results of testing collections

UPD: JMH benchmark

The source code of the tests is presented on github.

Conclusion

Once again I want to note that we reduce the amount of memory consumed by reducing the execution time. When performing the above tests in the defragmentation process, the size of the FastArray collection increased 3 times from the nominal. To reduce the size of the collection, use the trimToSize() method.
This version of the implementation is not final. Here is implemented the minimum required functionality, which later can be more carefully optimized.

The source code is fully presented on github.

Thank you for attention