[#HADOOP-3308] Improve QuickSort by excluding values eq the pivot from the partition

Hadoop Common

Improve QuickSort by excluding values eq the pivot from the partition

Created: 24/Apr/08 08:43 PM Updated: 22/Aug/08 07:50 PM

Component/s:

None

Affects Version/s:

None

Fix Version/s:

0.18.0

Time Tracking:

Not Specified

File Attachments:

File Name	Date Attached	Attached By	Size
3308-0.patch	2008-04-24 08:47 PM	Chris Douglas	5 kB
3308-1.patch	2008-04-24 11:16 PM	Chris Douglas	5 kB
3308-2.patch	2008-04-25 01:19 AM	Chris Douglas	6 kB

Hadoop Flags:	Reviewed
Resolution Date:	25/Apr/08 11:04 PM

Description

« Hide

The current implementation of QuickSort naively partitions on either side of the pivot. We can improve this by partitioning on either side of the set of values equal to the pivot. This assumes that comparing keys is expensive compared to swaps and index comparisons (which it certainly is in MapTask, and should be in general).

All

Comments

Work Log

Change History

Subversion Commits

Sort Order:

[ Permlink | « Hide ]

Hadoop QA added a comment - 24/Apr/08 10:12 PM

+1 overall. Here are the results of testing the latest attachment
http://issues.apache.org/jira/secure/attachment/12380870/3308-0.patch
against trunk revision 645773.

@author +1. The patch does not contain any @author tags.

tests included +1. The patch appears to include 3 new or modified tests.

javadoc +1. The javadoc tool did not generate any warning messages.

javac +1. The applied patch does not generate any new javac compiler warnings.

release audit +1. The applied patch does not generate any new release audit warnings.

findbugs +1. The patch does not introduce any new Findbugs warnings.

core tests +1. The patch passed core unit tests.

contrib tests +1. The patch passed contrib unit tests.

Test results: http://hudson.zones.apache.org/hudson/job/Hadoop-Patch/2318/testReport/
Findbugs warnings: http://hudson.zones.apache.org/hudson/job/Hadoop-Patch/2318/artifact/trunk/build/test/findbugs/newPatchFindbugsWarnings.html
Checkstyle results: http://hudson.zones.apache.org/hudson/job/Hadoop-Patch/2318/artifact/trunk/build/test/checkstyle-errors.html
Console output: http://hudson.zones.apache.org/hudson/job/Hadoop-Patch/2318/console

This message is automatically generated.

[ Permlink | « Hide ]

Chris Douglas added a comment - 24/Apr/08 11:17 PM

The code that recurs on the smaller of the partitions didn't; this fixes it.

[ Permlink | « Hide ]

Hadoop QA added a comment - 25/Apr/08 12:40 AM

+1 overall. Here are the results of testing the latest attachment
http://issues.apache.org/jira/secure/attachment/12380881/3308-1.patch
against trunk revision 645773.

@author +1. The patch does not contain any @author tags.

tests included +1. The patch appears to include 3 new or modified tests.

javadoc +1. The javadoc tool did not generate any warning messages.

javac +1. The applied patch does not generate any new javac compiler warnings.

release audit +1. The applied patch does not generate any new release audit warnings.

findbugs +1. The patch does not introduce any new Findbugs warnings.

core tests +1. The patch passed core unit tests.

contrib tests +1. The patch passed contrib unit tests.

Test results: http://hudson.zones.apache.org/hudson/job/Hadoop-Patch/2319/testReport/
Findbugs warnings: http://hudson.zones.apache.org/hudson/job/Hadoop-Patch/2319/artifact/trunk/build/test/findbugs/newPatchFindbugsWarnings.html
Checkstyle results: http://hudson.zones.apache.org/hudson/job/Hadoop-Patch/2319/artifact/trunk/build/test/checkstyle-errors.html
Console output: http://hudson.zones.apache.org/hudson/job/Hadoop-Patch/2319/console

This message is automatically generated.

[ Permlink | « Hide ]

Tsz Wo (Nicholas), SZE added a comment - 25/Apr/08 01:14 AM

Since IndexedSortable s and Progressable rep are constants, it would be good to store them in instance variables. If the QuickSort object is shared (i.e. race condition), put everything in an inner-class.

Also, making the recursion class final may help.

[ Permlink | « Hide ]

Chris Douglas added a comment - 25/Apr/08 01:19 AM

Made the class final per Nicholas's recommendation. Instead of instance vars, it should be sufficient to make them final in the call to sort. Also added an additional test case to test the new code more thoroughly.