You are viewing a plain text version of this content. The canonical link for it is here.
Posted to common-dev@hadoop.apache.org by "Benjamin Reed (JIRA)" <ji...@apache.org> on 2006/06/07 23:41:29 UTC
[jira] Created: (HADOOP-287) Speed up SequenceFile sort with memory
reduction
Speed up SequenceFile sort with memory reduction
------------------------------------------------
Key: HADOOP-287
URL: http://issues.apache.org/jira/browse/HADOOP-287
Project: Hadoop
Type: Improvement
Components: io
Versions: 0.3.2
Reporter: Benjamin Reed
Attachments: zoom-sort.patch
I replaced the merge sort with a quick sort and it yielded approx 30% improvement in sort time. It also reduced the memory requirement for sorting because the sort is done in place.
--
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: (HADOOP-287) Speed up SequenceFile sort with
memory reduction
Posted by "Doug Cutting (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HADOOP-287?page=comments#action_12415223 ]
Doug Cutting commented on HADOOP-287:
-------------------------------------
This looks good, but it doesn't pass unit tests any longer. In particular, the following fails for me:
ant -Dtestcase=TestSequenceFile test
This results in something like the following for me:
java.lang.RuntimeException: wrong key at 2838
at org.apache.hadoop.io.TestSequenceFile.checkSort(TestSequenceFile.java:146)
at org.apache.hadoop.io.TestSequenceFile.testSequenceFile(TestSequenceFile.java:53)
> Speed up SequenceFile sort with memory reduction
> ------------------------------------------------
>
> Key: HADOOP-287
> URL: http://issues.apache.org/jira/browse/HADOOP-287
> Project: Hadoop
> Type: Improvement
> Components: io
> Versions: 0.3.2
> Reporter: Benjamin Reed
> Attachments: zoom-sort.patch
>
> I replaced the merge sort with a quick sort and it yielded approx 30% improvement in sort time. It also reduced the memory requirement for sorting because the sort is done in place.
--
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: (HADOOP-287) Speed up SequenceFile sort with
memory reduction
Posted by "Andrzej Bialecki (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HADOOP-287?page=comments#action_12423818 ]
Andrzej Bialecki commented on HADOOP-287:
------------------------------------------
What is the status of this patch? I'm running with relatively slow disks, and I could sure use a 30% improvement in sorting time ... ;)
> Speed up SequenceFile sort with memory reduction
> ------------------------------------------------
>
> Key: HADOOP-287
> URL: http://issues.apache.org/jira/browse/HADOOP-287
> Project: Hadoop
> Issue Type: Improvement
> Components: io
> Affects Versions: 0.3.2
> Reporter: Benjamin Reed
> Assigned To: Doug Cutting
> Attachments: zoom-sort.patch, zoom-sort.patch
>
>
> I replaced the merge sort with a quick sort and it yielded approx 30% improvement in sort time. It also reduced the memory requirement for sorting because the sort is done in place.
--
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: (HADOOP-287) Speed up SequenceFile sort with memory
reduction
Posted by "Benjamin Reed (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HADOOP-287?page=all ]
Benjamin Reed updated HADOOP-287:
---------------------------------
Attachment: s.patch
> Speed up SequenceFile sort with memory reduction
> ------------------------------------------------
>
> Key: HADOOP-287
> URL: http://issues.apache.org/jira/browse/HADOOP-287
> Project: Hadoop
> Issue Type: Improvement
> Components: io
> Affects Versions: 0.3.2
> Reporter: Benjamin Reed
> Assigned To: Doug Cutting
> Attachments: s.patch, zoom-sort.patch, zoom-sort.patch
>
>
> I replaced the merge sort with a quick sort and it yielded approx 30% improvement in sort time. It also reduced the memory requirement for sorting because the sort is done in place.
--
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: (HADOOP-287) Speed up SequenceFile sort with
memory reduction
Posted by "Doug Cutting (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HADOOP-287?page=all ]
Doug Cutting resolved HADOOP-287.
---------------------------------
Fix Version/s: 0.5.0
Resolution: Fixed
I just committed this, with one change. Your patch mistakenly removed the 'in' field.
Thanks, Ben!
> Speed up SequenceFile sort with memory reduction
> ------------------------------------------------
>
> Key: HADOOP-287
> URL: http://issues.apache.org/jira/browse/HADOOP-287
> Project: Hadoop
> Issue Type: Improvement
> Components: io
> Affects Versions: 0.3.2
> Reporter: Benjamin Reed
> Assigned To: Doug Cutting
> Fix For: 0.5.0
>
> Attachments: s.patch, zoom-sort.patch, zoom-sort.patch
>
>
> I replaced the merge sort with a quick sort and it yielded approx 30% improvement in sort time. It also reduced the memory requirement for sorting because the sort is done in place.
--
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] Reopened: (HADOOP-287) Speed up SequenceFile sort with
memory reduction
Posted by "Doug Cutting (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HADOOP-287?page=all ]
Doug Cutting reopened HADOOP-287:
---------------------------------
I just reverted this.
> Speed up SequenceFile sort with memory reduction
> ------------------------------------------------
>
> Key: HADOOP-287
> URL: http://issues.apache.org/jira/browse/HADOOP-287
> Project: Hadoop
> Issue Type: Improvement
> Components: io
> Affects Versions: 0.3.2
> Reporter: Benjamin Reed
> Assigned To: Doug Cutting
> Fix For: 0.5.0
>
> Attachments: s.patch, zoom-sort.patch, zoom-sort.patch
>
>
> I replaced the merge sort with a quick sort and it yielded approx 30% improvement in sort time. It also reduced the memory requirement for sorting because the sort is done in place.
--
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: (HADOOP-287) Speed up SequenceFile sort with
memory reduction
Posted by "Benjamin Reed (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HADOOP-287?page=comments#action_12442138 ]
Benjamin Reed commented on HADOOP-287:
--------------------------------------
[[ Old comment, sent by email on Thu, 8 Jun 2006 07:32:09 -0700 ]]
Duh! Sorry Doug. Stupid error. I didn't realize you had unit tests.
I've fixed it. I'll run the tests now.
ben
> Speed up SequenceFile sort with memory reduction
> ------------------------------------------------
>
> Key: HADOOP-287
> URL: http://issues.apache.org/jira/browse/HADOOP-287
> Project: Hadoop
> Issue Type: Improvement
> Components: io
> Affects Versions: 0.3.2
> Reporter: Benjamin Reed
> Assigned To: Doug Cutting
> Attachments: s.patch, zoom-sort.patch, zoom-sort.patch
>
>
> I replaced the merge sort with a quick sort and it yielded approx 30% improvement in sort time. It also reduced the memory requirement for sorting because the sort is done in place.
--
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: (HADOOP-287) Speed up SequenceFile sort with memory
reduction
Posted by "Benjamin Reed (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HADOOP-287?page=all ]
Benjamin Reed updated HADOOP-287:
---------------------------------
Attachment: zoom-sort.patch
> Speed up SequenceFile sort with memory reduction
> ------------------------------------------------
>
> Key: HADOOP-287
> URL: http://issues.apache.org/jira/browse/HADOOP-287
> Project: Hadoop
> Type: Improvement
> Components: io
> Versions: 0.3.2
> Reporter: Benjamin Reed
> Attachments: zoom-sort.patch
>
> I replaced the merge sort with a quick sort and it yielded approx 30% improvement in sort time. It also reduced the memory requirement for sorting because the sort is done in place.
--
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: (HADOOP-287) Speed up SequenceFile sort with
memory reduction
Posted by "Doug Cutting (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HADOOP-287?page=all ]
Doug Cutting reassigned HADOOP-287:
-----------------------------------
Assign To: Doug Cutting
> Speed up SequenceFile sort with memory reduction
> ------------------------------------------------
>
> Key: HADOOP-287
> URL: http://issues.apache.org/jira/browse/HADOOP-287
> Project: Hadoop
> Type: Improvement
> Components: io
> Versions: 0.3.2
> Reporter: Benjamin Reed
> Assignee: Doug Cutting
> Attachments: zoom-sort.patch, zoom-sort.patch
>
> I replaced the merge sort with a quick sort and it yielded approx 30% improvement in sort time. It also reduced the memory requirement for sorting because the sort is done in place.
--
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: (HADOOP-287) Speed up SequenceFile sort with
memory reduction
Posted by "Owen O'Malley (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HADOOP-287?page=comments#action_12424941 ]
Owen O'Malley commented on HADOOP-287:
--------------------------------------
This patch broke the build. In particular, the org.apache.hadoop.mapred.TestMiniMRLocalFS no longer finishes. When the job becomes stuck, the reduces are still running. I assume they are stuck in an infinite loop somewhere.
> Speed up SequenceFile sort with memory reduction
> ------------------------------------------------
>
> Key: HADOOP-287
> URL: http://issues.apache.org/jira/browse/HADOOP-287
> Project: Hadoop
> Issue Type: Improvement
> Components: io
> Affects Versions: 0.3.2
> Reporter: Benjamin Reed
> Assigned To: Doug Cutting
> Fix For: 0.5.0
>
> Attachments: s.patch, zoom-sort.patch, zoom-sort.patch
>
>
> I replaced the merge sort with a quick sort and it yielded approx 30% improvement in sort time. It also reduced the memory requirement for sorting because the sort is done in place.
--
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: (HADOOP-287) Speed up SequenceFile sort with
memory reduction
Posted by "Doug Cutting (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HADOOP-287?page=comments#action_12415425 ]
Doug Cutting commented on HADOOP-287:
-------------------------------------
This works for me now. Thanks! I'll commit it once we get 0.3.2 out the door.
> Speed up SequenceFile sort with memory reduction
> ------------------------------------------------
>
> Key: HADOOP-287
> URL: http://issues.apache.org/jira/browse/HADOOP-287
> Project: Hadoop
> Type: Improvement
> Components: io
> Versions: 0.3.2
> Reporter: Benjamin Reed
> Attachments: zoom-sort.patch, zoom-sort.patch
>
> I replaced the merge sort with a quick sort and it yielded approx 30% improvement in sort time. It also reduced the memory requirement for sorting because the sort is done in place.
--
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: (HADOOP-287) Speed up SequenceFile sort with memory
reduction
Posted by "Benjamin Reed (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HADOOP-287?page=all ]
Benjamin Reed updated HADOOP-287:
---------------------------------
Attachment: zoom-sort.patch
My previous patch had two minor typos that gave incorrect results. This patch should work.
> Speed up SequenceFile sort with memory reduction
> ------------------------------------------------
>
> Key: HADOOP-287
> URL: http://issues.apache.org/jira/browse/HADOOP-287
> Project: Hadoop
> Type: Improvement
> Components: io
> Versions: 0.3.2
> Reporter: Benjamin Reed
> Attachments: zoom-sort.patch, zoom-sort.patch
>
> I replaced the merge sort with a quick sort and it yielded approx 30% improvement in sort time. It also reduced the memory requirement for sorting because the sort is done in place.
--
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: (HADOOP-287) Speed up SequenceFile sort with
memory reduction
Posted by "Benjamin Reed (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HADOOP-287?page=comments#action_12423847 ]
Benjamin Reed commented on HADOOP-287:
--------------------------------------
I have improved it a bit more. It now is guaranteed to only take logN stack space, and I eaked out a bit more performance. Unfortunately, the 30% improvement is for the in-memory sort. For your slow disks you need my other patch which reduces the number of times the data hits the disk. Unfortunately, that patch doesn't apply anymore. I have a newer version that removes one more full disk hit, so that should work even better. I'll try to create a patch for it today. (Unrelated changes break my patches and take a long time to reconcile...
> Speed up SequenceFile sort with memory reduction
> ------------------------------------------------
>
> Key: HADOOP-287
> URL: http://issues.apache.org/jira/browse/HADOOP-287
> Project: Hadoop
> Issue Type: Improvement
> Components: io
> Affects Versions: 0.3.2
> Reporter: Benjamin Reed
> Assigned To: Doug Cutting
> Attachments: s.patch, zoom-sort.patch, zoom-sort.patch
>
>
> I replaced the merge sort with a quick sort and it yielded approx 30% improvement in sort time. It also reduced the memory requirement for sorting because the sort is done in place.
--
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: (HADOOP-287) Speed up SequenceFile sort with
memory reduction
Posted by "Johan Oskarson (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HADOOP-287?page=comments#action_12433179 ]
Johan Oskarson commented on HADOOP-287:
---------------------------------------
Benjamin:
Would it be possible to look into what broke in the latest patch?
> Speed up SequenceFile sort with memory reduction
> ------------------------------------------------
>
> Key: HADOOP-287
> URL: http://issues.apache.org/jira/browse/HADOOP-287
> Project: Hadoop
> Issue Type: Improvement
> Components: io
> Affects Versions: 0.3.2
> Reporter: Benjamin Reed
> Assigned To: Doug Cutting
> Fix For: 0.6.0
>
> Attachments: s.patch, zoom-sort.patch, zoom-sort.patch
>
>
> I replaced the merge sort with a quick sort and it yielded approx 30% improvement in sort time. It also reduced the memory requirement for sorting because the sort is done in place.
--
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