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