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 "Shevek (JIRA)" <ji...@apache.org> on 2009/04/23 13:53:47 UTC

[jira] Created: (HADOOP-5727) Faster, simpler id.hashCode() which does not allocate memory

Faster, simpler id.hashCode() which does not allocate memory
------------------------------------------------------------

                 Key: HADOOP-5727
                 URL: https://issues.apache.org/jira/browse/HADOOP-5727
             Project: Hadoop Core
          Issue Type: Improvement
          Components: mapred
            Reporter: Shevek


Integer.valueOf allocates memory if the integer is not in the object-cache, which is the vast majority of cases for the task id. It is possible to compute the hash code of an integer without going via the integer cache, and hence avoiding allocating memory.

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


[jira] Updated: (HADOOP-5727) Faster, simpler id.hashCode() which does not allocate memory

Posted by "Chris Douglas (JIRA)" <ji...@apache.org>.
     [ https://issues.apache.org/jira/browse/HADOOP-5727?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Chris Douglas updated HADOOP-5727:
----------------------------------

    Status: Open  (was: Patch Available)

> Faster, simpler id.hashCode() which does not allocate memory
> ------------------------------------------------------------
>
>                 Key: HADOOP-5727
>                 URL: https://issues.apache.org/jira/browse/HADOOP-5727
>             Project: Hadoop Core
>          Issue Type: Improvement
>          Components: mapred
>            Reporter: Shevek
>         Attachments: 00_id-noallocate.patch, 03_id-noallocate.patch
>
>
> Integer.valueOf allocates memory if the integer is not in the object-cache, which is the vast majority of cases for the task id. It is possible to compute the hash code of an integer without going via the integer cache, and hence avoiding allocating memory.

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


[jira] Updated: (HADOOP-5727) Faster, simpler id.hashCode() which does not allocate memory

Posted by "Shevek (JIRA)" <ji...@apache.org>.
     [ https://issues.apache.org/jira/browse/HADOOP-5727?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Shevek updated HADOOP-5727:
---------------------------

    Attachment: 03_id-noallocate.patch

Another attempt at the patch, running svn diff from a different root.

> Faster, simpler id.hashCode() which does not allocate memory
> ------------------------------------------------------------
>
>                 Key: HADOOP-5727
>                 URL: https://issues.apache.org/jira/browse/HADOOP-5727
>             Project: Hadoop Core
>          Issue Type: Improvement
>          Components: mapred
>            Reporter: Shevek
>         Attachments: 00_id-noallocate.patch, 03_id-noallocate.patch
>
>
> Integer.valueOf allocates memory if the integer is not in the object-cache, which is the vast majority of cases for the task id. It is possible to compute the hash code of an integer without going via the integer cache, and hence avoiding allocating memory.

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


[jira] Updated: (HADOOP-5727) Faster, simpler id.hashCode() which does not allocate memory

Posted by "Chris Douglas (JIRA)" <ji...@apache.org>.
     [ https://issues.apache.org/jira/browse/HADOOP-5727?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Chris Douglas updated HADOOP-5727:
----------------------------------

    Status: Patch Available  (was: Open)

> Faster, simpler id.hashCode() which does not allocate memory
> ------------------------------------------------------------
>
>                 Key: HADOOP-5727
>                 URL: https://issues.apache.org/jira/browse/HADOOP-5727
>             Project: Hadoop Core
>          Issue Type: Improvement
>          Components: mapred
>            Reporter: Shevek
>         Attachments: 00_id-noallocate.patch, 03_id-noallocate.patch
>
>
> Integer.valueOf allocates memory if the integer is not in the object-cache, which is the vast majority of cases for the task id. It is possible to compute the hash code of an integer without going via the integer cache, and hence avoiding allocating memory.

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


[jira] Commented: (HADOOP-5727) Faster, simpler id.hashCode() which does not allocate memory

Posted by "Chris Douglas (JIRA)" <ji...@apache.org>.
    [ https://issues.apache.org/jira/browse/HADOOP-5727?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12703976#action_12703976 ] 

Chris Douglas commented on HADOOP-5727:
---------------------------------------

As pointed out, the patch returns exactly what Integer::hashCode did, so the fix only removes the object alloc (which is probably also optimized out, but returning {{id}} is clearer). The supplemental hashing in HashMap is interesting; purely out of curiosity, do you happen to have any references for broader, J2SE changes?

bq. HashMap is a list-hash, so consecutive hashes followed by a hash collision does not cause a walk of a long linear hash chain.

Are you sure? The openjdk6 [source|http://hg.openjdk.java.net/jdk6/jdk6/jdk/file/a42d6999734b/src/share/classes/java/util/HashMap.java] appears to create/walk a list for collisions (addEntry/get)...

The current patch looks good, but the comments keep context for this particular fix. Would you mind removing them?

> Faster, simpler id.hashCode() which does not allocate memory
> ------------------------------------------------------------
>
>                 Key: HADOOP-5727
>                 URL: https://issues.apache.org/jira/browse/HADOOP-5727
>             Project: Hadoop Core
>          Issue Type: Improvement
>          Components: mapred
>            Reporter: Shevek
>            Assignee: Shevek
>         Attachments: 00_id-noallocate.patch, 03_id-noallocate.patch
>
>
> Integer.valueOf allocates memory if the integer is not in the object-cache, which is the vast majority of cases for the task id. It is possible to compute the hash code of an integer without going via the integer cache, and hence avoiding allocating memory.

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


[jira] Updated: (HADOOP-5727) Faster, simpler id.hashCode() which does not allocate memory

Posted by "Chris Douglas (JIRA)" <ji...@apache.org>.
     [ https://issues.apache.org/jira/browse/HADOOP-5727?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Chris Douglas updated HADOOP-5727:
----------------------------------

    Attachment: 5727-0.patch

Removed comments

> Faster, simpler id.hashCode() which does not allocate memory
> ------------------------------------------------------------
>
>                 Key: HADOOP-5727
>                 URL: https://issues.apache.org/jira/browse/HADOOP-5727
>             Project: Hadoop Core
>          Issue Type: Improvement
>          Components: mapred
>            Reporter: Shevek
>            Assignee: Shevek
>             Fix For: 0.21.0
>
>         Attachments: 00_id-noallocate.patch, 03_id-noallocate.patch, 5727-0.patch
>
>
> Integer.valueOf allocates memory if the integer is not in the object-cache, which is the vast majority of cases for the task id. It is possible to compute the hash code of an integer without going via the integer cache, and hence avoiding allocating memory.

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


[jira] Commented: (HADOOP-5727) Faster, simpler id.hashCode() which does not allocate memory

Posted by "Hudson (JIRA)" <ji...@apache.org>.
    [ https://issues.apache.org/jira/browse/HADOOP-5727?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12706150#action_12706150 ] 

Hudson commented on HADOOP-5727:
--------------------------------

Integrated in Hadoop-trunk #827 (See [http://hudson.zones.apache.org/hudson/job/Hadoop-trunk/827/])
    . Simplify hashcode for ID types. Contributed by Shevek


> Faster, simpler id.hashCode() which does not allocate memory
> ------------------------------------------------------------
>
>                 Key: HADOOP-5727
>                 URL: https://issues.apache.org/jira/browse/HADOOP-5727
>             Project: Hadoop Core
>          Issue Type: Improvement
>          Components: mapred
>            Reporter: Shevek
>            Assignee: Shevek
>             Fix For: 0.21.0
>
>         Attachments: 00_id-noallocate.patch, 03_id-noallocate.patch, 5727-0.patch
>
>
> Integer.valueOf allocates memory if the integer is not in the object-cache, which is the vast majority of cases for the task id. It is possible to compute the hash code of an integer without going via the integer cache, and hence avoiding allocating memory.

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


[jira] Updated: (HADOOP-5727) Faster, simpler id.hashCode() which does not allocate memory

Posted by "Shevek (JIRA)" <ji...@apache.org>.
     [ https://issues.apache.org/jira/browse/HADOOP-5727?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Shevek updated HADOOP-5727:
---------------------------

    Status: Patch Available  (was: Open)

> Faster, simpler id.hashCode() which does not allocate memory
> ------------------------------------------------------------
>
>                 Key: HADOOP-5727
>                 URL: https://issues.apache.org/jira/browse/HADOOP-5727
>             Project: Hadoop Core
>          Issue Type: Improvement
>          Components: mapred
>            Reporter: Shevek
>         Attachments: 00_id-noallocate.patch
>
>
> Integer.valueOf allocates memory if the integer is not in the object-cache, which is the vast majority of cases for the task id. It is possible to compute the hash code of an integer without going via the integer cache, and hence avoiding allocating memory.

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


[jira] Commented: (HADOOP-5727) Faster, simpler id.hashCode() which does not allocate memory

Posted by "Shevek (JIRA)" <ji...@apache.org>.
    [ https://issues.apache.org/jira/browse/HADOOP-5727?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12703685#action_12703685 ] 

Shevek commented on HADOOP-5727:
--------------------------------

bq. This is a good point. It is not necessary to create an object. However, returning the id directly might not lead to a good hash code. We may have to add a hash code implementation. 

This discussion was rampant in the very early days of Java: Consecutive objects, including String, etc, have always had consecutive hash codes. In fact, it does not really matter because:

* HashMap is a list-hash, so consecutive hashes followed by a hash collision does not cause a walk of a long linear hash chain. The length of the chain walked because of a collision will only be 2.
* HashMap implements a supplementary transformation on hash codes (one of the Mersenne Twisters?), so it is not necessary to ensure distribution or uniformity of the basic hash codes. In fact, HashMap probably does better than the application code would do.
* Other Map strategies, such as R-B tree, do not use hashCode().
* In general, the issue of consecutive objects, especially numbers, generating consecutive hash codes is accepted and understood by library authors who require more uniform distribution of hash codes, and account is taken at that point.
* The J2SE internally uses this strategy, and they spend a lot more time thinking about these problems than we do.

I therefore submit that this patch should be applied as-is.

> Faster, simpler id.hashCode() which does not allocate memory
> ------------------------------------------------------------
>
>                 Key: HADOOP-5727
>                 URL: https://issues.apache.org/jira/browse/HADOOP-5727
>             Project: Hadoop Core
>          Issue Type: Improvement
>          Components: mapred
>            Reporter: Shevek
>         Attachments: 00_id-noallocate.patch, 03_id-noallocate.patch
>
>
> Integer.valueOf allocates memory if the integer is not in the object-cache, which is the vast majority of cases for the task id. It is possible to compute the hash code of an integer without going via the integer cache, and hence avoiding allocating memory.

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


[jira] Commented: (HADOOP-5727) Faster, simpler id.hashCode() which does not allocate memory

Posted by "Hadoop QA (JIRA)" <ji...@apache.org>.
    [ https://issues.apache.org/jira/browse/HADOOP-5727?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12702671#action_12702671 ] 

Hadoop QA commented on HADOOP-5727:
-----------------------------------

-1 overall.  Here are the results of testing the latest attachment 
  http://issues.apache.org/jira/secure/attachment/12406213/00_id-noallocate.patch
  against trunk revision 768376.

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

    -1 tests included.  The patch doesn't appear to include any new or modified tests.
                        Please justify why no tests are needed for this patch.

    -1 patch.  The patch command could not apply the patch.

Console output: http://hudson.zones.apache.org/hudson/job/Hadoop-Patch-vesta.apache.org/240/console

This message is automatically generated.

> Faster, simpler id.hashCode() which does not allocate memory
> ------------------------------------------------------------
>
>                 Key: HADOOP-5727
>                 URL: https://issues.apache.org/jira/browse/HADOOP-5727
>             Project: Hadoop Core
>          Issue Type: Improvement
>          Components: mapred
>            Reporter: Shevek
>         Attachments: 00_id-noallocate.patch
>
>
> Integer.valueOf allocates memory if the integer is not in the object-cache, which is the vast majority of cases for the task id. It is possible to compute the hash code of an integer without going via the integer cache, and hence avoiding allocating memory.

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


[jira] Assigned: (HADOOP-5727) Faster, simpler id.hashCode() which does not allocate memory

Posted by "Chris Douglas (JIRA)" <ji...@apache.org>.
     [ https://issues.apache.org/jira/browse/HADOOP-5727?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Chris Douglas reassigned HADOOP-5727:
-------------------------------------

    Assignee: Shevek

> Faster, simpler id.hashCode() which does not allocate memory
> ------------------------------------------------------------
>
>                 Key: HADOOP-5727
>                 URL: https://issues.apache.org/jira/browse/HADOOP-5727
>             Project: Hadoop Core
>          Issue Type: Improvement
>          Components: mapred
>            Reporter: Shevek
>            Assignee: Shevek
>         Attachments: 00_id-noallocate.patch, 03_id-noallocate.patch
>
>
> Integer.valueOf allocates memory if the integer is not in the object-cache, which is the vast majority of cases for the task id. It is possible to compute the hash code of an integer without going via the integer cache, and hence avoiding allocating memory.

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


[jira] Commented: (HADOOP-5727) Faster, simpler id.hashCode() which does not allocate memory

Posted by "Hadoop QA (JIRA)" <ji...@apache.org>.
    [ https://issues.apache.org/jira/browse/HADOOP-5727?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12704622#action_12704622 ] 

Hadoop QA commented on HADOOP-5727:
-----------------------------------

-1 overall.  Here are the results of testing the latest attachment 
  http://issues.apache.org/jira/secure/attachment/12406649/03_id-noallocate.patch
  against trunk revision 770044.

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

    -1 tests included.  The patch doesn't appear to include any new or modified tests.
                        Please justify why no tests are needed for this patch.

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

    +1 javac.  The applied patch does not increase the total number of javac compiler warnings.

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

    +1 Eclipse classpath. The patch retains Eclipse classpath integrity.

    +1 release audit.  The applied patch does not increase the total number of release audit warnings.

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

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

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

This message is automatically generated.

> Faster, simpler id.hashCode() which does not allocate memory
> ------------------------------------------------------------
>
>                 Key: HADOOP-5727
>                 URL: https://issues.apache.org/jira/browse/HADOOP-5727
>             Project: Hadoop Core
>          Issue Type: Improvement
>          Components: mapred
>            Reporter: Shevek
>            Assignee: Shevek
>         Attachments: 00_id-noallocate.patch, 03_id-noallocate.patch
>
>
> Integer.valueOf allocates memory if the integer is not in the object-cache, which is the vast majority of cases for the task id. It is possible to compute the hash code of an integer without going via the integer cache, and hence avoiding allocating memory.

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


[jira] Updated: (HADOOP-5727) Faster, simpler id.hashCode() which does not allocate memory

Posted by "Chris Douglas (JIRA)" <ji...@apache.org>.
     [ https://issues.apache.org/jira/browse/HADOOP-5727?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Chris Douglas updated HADOOP-5727:
----------------------------------

       Resolution: Fixed
    Fix Version/s: 0.21.0
     Hadoop Flags: [Reviewed]
           Status: Resolved  (was: Patch Available)

I committed this. Thanks, Shevek

> Faster, simpler id.hashCode() which does not allocate memory
> ------------------------------------------------------------
>
>                 Key: HADOOP-5727
>                 URL: https://issues.apache.org/jira/browse/HADOOP-5727
>             Project: Hadoop Core
>          Issue Type: Improvement
>          Components: mapred
>            Reporter: Shevek
>            Assignee: Shevek
>             Fix For: 0.21.0
>
>         Attachments: 00_id-noallocate.patch, 03_id-noallocate.patch, 5727-0.patch
>
>
> Integer.valueOf allocates memory if the integer is not in the object-cache, which is the vast majority of cases for the task id. It is possible to compute the hash code of an integer without going via the integer cache, and hence avoiding allocating memory.

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


[jira] Updated: (HADOOP-5727) Faster, simpler id.hashCode() which does not allocate memory

Posted by "Shevek (JIRA)" <ji...@apache.org>.
     [ https://issues.apache.org/jira/browse/HADOOP-5727?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Shevek updated HADOOP-5727:
---------------------------

    Attachment: 00_id-noallocate.patch

aha, I found the patch upload button - it's not the one marked "submit patch"!

> Faster, simpler id.hashCode() which does not allocate memory
> ------------------------------------------------------------
>
>                 Key: HADOOP-5727
>                 URL: https://issues.apache.org/jira/browse/HADOOP-5727
>             Project: Hadoop Core
>          Issue Type: Improvement
>          Components: mapred
>            Reporter: Shevek
>         Attachments: 00_id-noallocate.patch
>
>
> Integer.valueOf allocates memory if the integer is not in the object-cache, which is the vast majority of cases for the task id. It is possible to compute the hash code of an integer without going via the integer cache, and hence avoiding allocating memory.

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.