I was going to add another ArrayList review comment in the code but it
was getting too long and so I'm going to write it here and reference
this message in the code.
I was looking at the growAtEnd method - fixing the things I wrote about
in r982777. It says:
private void growAtEnd(int required) {
int lastIndex = firstIndex + size;
if (required < array.length - size) {
if (size > 0) {
[*] System.arraycopy(array, firstIndex, array, 0, size);
int start = size < firstIndex ? firstIndex : size;
Arrays.fill(array, start, array.length, null);
}
firstIndex = 0;
} else {
// create big array and copy everything to it
}
}
At [*], we know that:
1) there is space at the front (firstIndex of space to be exact),
2) From (1) we can infer that there must have been an insertion at the
front at some point since that is the only code path to growAtFront(). [0]
In order to make space at the end (even a single entry) we use *all* the
space at the beginning. This doesn't seem optimal because:
A) We know 2) so it is not unlikely that there will be another insertion
at the front in future. Consider the pathological case of alternately
adding at front and end. growAtFront has the same logic so we end up
copying everything back and forth moving the free space from end to end.
B) The more we move the more we need to null out. Consider the case
where we have 100 of free space at the front and none at the end and
we are appending one element to the end. Currently we move all the
elements by 100 places to create 100 free space at the end. We then
null out the old entries that we didn't overwrite during the move. If
we'd only moved 50 places leaving a more balanced amount of free space
we'd only have to null out at most 50 old entries.
Also, we actually null out too much because:
a) We fill to array.length but we should fill to lastIndex (or
firstIndex-size) [this is already in the review comments]
b) We should assume that we are creating the required space for a
reason - that it is about to be used - so we needn't null the entries
we are about to write too anyway.
I think the excessive resetting to null fixes are a safe call so I am
going to make those soon.
I'm not exactly sure what to do about the other issue.
Comments welcome.
Regards,
Mark.
[0] Actually just before sending this I realised that there is another
way to get free space at the front... be removing from location 0 -
i.e. treating the ArrayList as a kind of queue. But I'm not sure this
entirely invalidates the argument it just isn't so clear cut.
