GC overhead limit exceeded - Arrays

Question

i get this error after waiting long time for my code to execute and its pointing me to this method

public Iterable<Board> neighbors() {
        Queue<Board> q = new LinkedList<>();
        int n = dimension();
        int x = 0, y = 0;
        outer:
        // do some stuff to get the x and y
        if (y+1 < n) {
            the line where i get the error -> int [][]arr = new int[n][n];
            for (int i = 0; i < tiles.length; i++) {
                arr[i] = Arrays.copyOf(tiles[i], n);
            }
            // do some stuff
            Board br = new Board(arr);
            if(!this.equals(br)) {
                q.add(new Board(arr));
            }
        }
       if (y-1 >= 0) {
           int [][]arr = new int[n][n];
           for (int i = 0; i < tiles.length; i++) {
                arr[i] = Arrays.copyOf(tiles[i], n);
            }
            // do some stuff
            Board br = new Board(arr);
            if(!this.equals(br)) {
                q.add(new Board(arr));
            }
        }
       if (x-1 >= 0) {
           int [][]arr = new int[n][n];
           for (int i = 0; i < tiles.length; i++) {
                arr[i] = Arrays.copyOf(tiles[i], n);
            }
            // do some stuff
            Board br = new Board(arr);
            if(!this.equals(br)) {
                q.add(new Board(arr));
            }
        }
        if (x+1 < n) {
            int [][]arr = new int[n][n];
            for (int i = 0; i < tiles.length; i++) {
                 arr[i] = Arrays.copyOf(tiles[i], n);
             }
            // do some stuff
            Board br = new Board(arr);
            if(!this.equals(br)) {
                q.add(new Board(arr));
            }
        }
        return q;
    }

i basically need to copy tiles array and make changes to the copy "arr" but keep the tiles array without changing to use it later..i really don't like the way i'm doing it copying and pasting code i think its inefficient but no other way comes to my mind so i would like to know why i get this error "i know its because GC taking more time and not doing alot" but i want to know why its happening in this case also if there is better way to copy the array. also i increased the heap memory to -Xmx1600m

Thanks for your time.

Answer 1

The Problem

It is likely that the problem arises from creating a lot of objects in a short period of time. See this answer for more information.

At the moment, one Board consist of at least four objects:

• The Board itself
• The array arr inside the board
• The three arrays inside arr

Creating Less Objects

Our goal is to create fewer objects (arrays). Since you want to deal with small boards only, we could use one long to store the complete 3×3 board. A long has 64 bit. We use 64 / 9 = 7 bits per field to store the value on that field:

state = ... 0000100 0000011 0000010 0000001 0000000
           4th field   ↑   2nd field   ↑   0th field
                   3rd field       1st field

The following class handles the bit operations.

class Board {

    private final static int SIDE_LENGTH = 3;
    private final static int FIELDS = SIDE_LENGTH * SIDE_LENGTH;
    private final static int BITS_PER_FIELD = 64 / FIELDS;
    private final static long FIELD_MASK = (1 << BITS_PER_FIELD) - 1;

    private long state;

    public Board() {
        for (int field = 0; field < FIELDS; ++field) {
            set(field, field);
        }
    }

    /** Copy constructor. */
    public Board(Board other) {
        this.state = other.state;
    }

    public int get(int x, int y) {
        return get(coordinatesToField(x, y));
    }

    public void set(int x, int y, int value) {
        set(coordinatesToField(x, y), value);
    }

    private int coordinatesToField(int x, int y) {
        return SIDE_LENGTH * y + x;
    }

    private int get(int field) {
        return (int) ((state >>> (field * BITS_PER_FIELD)) & FIELD_MASK);
    }

    private void set(int field, int value) {
        int shift = field * BITS_PER_FIELD;
        state &= ~(FIELD_MASK << shift);
        state |= (long) value << shift;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int field = 0; field < FIELDS; ++field) {
            sb.append(get(field));
            sb.append((field + 1) % SIDE_LENGTH == 0 ? "\n" : "\t");
        }
        return sb.toString();
    }

    // TODO implement equals and hashCode
}

When using this class, you don't have to deal with arrays anymore, which saves not only a lot of objects, but also the copy code in your prorgram.

The class also works for 1×1, 2×2, and 4×4 boards, but not for larger ones due to the 64 bit limit.

Usage Examples

public static void main(String[] args) {
    // Create and print the initial board
    // 0 1 2
    // 3 4 5
    // 6 7 8
    Board b = new Board();
    System.out.println(b);

    // Copy an existing board
    Bord copy = new Board(b);

    // Set the upper right field to value 8
    copy.set(2, 0, 8);

    // Print the center field
    // 4
    Syste.out.println(copy.get(1, 1));

}

Additional Ideas

You even could avoid creating Board objects at all, and just store the long values. But that doesn't help when you are using generics (such as LinkedList) because of Java's auto boxing.

Also note that LinkedList wraps each entry in an additional node object. Maybe you can use a more efficient DataStructure like a circular buffer.

Depending on what you are doing, you might as well have a look at the Flyweight design pattern.