Harmony
  1. Harmony
  2. HARMONY-6323

[classlib] [luni] Simplify and speed-up collection shuffle, add a non-probabilistic test

    Details

    • Type: Improvement Improvement
    • Status: Closed
    • Priority: Minor Minor
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 5.0M12
    • Component/s: Classlib
    • Labels:
      None
    • Environment:
      SVN Revision 801399
    • Patch Info:
      Patch Available
    • Estimated Complexity:
      Moderate

      Description

      Shuffle needlessly tests Random.nextInt() for a negative value
      It iterates from index N-1 to 0, which means it always swaps index 0 with itself needlessly.
      It is only tested with probabilistic tests, the patch adds a proper test. Note that the attached test also passes on the RI.

        Activity

        Hide
        Jesse Wilson added a comment -

        #Android

        Show
        Jesse Wilson added a comment - #Android
        Hide
        Tim Ellison added a comment -

        Thanks Jesse.

        Patch applied to LUNI module at repo revision r810887.

        Please verify it was applied as you expected.

        Show
        Tim Ellison added a comment - Thanks Jesse. Patch applied to LUNI module at repo revision r810887. Please verify it was applied as you expected.
        Hide
        Tim Ellison added a comment -

        Temporarily re-opening this issue as I have reverted the test case update in r810919.

        While the new tests pass ok on DRLVM, they have failed on IBM J9 VME with

        testShuffleRandomAccessWithSeededRandom Failure expected:<[B, A, D, C, G, E, F]> but was:<[A, B, D, C, G, E, F]>
        testShuffleWithSeededRandom Failure expected:<[B, A, D, C, G, E, F]> but was:<[A, B, D, C, G, E, F]>

        The immediate thought was that the Random seed was returning different random values, but a quick check shows that is not so. I'll investigate further.

        Show
        Tim Ellison added a comment - Temporarily re-opening this issue as I have reverted the test case update in r810919. While the new tests pass ok on DRLVM, they have failed on IBM J9 VME with testShuffleRandomAccessWithSeededRandom Failure expected:< [B, A, D, C, G, E, F] > but was:< [A, B, D, C, G, E, F] > testShuffleWithSeededRandom Failure expected:< [B, A, D, C, G, E, F] > but was:< [A, B, D, C, G, E, F] > The immediate thought was that the Random seed was returning different random values, but a quick check shows that is not so. I'll investigate further.
        Hide
        Tim Ellison added a comment -

        Jesse, the fix required changing the impl to work the same way as before, swapping all the way down to the second element.

        Index: src/main/java/java/util/Collections.java
        ===================================================================
        — src/main/java/java/util/Collections.java (revision 811363)
        +++ src/main/java/java/util/Collections.java (working copy)
        @@ -1844,13 +1844,13 @@
        final List<Object> objectList = (List<Object>) list;

        if (list instanceof RandomAccess) {

        • for (int i = objectList.size() - 1; i > 1; i--)
          Unknown macro: {+ for (int i = objectList.size() - 1; i > 0; i--) { int index = random.nextInt(i + 1); objectList.set(index, objectList.set(i, objectList.get(index))); } }

          else {
          Object[] array = objectList.toArray();

        • for (int i = array.length - 1; i > 1; i--) {
          + for (int i = array.length - 1; i > 0; i--) {
          int index = random.nextInt(i + 1);
          Object temp = array[i];
          array[i] = array[index];

        The fix and tests were committed to the LUNI module at repo revision r811363.

        Please check you agree with this fix.

        Show
        Tim Ellison added a comment - Jesse, the fix required changing the impl to work the same way as before, swapping all the way down to the second element. Index: src/main/java/java/util/Collections.java =================================================================== — src/main/java/java/util/Collections.java (revision 811363) +++ src/main/java/java/util/Collections.java (working copy) @@ -1844,13 +1844,13 @@ final List<Object> objectList = (List<Object>) list; if (list instanceof RandomAccess) { for (int i = objectList.size() - 1; i > 1; i--) Unknown macro: {+ for (int i = objectList.size() - 1; i > 0; i--) { int index = random.nextInt(i + 1); objectList.set(index, objectList.set(i, objectList.get(index))); } } else { Object[] array = objectList.toArray(); for (int i = array.length - 1; i > 1; i--) { + for (int i = array.length - 1; i > 0; i--) { int index = random.nextInt(i + 1); Object temp = array [i] ; array [i] = array [index] ; The fix and tests were committed to the LUNI module at repo revision r811363. Please check you agree with this fix.
        Hide
        Jesse Wilson added a comment -

        Yup, your fixes look good, and I'm disappointed I made such a clumsy off-by-one error! Thanks!

        I'm surprised that the test behaves differently on different VMs; with the random properly seeded it should give the same output everywhere. I'm going to look into this.

        Show
        Jesse Wilson added a comment - Yup, your fixes look good, and I'm disappointed I made such a clumsy off-by-one error! Thanks! I'm surprised that the test behaves differently on different VMs; with the random properly seeded it should give the same output everywhere. I'm going to look into this.
        Hide
        Jesse Wilson added a comment -

        LGTM

        Show
        Jesse Wilson added a comment - LGTM
        Hide
        Tim Ellison added a comment -

        Jesse wrote:
        > I'm surprised that the test behaves differently on different VMs;
        > with the random properly seeded it should give the same
        > output everywhere. I'm going to look into this.

        I already went back and checked that the behavior is no different on the DRLVM, and indeed it is identical. So I must have messed up on the pre-commit testing.

        I explicitly checked that Random(0) produces the identical results on IBM/DRLVM/RI and it does. All is well now.

        Show
        Tim Ellison added a comment - Jesse wrote: > I'm surprised that the test behaves differently on different VMs; > with the random properly seeded it should give the same > output everywhere. I'm going to look into this. I already went back and checked that the behavior is no different on the DRLVM, and indeed it is identical. So I must have messed up on the pre-commit testing. I explicitly checked that Random(0) produces the identical results on IBM/DRLVM/RI and it does. All is well now.
        Hide
        Tim Ellison added a comment -

        ( But I don't know how your original impl could have passed your test?! )

        Show
        Tim Ellison added a comment - ( But I don't know how your original impl could have passed your test?! )
        Hide
        Jesse Wilson added a comment -

        I have no idea. I think I must have uploaded a working draft of the patch. I should be more careful!

        Show
        Jesse Wilson added a comment - I have no idea. I think I must have uploaded a working draft of the patch. I should be more careful!

          People

          • Assignee:
            Tim Ellison
            Reporter:
            Jesse Wilson
          • Votes:
            0 Vote for this issue
            Watchers:
            0 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Time Tracking

              Estimated:
              Original Estimate - 0.25h
              0.25h
              Remaining:
              Remaining Estimate - 0.25h
              0.25h
              Logged:
              Time Spent - Not Specified
              Not Specified

                Development