High performance primitive dynamic array

Question

Unfortunately Java does not support generic programming with primitive types. Using collections classes with boxed types may increase memory usage by a factor of 3-4 (e.g. int being 32-bit and Integer 128-bit). Throughput may be lower, with some tests demonstrating boxed types being at least 10 times slower. This seems consistent with my own measurements. I have not found any official (Oracle) or otherwise reputable implementations of primitive arrays, so here I go.

The goal is to write a fast and simple linear container for primitives. It is intended to be as similar as possible to ArrayList. It will at least implement the common array operations size(), add(int value), add(int index, int value), set(int index, int value), get(int index), remove(), remove(int index) and clear(). A few operations, like contains(Object obj) and indexOf(Object obj) will be left out, because they rely on reference types, not value types.

I'm interested in performance optimizations. Hopefully someone better knows how this code can be optimized further. Below is the implementation of int-vector, iVector. The name is only a preliminary placeholder, and vectors for other primitives can be created by changing the classname and the int-types in the implementation.

public class iVector {
    private int[] data;
    private int length = 0;

    //Constructors
    public iVector(){
        data = new int[10];
    }
    public iVector(int initialCapacity){
        if(initialCapacity < 10)
            initialCapacity = 10;
        data = new int[initialCapacity];
    }


    //Methods
    public int size(){
        return length;
    }

    public void ensureCapacity(final int capacity){
        if(capacity <= data.length) return;
        int[] newData = new int[capacity];
        System.arraycopy(data, 0, newData, 0, data.length);
        data = newData;
    }

    public void add(final int value){
        if(length == data.length)
            ensureCapacity(data.length + data.length/2); // Grow by approx. 1.5x
        data[length] = value;
        ++length;
    }

    public void add(final int index, final int value){
        if (index >= length || index < 0)
            throw new ArrayIndexOutOfBoundsException(index);
        if (length == data.length)
            ensureCapacity(data.length + data.length / 2); // Grow by approx. 1.5x
        for (int i = length; i > index; --i)
            data[i] = data[i - 1];
        data[index] = value;
        ++length;
    }

    public void set(final int index, final int value){
        if(index >= length)
            throw new ArrayIndexOutOfBoundsException(index);
        data[index] = value; //if (index<0) or (index>data.length), IndexOutOf. is thrown
    }

    public int get(final int index){
        if(index >= length)
            throw new ArrayIndexOutOfBoundsException(index);
        return data[index]; //if (index<0) or (index > data.length), IndexOutOf. is thrown
    }

    public void remove(){ // Remove last element
        if(length == 0) return;
        --length;
    }

    public int remove(int index){ // Removes and returns the removed value
        final int result = get(index);
        --length;
        for(; index < length; ++index)
            data[index] = data[index + 1];
        return result;
    }

    public void clear(){ // Make empty
        length = 0;
    }
}

Answer 1

• There is a small bug: In the method add(int, int), it should probably be

  if (index > length || index < 0)
      throw new ArrayIndexOutOfBoundsException(index);
  

  instead of

  if (index >= length || index < 0)
      throw new ArrayIndexOutOfBoundsException(index);
  

  Inserting at the index length would just mean appending an element to the end of the iVector, so an index of length wouldn't be invalid.

• Also, data.length + data.length/2 might overflow for very large values of length. You could prepare for this by checking whether Integer.MAX_VALUE - data.length/2 >= data.length.

• In the method ensureCapacity(int), it would suffice to copy length elements instead of data.length elements, since the values of all elements in data with an index equal to or greater than length are irrelevant.

• You could simply call add(length, value) from add(int value), because right now, the code of add(int) is effectively duplicated in add(int, int). If the reason for this is performance due to the unnecessity of argument validation, this would probably only be relevant for a very large number of successive additions, and for this, you could make a separate bulk method like addAll (which could also employ other optimizations like calling System.arraycopy instead of manually copying each element via iteration).

• public void remove(){
      if(length == 0) return;
      --length;
  }
  

  Can be written more concisely as:

  public void remove(){
      if(length != 0) --length;
  }
  

• remove() returns void whereas remove(int index) returns the value previously at index. This is inconsistent. I suggest you make remove() also return the previously last element.

