Out of memory?

The test below fails for out of memory. I didn't think it was that intense. Is there a low limit on memory? Just checking.

Thanks!

  • java.lang.OutOfMemoryError: Java heap space
  • at IntArrayUtilities.createLinearArray(IntArrayUtilities.java:108)

  • at IntArrayUtilitiesTest.testBinarySearch(IntArrayUtilitiesTest.java:41)

  • at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)

  • at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)

  • at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)

  • at java.lang.reflect.Method.invoke(Method.java:497)

  • at org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:50)

  • at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:12)

  • at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:47)

  • at org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:17)

  • at org.junit.internal.runners.statements.RunBefores.evaluate(RunBefores.java:26)

  • at org.junit.internal.runners.statements.RunAfters.evaluate(RunAfters.java:27)

  • at org.junit.internal.runners.statements.FailOnTimeout$CallableStatement.call(FailOnTimeout.java:298)

  • at org.junit.internal.runners.statements.FailOnTimeout$CallableStatement.call(FailOnTimeout.java:292)

  • at java.util.concurrent.FutureTask.run(FutureTask.java:266)

  • at java.lang.Thread.run(Thread.java:745)

  @Test

  public void testShuffle() {

   // fail("unimplemented");

    // This test is inspired by experiments 1.1.36 and 1.1.37 in Sedgewick

    // and Wayne, Algorithms, 4th edition. It tests whether, over many

    // shuffles, each card is equally likely to end up in each position. It

    // may fail once in a great while, but it generally passes for a correct

    // shuffling algorithm and fails for common incorrect algorithms.

    int[] unshuffled = IntArrayUtilities.createLinearArray(25);

    int[][] counts = new int[unshuffled.length][unshuffled.length];

    for (int trial = 0; trial < 5000; trial++) {

      boolean[] seen = new boolean[unshuffled.length];

      int[] testArray = IntArrayUtilities.createLinearArray(unshuffled.length);

      IntArrayUtilities.shuffle(testArray);

      for (int i = 0; i < unshuffled.length; i++) {

        for (int j = 0; j < testArray.length; j++) {

          int a = unshuffled[i];

          int b = testArray[j];

          if (a == b) {

            counts[i][j]++;

            assertFalse(seen[i]);

            seen[i] = true;

          }

        }

      }

    }

    for (int i = 0; i < unshuffled.length; i++) {

      for (int j = 0; j < unshuffled.length; j++) {

        assertTrue(counts[i][j] > (5000.0 / unshuffled.length) * 0.5);

        assertTrue(counts[i][j] < (5000.0 / unshuffled.length) * 1.5);

      }

    }

  }
Groups:

Comments

Stephen Edwards

The JavaTddPlugin provides 512m

The JavaTddPlugin provides a max heap limit of 512M, which seems like it would be more than enough here.  However, just because the exception arises in this test, that doesn't mean this test is the primary culprit--if earlier test(s) use up most of the heap in a way that does not allow for garbage reclamation, then the problem might show up in a later test.  Also, the JUnit infrastructure is basically buffering all test results and output in memory, which contributes to heap usage if there are extreme amounts of output being generated in earlier tests.   Overall, though, I don't see any problems (and certainly, the memory exhaustion should show when running the test suite from the command line or in Eclipse without enlarging the Java heap size, which defaults to just 64M).