Problem
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;
}
}
Solution
-
There is a small bug: In the method
add(int, int), it should probably beif (index > length || index < 0) throw new ArrayIndexOutOfBoundsException(index);instead of
if (index >= length || index < 0) throw new ArrayIndexOutOfBoundsException(index);Inserting at the index
lengthwould just mean appending an element to the end of the iVector, so an index oflengthwouldn’t be invalid. -
Also,
data.length + data.length/2might overflow for very large values oflength. You could prepare for this by checking whetherInteger.MAX_VALUE - data.length/2 >= data.length. -
In the method
ensureCapacity(int), it would suffice to copylengthelements instead ofdata.lengthelements, since the values of all elements indatawith an index equal to or greater thanlengthare irrelevant. -
You could simply call
add(length, value)fromadd(int value), because right now, the code ofadd(int)is effectively duplicated inadd(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 likeaddAll(which could also employ other optimizations like callingSystem.arraycopyinstead 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()returnsvoidwhereasremove(int index)returns the value previously atindex. This is inconsistent. I suggest you makeremove()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
afrom 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
ebetweencandf, 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
dbeforee, you could do this:cdefgh---bWhile this would make simple
getorsetoperations a tiny bit more expensive, because you would have to calculate the index for the internal array from the public index for theiVector, I guess that this can save quite a bit of performance foraddorremoveoperations 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).