• It occurred to me that, if the internal array can contain "vacant lots" at the end, it could also contain vacant lots at the beginning. For example, consider this array with a capacity of 10, containing 6 elements:

  abcfgh----
  

  Now, if you want to delete a from the array, your code would do this:

  bcfgh-----
  

  I.e. delete the first element and shift all subsequent elements to the left by one position. But it would be much more efficient to do this:

  -bcfgh----
  

  This would also require a pointer to the first element in addition to a field that stores the number of elements in the iVector. And if you want to insert or delete an element, you could calculate for each direction how many elements would have to be shifted, and then perform the cheaper of the two variants and update the respective pointer accordingly. For example, if you now want to insert e between c and f, a "left-push" would require two elements to be moved (bc), whereas a "right-push" would require three elements to be moved (fgh), so the left-push variant would be cheaper:

  bcefgh----
  

  In fact, the array could even wrap around. If you now want to insert d before e, you could do this:

  cdefgh---b
  

  While this would make simple get or set operations a tiny bit more expensive, because you would have to calculate the index for the internal array from the public index for the iVector, I guess that this can save quite a bit of performance for add or remove operations on the lower half of the iVector.

Update

So I've tried to implement the wraparound suggestion myself, and the code now seems to be about twice as fast as your version when removing and inserting from/to random positions in the vector. When only operating on the upper half, it is, of course, a little bit slower, because the overhead is never compensated for by shifting fewer elements than your original code. Here is my implementation:

public class IntArrayList {
    private int[] data;
    private int size;
    private int indexOfFirstElement;

    public IntArrayList() {
        this(10);
    }

    public IntArrayList(int initialCapacity) {
        data = new int[Math.max(initialCapacity, 10)];
        size = 0;
        indexOfFirstElement = 0;
    }

    public int size() {
        return size;
    }

    /**
     * Returns the index of the element in the internal array that is
     * {@code offset} positions away from the element at the index
     * {@code index}, wrapping around the array if necessary.
     * {@code offset} can be negative, in which case the distance will be
     * traveled to the left of the original element rather than to the right.
     * This method assumes that the passed index is valid and that the
     * absolute value of {@code offset} is not greater
     * than the length of the internal array. If these conditions are not
     * met, the returned index might not be valid.
     *
     * @param index  a valid index for the internal array
     * @param offset the distance from the element at index {@code index}; may be negative
     * @return the index of the array element at the specified distance
     */
    private int indexForOffset(int index, int offset) {
        int offsetIndex = index + offset; //might overflow
        if (data.length - index <= offset) { //includes cases where the previous line overflows
            offsetIndex -= data.length;
        } else if (offsetIndex < 0) { //cannot be the result of an overflow
            offsetIndex += data.length;
        }
        return offsetIndex;
    }

    public void ensureCapacity(final int capacity) {
        if (capacity > data.length) {
            int[] newData = new int[capacity];
            if (size != 0) {
                if (indexOfFirstElement <= indexForOffset(indexOfFirstElement, size - 1)) {
                    System.arraycopy(data, indexOfFirstElement, newData, 0, size);
                } else {
                    System.arraycopy(data, indexOfFirstElement, newData, 0, data.length - indexOfFirstElement);
                    System.arraycopy(data, 0, newData, data.length - indexOfFirstElement, indexOfFirstElement + size - data.length);
                }
            }
            data = newData;
            indexOfFirstElement = 0;
        }
    }

    /**
     * Converts an index for this {@code IntArrayList} to the
     * corresponding index for the internal array. This method
     * assumes that the passed index is valid. If it is not,
     * the returned index might not be valid as well.
     *
     * @param publicIndex A valid index for this {@code IntArrayList}
     * @return the index pointing to the corresponding element in the internal array
     */
    private int internalArrayIndex(int publicIndex) {
        int internalArrayIndex = publicIndex + indexOfFirstElement;
        if (internalArrayIndex < 0 || internalArrayIndex >= data.length) {
            internalArrayIndex -= data.length;
        }
        return internalArrayIndex;
    }

    public void add(final int value) {
        add(size, value);
    }

    public void add(final int index, final int value) {
        if (index > size || index < 0) {
            throw new IndexOutOfBoundsException(index);
        }

        if (size == data.length) {
            if (data.length == Integer.MAX_VALUE) {
                throw new OutOfMemoryError();
            } else {
                int newCapacity = data.length + data.length / 2; // Grow by approx. 1.5x
                if (newCapacity < 0) { //overflow
                    newCapacity = Integer.MAX_VALUE;
                }
                ensureCapacity(newCapacity);
            }
        }

        int internalInsertionIndex = internalArrayIndex(index);
        if (index >= (size + 1) >>> 1) { //right-push
            moveRangeWrapping(data, internalInsertionIndex, 1, size - index);
        } else { //left-push
            internalInsertionIndex = indexForOffset(internalInsertionIndex, -1);
            moveRangeWrapping(data, indexOfFirstElement, -1, index);
            indexOfFirstElement = indexForOffset(indexOfFirstElement, -1);
        }
        data[internalInsertionIndex] = value;
        size++;
    }

    public void set(final int index, final int value) {
        if (index >= size || index < 0) {
            throw new IndexOutOfBoundsException(index);
        }
        data[internalArrayIndex(index)] = value;
    }

