You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@harmony.apache.org by "Rustem Rafikov (JIRA)" <ji...@apache.org> on 2006/06/21 15:05:29 UTC
[jira] Created: (HARMONY-636) performance enhancement for
Arrays.sort(Object[]...)
performance enhancement for Arrays.sort(Object[]...)
----------------------------------------------------
Key: HARMONY-636
URL: http://issues.apache.org/jira/browse/HARMONY-636
Project: Harmony
Type: Improvement
Components: Classlib
Reporter: Rustem Rafikov
Priority: Minor
Attachments: Arrays_objectsort_patch.zip
Dear All,
I would like to suggest a patch improving performance of object's sorting algorithms.
Actually the algorithm suggested uses different methods for sorting objects and strings:
1. Object's sorting uses adaptive merge-sort. It works much faster for nearly sorted arrays.
2. String's sorting algorithms are specially tuned for strings.
Attached zip contains the patch itself and a micro benchmark.
The micro-bench loads 100000 strings from aspell dictionary (you can find it in /usr/lib/aspell, for example: english-med-only), makes it sorted with different degree and then sort it.
Even though this patch adds a lot of code lines instead of a little piece of original code, the test shows performance improvement as much as 45% for objects and 50% for strings.
Thanks,
Rustem
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
http://www.atlassian.com/software/jira
[jira] Updated: (HARMONY-636) performance enhancement for
Arrays.sort(Object[]...)
Posted by "Rustem Rafikov (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HARMONY-636?page=all ]
Rustem Rafikov updated HARMONY-636:
-----------------------------------
Attachment: Arrays.objectsort.07042006.zip
Hi Tim,
New patch is attached.
--
Thanks, Rustem
> performance enhancement for Arrays.sort(Object[]...)
> ----------------------------------------------------
>
> Key: HARMONY-636
> URL: http://issues.apache.org/jira/browse/HARMONY-636
> Project: Harmony
> Type: Improvement
> Components: Classlib
> Reporter: Rustem Rafikov
> Assignee: Tim Ellison
> Priority: Minor
> Attachments: Arrays.objectsort.07042006.zip, Arrays_objectsort_patch.zip
>
> Dear All,
> I would like to suggest a patch improving performance of object's sorting algorithms.
> Actually the algorithm suggested uses different methods for sorting objects and strings:
> 1. Object's sorting uses adaptive merge-sort. It works much faster for nearly sorted arrays.
> 2. String's sorting algorithms are specially tuned for strings.
> Attached zip contains the patch itself and a micro benchmark.
> The micro-bench loads 100000 strings from aspell dictionary (you can find it in /usr/lib/aspell, for example: english-med-only), makes it sorted with different degree and then sort it.
> Even though this patch adds a lot of code lines instead of a little piece of original code, the test shows performance improvement as much as 45% for objects and 50% for strings.
> Thanks,
> Rustem
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
http://www.atlassian.com/software/jira
[jira] Assigned: (HARMONY-636) performance enhancement for
Arrays.sort(Object[]...)
Posted by "Tim Ellison (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HARMONY-636?page=all ]
Tim Ellison reassigned HARMONY-636:
-----------------------------------
Assign To: Tim Ellison
> performance enhancement for Arrays.sort(Object[]...)
> ----------------------------------------------------
>
> Key: HARMONY-636
> URL: http://issues.apache.org/jira/browse/HARMONY-636
> Project: Harmony
> Type: Improvement
> Components: Classlib
> Reporter: Rustem Rafikov
> Assignee: Tim Ellison
> Priority: Minor
> Attachments: Arrays_objectsort_patch.zip
>
> Dear All,
> I would like to suggest a patch improving performance of object's sorting algorithms.
> Actually the algorithm suggested uses different methods for sorting objects and strings:
> 1. Object's sorting uses adaptive merge-sort. It works much faster for nearly sorted arrays.
> 2. String's sorting algorithms are specially tuned for strings.
> Attached zip contains the patch itself and a micro benchmark.
> The micro-bench loads 100000 strings from aspell dictionary (you can find it in /usr/lib/aspell, for example: english-med-only), makes it sorted with different degree and then sort it.
> Even though this patch adds a lot of code lines instead of a little piece of original code, the test shows performance improvement as much as 45% for objects and 50% for strings.
> Thanks,
> Rustem
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
http://www.atlassian.com/software/jira
[jira] Commented: (HARMONY-636) performance enhancement for
Arrays.sort(Object[]...)
Posted by "Rustem Rafikov (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HARMONY-636?page=comments#action_12417264 ]
Rustem Rafikov commented on HARMONY-636:
----------------------------------------
Hi Tim,
Unfortunately, the test is not perfect :). It requires that words list must be in aspell format (i.e. strings should be delimited with 0x00).
Such stack trace may be if you use hand-written words file with strings delimited by 'new line'.
Is it such case?
Should I attach my words.txt to run the test?
> performance enhancement for Arrays.sort(Object[]...)
> ----------------------------------------------------
>
> Key: HARMONY-636
> URL: http://issues.apache.org/jira/browse/HARMONY-636
> Project: Harmony
> Type: Improvement
> Components: Classlib
> Reporter: Rustem Rafikov
> Assignee: Tim Ellison
> Priority: Minor
> Attachments: Arrays_objectsort_patch.zip
>
> Dear All,
> I would like to suggest a patch improving performance of object's sorting algorithms.
> Actually the algorithm suggested uses different methods for sorting objects and strings:
> 1. Object's sorting uses adaptive merge-sort. It works much faster for nearly sorted arrays.
> 2. String's sorting algorithms are specially tuned for strings.
> Attached zip contains the patch itself and a micro benchmark.
> The micro-bench loads 100000 strings from aspell dictionary (you can find it in /usr/lib/aspell, for example: english-med-only), makes it sorted with different degree and then sort it.
> Even though this patch adds a lot of code lines instead of a little piece of original code, the test shows performance improvement as much as 45% for objects and 50% for strings.
> Thanks,
> Rustem
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
http://www.atlassian.com/software/jira
[jira] Commented: (HARMONY-636) performance enhancement for
Arrays.sort(Object[]...)
Posted by "Rustem Rafikov (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HARMONY-636?page=comments#action_12419454 ]
Rustem Rafikov commented on HARMONY-636:
----------------------------------------
Looks fine.
Thanks Tim.
--bwR
> performance enhancement for Arrays.sort(Object[]...)
> ----------------------------------------------------
>
> Key: HARMONY-636
> URL: http://issues.apache.org/jira/browse/HARMONY-636
> Project: Harmony
> Type: Improvement
> Components: Classlib
> Reporter: Rustem Rafikov
> Assignee: Tim Ellison
> Priority: Minor
> Attachments: Arrays.objectsort.07042006.zip, Arrays.objectsort.07042006_2.zip, Arrays_objectsort_patch.zip
>
> Dear All,
> I would like to suggest a patch improving performance of object's sorting algorithms.
> Actually the algorithm suggested uses different methods for sorting objects and strings:
> 1. Object's sorting uses adaptive merge-sort. It works much faster for nearly sorted arrays.
> 2. String's sorting algorithms are specially tuned for strings.
> Attached zip contains the patch itself and a micro benchmark.
> The micro-bench loads 100000 strings from aspell dictionary (you can find it in /usr/lib/aspell, for example: english-med-only), makes it sorted with different degree and then sort it.
> Even though this patch adds a lot of code lines instead of a little piece of original code, the test shows performance improvement as much as 45% for objects and 50% for strings.
> Thanks,
> Rustem
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
http://www.atlassian.com/software/jira
[jira] Updated: (HARMONY-636) performance enhancement for
Arrays.sort(Object[]...)
Posted by "Rustem Rafikov (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HARMONY-636?page=all ]
Rustem Rafikov updated HARMONY-636:
-----------------------------------
Attachment: Arrays_objectsort_patch.zip
> performance enhancement for Arrays.sort(Object[]...)
> ----------------------------------------------------
>
> Key: HARMONY-636
> URL: http://issues.apache.org/jira/browse/HARMONY-636
> Project: Harmony
> Type: Improvement
> Components: Classlib
> Reporter: Rustem Rafikov
> Priority: Minor
> Attachments: Arrays_objectsort_patch.zip
>
> Dear All,
> I would like to suggest a patch improving performance of object's sorting algorithms.
> Actually the algorithm suggested uses different methods for sorting objects and strings:
> 1. Object's sorting uses adaptive merge-sort. It works much faster for nearly sorted arrays.
> 2. String's sorting algorithms are specially tuned for strings.
> Attached zip contains the patch itself and a micro benchmark.
> The micro-bench loads 100000 strings from aspell dictionary (you can find it in /usr/lib/aspell, for example: english-med-only), makes it sorted with different degree and then sort it.
> Even though this patch adds a lot of code lines instead of a little piece of original code, the test shows performance improvement as much as 45% for objects and 50% for strings.
> Thanks,
> Rustem
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
http://www.atlassian.com/software/jira
[jira] Commented: (HARMONY-636) performance enhancement for
Arrays.sort(Object[]...)
Posted by "Tim Ellison (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HARMONY-636?page=comments#action_12417135 ]
Tim Ellison commented on HARMONY-636:
-------------------------------------
FYI: I tried to run the test and it failed with:
Sorting strings:
0 %Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Array index out of range: 0
at test.pkg.TestUtils.doArrNearlySorted(TestUtils.java:45)
at test.pkg.SortTest.test(SortTest.java:53)
at test.pkg.SortTest.main(SortTest.java:78)
I will investigate ...
> performance enhancement for Arrays.sort(Object[]...)
> ----------------------------------------------------
>
> Key: HARMONY-636
> URL: http://issues.apache.org/jira/browse/HARMONY-636
> Project: Harmony
> Type: Improvement
> Components: Classlib
> Reporter: Rustem Rafikov
> Assignee: Tim Ellison
> Priority: Minor
> Attachments: Arrays_objectsort_patch.zip
>
> Dear All,
> I would like to suggest a patch improving performance of object's sorting algorithms.
> Actually the algorithm suggested uses different methods for sorting objects and strings:
> 1. Object's sorting uses adaptive merge-sort. It works much faster for nearly sorted arrays.
> 2. String's sorting algorithms are specially tuned for strings.
> Attached zip contains the patch itself and a micro benchmark.
> The micro-bench loads 100000 strings from aspell dictionary (you can find it in /usr/lib/aspell, for example: english-med-only), makes it sorted with different degree and then sort it.
> Even though this patch adds a lot of code lines instead of a little piece of original code, the test shows performance improvement as much as 45% for objects and 50% for strings.
> Thanks,
> Rustem
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
http://www.atlassian.com/software/jira
[jira] Closed: (HARMONY-636) performance enhancement for
Arrays.sort(Object[]...)
Posted by "Tim Ellison (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HARMONY-636?page=all ]
Tim Ellison closed HARMONY-636:
-------------------------------
Verified by Rustem.
> performance enhancement for Arrays.sort(Object[]...)
> ----------------------------------------------------
>
> Key: HARMONY-636
> URL: http://issues.apache.org/jira/browse/HARMONY-636
> Project: Harmony
> Type: Improvement
> Components: Classlib
> Reporter: Rustem Rafikov
> Assignee: Tim Ellison
> Priority: Minor
> Attachments: Arrays.objectsort.07042006.zip, Arrays.objectsort.07042006_2.zip, Arrays_objectsort_patch.zip
>
> Dear All,
> I would like to suggest a patch improving performance of object's sorting algorithms.
> Actually the algorithm suggested uses different methods for sorting objects and strings:
> 1. Object's sorting uses adaptive merge-sort. It works much faster for nearly sorted arrays.
> 2. String's sorting algorithms are specially tuned for strings.
> Attached zip contains the patch itself and a micro benchmark.
> The micro-bench loads 100000 strings from aspell dictionary (you can find it in /usr/lib/aspell, for example: english-med-only), makes it sorted with different degree and then sort it.
> Even though this patch adds a lot of code lines instead of a little piece of original code, the test shows performance improvement as much as 45% for objects and 50% for strings.
> Thanks,
> Rustem
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
http://www.atlassian.com/software/jira
[jira] Resolved: (HARMONY-636) performance enhancement for
Arrays.sort(Object[]...)
Posted by "Tim Ellison (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HARMONY-636?page=all ]
Tim Ellison resolved HARMONY-636:
---------------------------------
Resolution: Fixed
Thanks for the enhancement Rustem.
Your second patch was applied to the LUNI module at repo revision r419207.
Please check that the patch was applied as you expected.
> performance enhancement for Arrays.sort(Object[]...)
> ----------------------------------------------------
>
> Key: HARMONY-636
> URL: http://issues.apache.org/jira/browse/HARMONY-636
> Project: Harmony
> Type: Improvement
> Components: Classlib
> Reporter: Rustem Rafikov
> Assignee: Tim Ellison
> Priority: Minor
> Attachments: Arrays.objectsort.07042006.zip, Arrays.objectsort.07042006_2.zip, Arrays_objectsort_patch.zip
>
> Dear All,
> I would like to suggest a patch improving performance of object's sorting algorithms.
> Actually the algorithm suggested uses different methods for sorting objects and strings:
> 1. Object's sorting uses adaptive merge-sort. It works much faster for nearly sorted arrays.
> 2. String's sorting algorithms are specially tuned for strings.
> Attached zip contains the patch itself and a micro benchmark.
> The micro-bench loads 100000 strings from aspell dictionary (you can find it in /usr/lib/aspell, for example: english-med-only), makes it sorted with different degree and then sort it.
> Even though this patch adds a lot of code lines instead of a little piece of original code, the test shows performance improvement as much as 45% for objects and 50% for strings.
> Thanks,
> Rustem
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
http://www.atlassian.com/software/jira
[jira] Commented: (HARMONY-636) performance enhancement for
Arrays.sort(Object[]...)
Posted by "Tim Ellison (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HARMONY-636?page=comments#action_12419086 ]
Tim Ellison commented on HARMONY-636:
-------------------------------------
Thanks for the updated patch Rustem.
I get a test failure after applying the update from out test cases, as follows:
> performance enhancement for Arrays.sort(Object[]...)
> ----------------------------------------------------
>
> Key: HARMONY-636
> URL: http://issues.apache.org/jira/browse/HARMONY-636
> Project: Harmony
> Type: Improvement
> Components: Classlib
> Reporter: Rustem Rafikov
> Assignee: Tim Ellison
> Priority: Minor
> Attachments: Arrays.objectsort.07042006.zip, Arrays_objectsort_patch.zip
>
> Dear All,
> I would like to suggest a patch improving performance of object's sorting algorithms.
> Actually the algorithm suggested uses different methods for sorting objects and strings:
> 1. Object's sorting uses adaptive merge-sort. It works much faster for nearly sorted arrays.
> 2. String's sorting algorithms are specially tuned for strings.
> Attached zip contains the patch itself and a micro benchmark.
> The micro-bench loads 100000 strings from aspell dictionary (you can find it in /usr/lib/aspell, for example: english-med-only), makes it sorted with different degree and then sort it.
> Even though this patch adds a lot of code lines instead of a little piece of original code, the test shows performance improvement as much as 45% for objects and 50% for strings.
> Thanks,
> Rustem
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
http://www.atlassian.com/software/jira
[jira] Updated: (HARMONY-636) performance enhancement for
Arrays.sort(Object[]...)
Posted by "Rustem Rafikov (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HARMONY-636?page=all ]
Rustem Rafikov updated HARMONY-636:
-----------------------------------
Attachment: Arrays.objectsort.07042006_2.zip
Sorry,
there was an error when sorting a specified range.
The final (I hope) patch is attached.
All tests have been successfully passed.
Rustem.
> performance enhancement for Arrays.sort(Object[]...)
> ----------------------------------------------------
>
> Key: HARMONY-636
> URL: http://issues.apache.org/jira/browse/HARMONY-636
> Project: Harmony
> Type: Improvement
> Components: Classlib
> Reporter: Rustem Rafikov
> Assignee: Tim Ellison
> Priority: Minor
> Attachments: Arrays.objectsort.07042006.zip, Arrays.objectsort.07042006_2.zip, Arrays_objectsort_patch.zip
>
> Dear All,
> I would like to suggest a patch improving performance of object's sorting algorithms.
> Actually the algorithm suggested uses different methods for sorting objects and strings:
> 1. Object's sorting uses adaptive merge-sort. It works much faster for nearly sorted arrays.
> 2. String's sorting algorithms are specially tuned for strings.
> Attached zip contains the patch itself and a micro benchmark.
> The micro-bench loads 100000 strings from aspell dictionary (you can find it in /usr/lib/aspell, for example: english-med-only), makes it sorted with different degree and then sort it.
> Even though this patch adds a lot of code lines instead of a little piece of original code, the test shows performance improvement as much as 45% for objects and 50% for strings.
> Thanks,
> Rustem
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
http://www.atlassian.com/software/jira
[jira] Commented: (HARMONY-636) performance enhancement for
Arrays.sort(Object[]...)
Posted by "Tim Ellison (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HARMONY-636?page=comments#action_12419089 ]
Tim Ellison commented on HARMONY-636:
-------------------------------------
(continuation of previous comment)
java.lang.NullPointerException at tests.api.java.util.ArraysTest$ReversedIntegerComparator.compare(ArraysTest.java:28) at java.util.Arrays.mergeSort(Arrays.java:2297) at java.util.Arrays.mergeSort(Arrays.java:2309) at java.util.Arrays.mergeSort(Arrays.java:2309) at java.util.Arrays.mergeSort(Arrays.java:2310) at java.util.Arrays.sort(Arrays.java:2663) at java.util.Arrays.sort(Arrays.java:2652) at tests.api.java.util.ArraysTest.test_sort$Ljava_lang_ObjectIILjava_util_Comparator(ArraysTest.java:1257)
The test case source can be found here
http://svn.apache.org/viewvc/incubator/harmony/enhanced/classlib/trunk/modules/luni/src/test/java/tests/api/java/util/ArraysTest.java?view=markup
then search in there for "test_sort$Ljava_lang_ObjectIILjava_util_Comparator()"
Please can you take a look and figure out the cause.
> performance enhancement for Arrays.sort(Object[]...)
> ----------------------------------------------------
>
> Key: HARMONY-636
> URL: http://issues.apache.org/jira/browse/HARMONY-636
> Project: Harmony
> Type: Improvement
> Components: Classlib
> Reporter: Rustem Rafikov
> Assignee: Tim Ellison
> Priority: Minor
> Attachments: Arrays.objectsort.07042006.zip, Arrays_objectsort_patch.zip
>
> Dear All,
> I would like to suggest a patch improving performance of object's sorting algorithms.
> Actually the algorithm suggested uses different methods for sorting objects and strings:
> 1. Object's sorting uses adaptive merge-sort. It works much faster for nearly sorted arrays.
> 2. String's sorting algorithms are specially tuned for strings.
> Attached zip contains the patch itself and a micro benchmark.
> The micro-bench loads 100000 strings from aspell dictionary (you can find it in /usr/lib/aspell, for example: english-med-only), makes it sorted with different degree and then sort it.
> Even though this patch adds a lot of code lines instead of a little piece of original code, the test shows performance improvement as much as 45% for objects and 50% for strings.
> Thanks,
> Rustem
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
http://www.atlassian.com/software/jira
[jira] Commented: (HARMONY-636) performance enhancement for
Arrays.sort(Object[]...)
Posted by "Tim Ellison (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HARMONY-636?page=comments#action_12418950 ]
Tim Ellison commented on HARMONY-636:
-------------------------------------
Rustem,
Apologies for the delay -- there have been modification to the file you patched.
If you could send an updated patch that would help, otherwise I'll merge your changes in and evaluate in the next few days.
Thanks
Tim
> performance enhancement for Arrays.sort(Object[]...)
> ----------------------------------------------------
>
> Key: HARMONY-636
> URL: http://issues.apache.org/jira/browse/HARMONY-636
> Project: Harmony
> Type: Improvement
> Components: Classlib
> Reporter: Rustem Rafikov
> Assignee: Tim Ellison
> Priority: Minor
> Attachments: Arrays_objectsort_patch.zip
>
> Dear All,
> I would like to suggest a patch improving performance of object's sorting algorithms.
> Actually the algorithm suggested uses different methods for sorting objects and strings:
> 1. Object's sorting uses adaptive merge-sort. It works much faster for nearly sorted arrays.
> 2. String's sorting algorithms are specially tuned for strings.
> Attached zip contains the patch itself and a micro benchmark.
> The micro-bench loads 100000 strings from aspell dictionary (you can find it in /usr/lib/aspell, for example: english-med-only), makes it sorted with different degree and then sort it.
> Even though this patch adds a lot of code lines instead of a little piece of original code, the test shows performance improvement as much as 45% for objects and 50% for strings.
> Thanks,
> Rustem
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
http://www.atlassian.com/software/jira