Harmony
  1. Harmony
  2. HARMONY-6068

[luni] Improve Integer.toString(int) performance

    Details

    • Type: Improvement Improvement
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: 5.0M8
    • Fix Version/s: 5.0M9
    • Component/s: Classlib
    • Labels:
      None
    • Patch Info:
      Patch Available

      Description

      I very agree with Aleksey Shipilev' comment [1] for JIRA HARMONY-6056 as following, so I implement an optimized algorithm for Integer.toString(int) method. Thanks to Aleksey Shipilev's benchmark, here are the test results[2] on my windows platform.
      [1] "Ok, we can implement the in-place Integer.toString() and specialize
      the radix-10 conversion in Integer. Then Classlib performance guys
      might use the inplace conversion to optimize StringBuilder performance
      or even catch the concatenation like J9 does.
      My idea is to share whatever optimization between all VMs that use the Classlib."
      [2]
      Result for Harmony java6 branch:
      (String)base + (int)add:
      -------------------------------------------
      base length (vars with rows): 0..2..10
      add length (vars with cols): 0..2..10

      loop duration = 100 msecs
      target variance = 0.05

      ops/msec, the more the better:
      6721, 6096, *4650, *3846, *3178,
      *8080, *5833, *4447, 3731, 3048,
      *7985, *5848, 4788, 3727, *3114,
      *7891, 5592, *4389, *3560, 3048,
      8388, 5607, *4522, 3727, 3051,

      After applied my patch:
      (String)base + (int)add:
      -------------------------------------------
      base length (vars with rows): 0..2..10
      add length (vars with cols): 0..2..10

      loop duration = 100 msecs
      target variance = 0.05

      ops/msec, the more the better:
      8322, 6721, 4791, 4788, 4788,
      8388, 6721, 5156, *5012, 4797,
      8388, 6707, 5161, *4963, 4795,
      8388, 6707, *5126, 4802, 4788,
      *8048, 6700, *5021, 4802, *4687,

      1. HARMONY-6068.diff
        4 kB
        Jim Yu
      2. HARMONY-6068-final.diff
        4 kB
        Jim Yu
      3. HARMONY-6068-final-V2.diff
        4 kB
        Jim Yu
      4. HARMONY-6068-merged-v1.diff
        5 kB
        Aleksey Shipilev
      5. HARMONY-6068-merged-v2.diff
        8 kB
        Aleksey Shipilev
      6. HARMONY-6068-testcase.diff
        1 kB
        Jim Yu

        Issue Links

          Activity

          Hide
          Tim Ellison added a comment -

          No response, assuming ok.

          Show
          Tim Ellison added a comment - No response, assuming ok.
          Hide
          Tim Ellison added a comment -

          Tests applied at repo revision r738625.

          Please check they were applied as you expected.

          Show
          Tim Ellison added a comment - Tests applied at repo revision r738625. Please check they were applied as you expected.
          Hide
          Jim Yu added a comment -

          Thanks, Tim. I've added more test cases for this method.

          Show
          Jim Yu added a comment - Thanks, Tim. I've added more test cases for this method.
          Hide
          Tim Ellison added a comment -

          Forgot to mention the patch was applied at repo revision r732988.

          Show
          Tim Ellison added a comment - Forgot to mention the patch was applied at repo revision r732988.
          Hide
          Jim Yu added a comment -

          Sorry for bringing formatting changes, I've attached a new one : )

          Show
          Jim Yu added a comment - Sorry for bringing formatting changes, I've attached a new one : )
          Hide
          Tim Ellison added a comment -

          Thanks to all who worked on this.

          I applied the final patch with minor changes:

          • removed the new lines
          • renamed 'numbers' array to 'decimalScale'
          • added a couple of comments, more would be good

          Anybody write functional tests that ensure the boundary cases of the algorithm are working correctly?

          Show
          Tim Ellison added a comment - Thanks to all who worked on this. I applied the final patch with minor changes: removed the new lines renamed 'numbers' array to 'decimalScale' added a couple of comments, more would be good Anybody write functional tests that ensure the boundary cases of the algorithm are working correctly?
          Hide
          Aleksey Shipilev added a comment -

          Right. Jim, the patch looks good, and ideally there should be no formatting changes included (there're some newlines crawled into the patch).

          Of course the same block might be applied for Short and Long, but let's adopt this patch first and then generalize it for Long.toString() and Short.toString().

          Show
          Aleksey Shipilev added a comment - Right. Jim, the patch looks good, and ideally there should be no formatting changes included (there're some newlines crawled into the patch). Of course the same block might be applied for Short and Long, but let's adopt this patch first and then generalize it for Long.toString() and Short.toString().
          Hide
          Jim Yu added a comment -

          Regis,

          Because the first algorithm has better performance for small integers while the second one has better performance for big integers. We can get an overall high performance for all integers if we use different algorithm for different integers. These algorithms can definitely be applied to Short and Long just with minor change.

          Show
          Jim Yu added a comment - Regis, Because the first algorithm has better performance for small integers while the second one has better performance for big integers. We can get an overall high performance for all integers if we use different algorithm for different integers. These algorithms can definitely be applied to Short and Long just with minor change.
          Hide
          Regis Xu added a comment -

          Hi Jim,

          Why does integer between -1000 and 1000 use different algorithmes? And is it ok to apply this algorithm to Short and Long?

          Show
          Regis Xu added a comment - Hi Jim, Why does integer between -1000 and 1000 use different algorithmes? And is it ok to apply this algorithm to Short and Long?
          Hide
          Jim Yu added a comment -

          Hi Nathan,
          This patch is for both trunk and Java 6 branch.

          Show
          Jim Yu added a comment - Hi Nathan, This patch is for both trunk and Java 6 branch.
          Hide
          Nathan Beyer added a comment -

          Is this for the Java 6 branch only or the is subject wrong?

          Show
          Nathan Beyer added a comment - Is this for the Java 6 branch only or the is subject wrong?
          Hide
          Aleksey Shipilev added a comment -

          HARMONY-6068-merged-v2.diff
          Updated.

          Show
          Aleksey Shipilev added a comment - HARMONY-6068 -merged-v2.diff Updated.
          Hide
          Aleksey Shipilev added a comment -

          HARMONY-6068-merged-v1.diff

          Merged implementations from this issue, Kevin's from HARMONY-6056, and mine (a bit hacked Kevin's one).

          Show
          Aleksey Shipilev added a comment - HARMONY-6068 -merged-v1.diff Merged implementations from this issue, Kevin's from HARMONY-6056 , and mine (a bit hacked Kevin's one).
          Hide
          Aleksey Shipilev added a comment -

          This patch is another version of radix-10 conversion inspired by HARMONY-6056.

          Show
          Aleksey Shipilev added a comment - This patch is another version of radix-10 conversion inspired by HARMONY-6056 .

            People

            • Assignee:
              Tim Ellison
              Reporter:
              Jim Yu
            • Votes:
              0 Vote for this issue
              Watchers:
              1 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Time Tracking

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

                  Development