    public int get(final int index) {
        if (index >= size || index < 0) {
            throw new IndexOutOfBoundsException(index);
        }
        return data[internalArrayIndex(index)];
    }

    public int remove() {
        return remove(size - 1);
    }

    public int remove(int index) {
        final int result = get(index);

        int internalDeletionIndex = internalArrayIndex(index);

        if (index >= size / 2) { //right-side-pull
            moveRangeWrapping(data, indexForOffset(internalDeletionIndex, 1), -1, size - index - 1);
        } else { //left-side-pull
            moveRangeWrapping(data, indexOfFirstElement, 1, index);
            indexOfFirstElement = indexForOffset(indexOfFirstElement, 1);
        }

        size--;
        return result;
    }

    public void clear() {
        size = 0;
        indexOfFirstElement = 0;
    }

    @Override
    public int hashCode() {
        int hashCode = 1;
        for (int i = 0; i < size; i++) {
            hashCode = 31 * hashCode + get(i);
        }
        return hashCode;
    }

    //moves a range without wrapping around
    private static void moveRange(int[] array, int sourceStartPosition, int destinationStartPosition, int length) {
        if (sourceStartPosition < 0 || destinationStartPosition < 0 || length < 0
                || sourceStartPosition > array.length - length
                || destinationStartPosition > array.length - length) {
            throw new IndexOutOfBoundsException();
        }
        int offset = destinationStartPosition - sourceStartPosition;
        if (offset > 0) {
            for (int i = destinationStartPosition + length - 1; i >= destinationStartPosition; i--) {
                array[i] = array[i - offset];
            }
        } else if (offset < 0) {
            for (int i = destinationStartPosition; i < destinationStartPosition + length; i++) {
                array[i] = array[i - offset];
            }
        }
    }

    //moves a range, wrapping around if necessary; requires that the foremost element
    //in the direction to be moved would not overwrite another element from the range to be moved
    private static void moveRangeWrapping(int[] array, int sourceStartPosition, int offset, int length) {
        if (length < 0 || length > array.length - Math.abs(offset)
                || sourceStartPosition < 0 || sourceStartPosition >= array.length) {
            throw new IndexOutOfBoundsException();
        }
        if (offset > 0) {
            if (sourceStartPosition > array.length - length - offset) {
                if (sourceStartPosition > array.length - length) {
                    moveRange(array, 0, offset, sourceStartPosition + length - array.length);
                }
                int tempStartPosition = Math.max(array.length - offset, sourceStartPosition);
                moveRange(array, tempStartPosition, tempStartPosition + offset - array.length, (sourceStartPosition < array.length - length ? sourceStartPosition + length : array.length) - tempStartPosition);
            }
            if (array.length - offset > sourceStartPosition) {
                moveRange(array, sourceStartPosition, sourceStartPosition + offset, Math.min(length, array.length - offset - sourceStartPosition));
            }
        } else if (offset < 0) {
            //sourceEndPosition is from 1 to array.length, inclusive
            int sourceEndPosition = sourceStartPosition + length;
            if (sourceEndPosition > array.length || sourceEndPosition < 0) {
                sourceEndPosition -= array.length;
            }

            if (sourceEndPosition + offset < length) {
                if (sourceEndPosition < length) {
                    moveRange(array, sourceStartPosition, sourceStartPosition + offset, array.length - sourceStartPosition);
                }
                int tempStartPosition = Math.max(0, sourceEndPosition - length);
                moveRange(array, tempStartPosition, tempStartPosition + offset + array.length, Math.min(-offset, sourceEndPosition) - tempStartPosition);
            }
            if (sourceEndPosition + offset > 0) {
                int tempStartPosition = Math.max(-offset, sourceEndPosition - length);
                moveRange(array, tempStartPosition, tempStartPosition + offset, sourceEndPosition - tempStartPosition);
            }
        }
    }
}

I've renamed length to size because I found length just too confusing with data.length always coming up somewhere. I've also replaced some of your ArrayIndexOutOfBoundsExceptions with IndexOutOfBoundsExceptions, since an ArrayIndexOutOfBoundsException is only meant for arrays, and not for any index-based data structure.

Unfortunately, the method moveRangeWrapping is an eyesore. Maybe this can be mitigated by introducing more local variables, but the problem is the constant threat of overflows, which often requires the comparison statements in a way that they don't lend themselves to use local variables (e.g. if (sourceStartPosition > array.length - length) instead of if (sourceStartPosition + length > array.length)), so I'm not sure how much can be done about this.

In addition, I've implemented hashCode() so that it produces a hash equivalent to the hash code of an analogous List<Integer>, which can be used both for testing purposes and to prevent clever compiler optimizations (hopefully).