performance_problems.md

Performance Problems

While the code as is works, it will not perform well.

Since we copy the underlying array every time someone adds a new element it can be expensive to add a lot of elements.

Pretend we were going to add a hundred elements to the growable array.

~class GrowableIntArray {
~    // Store an int[] internally
~    private int[] data;
~
~    GrowableIntArray() {
~        // Make sure to initialize it correctly
~        this.data = new int[0];
~    }
~
~    // When someone wants to get an item, get it from the array
~    int get(int index) {
~        return this.data[index];
~    }
~
~    // Same deal when someone wants to set an item at an index.
~    void set(int index, int value) {
~        this.data[index] = value;
~    }
~
~    // And we need an accessor for the size so that someone
~    // can loop over the array.
~    int size() {
~        return this.data.length;
~    }
~
~    void add(int value) {
~        // Copy the old array to a new, bigger one
~        int[] newArray = new int[this.data.length + 1];
~        for (int i = 0; i < this.data.length; i++) {
~            newArray[i] = this.data[i];
~        }
~
~        // Then put the new element at the end
~        newArray[newArray.length - 1] = value;
~
~        // And swap the array
~        this.data = newArray; 
~    }
~}
~
~
class Main {
    void main() {
        var array = new GrowableIntArray();

        for (int i = 0; i < 100; i++) {
            array.add(i);
        }

        System.out.println(array.size());
    }
}

For the each element we need to make a copy of an array. So when we add the first element we need to make an array 1 element big. The second, copy that 1 element array and make a new 2 element one.

So if you do napkin math on the things that need to happen you get this

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 + 12 ...

Which is just a crazy number of copies. It means calling .add on an already big list will be slow and calling .add a lot of times to make a big list will be very slow.