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

        Transition Time In Source Status Execution Times Last Executer Last Execution Date
        Open Open Resolved Resolved
        6d 11h 3m 1 Tim Ellison 03/Sep/09 11:51
        Resolved Resolved Reopened Reopened
        2h 29m 1 Tim Ellison 03/Sep/09 14:21
        Reopened Reopened Resolved Resolved
        23h 11m 1 Tim Ellison 04/Sep/09 13:33
        Resolved Resolved Closed Closed
        5h 49m 1 Jesse Wilson 04/Sep/09 19:22
        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!
        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
        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.
        Jesse Wilson made changes -
        Status Resolved [ 5 ] Closed [ 6 ]
        Hide
        Jesse Wilson added a comment -

        LGTM

        Show
        Jesse Wilson added a comment - LGTM
        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.
        Tim Ellison made changes -
        Status Reopened [ 4 ] Resolved [ 5 ]
        Resolution Fixed [ 1 ]
        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.
        Tim Ellison made changes -
        Resolution Fixed [ 1 ]
        Status Resolved [ 5 ] Reopened [ 4 ]
        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.
        Tim Ellison made changes -
        Status Open [ 1 ] Resolved [ 5 ]
        Fix Version/s 5.0M12 [ 12314191 ]
        Resolution Fixed [ 1 ]
        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.
        Tim Ellison made changes -
        Summary Simplify and speed-up shuffle, add a non-probabilistic test [classlib] [luni] Simplify and speed-up collection shuffle, add a non-probabilistic test
        Tim Ellison made changes -
        Assignee Tim Ellison [ tellison ]
        Jesse Wilson made changes -
        Priority Major [ 3 ] Minor [ 4 ]
        Hide
        Jesse Wilson added a comment -

        #Android

        Show
        Jesse Wilson added a comment - #Android
        Jesse Wilson made changes -
        Field Original Value New Value
        Attachment Shuffle-fixes.patch [ 12417942 ]
        Jesse Wilson created issue -

          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