hadoop-common-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Hadoop QA (JIRA)" <j...@apache.org>
Subject [jira] Commented: (HADOOP-5705) Improved tries in TotalOrderPartitioner to eliminate large leaf nodes.
Date Thu, 23 Apr 2009 00:44:47 GMT

    [ https://issues.apache.org/jira/browse/HADOOP-5705?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12701767#action_12701767
] 

Hadoop QA commented on HADOOP-5705:
-----------------------------------

-1 overall.  Here are the results of testing the latest attachment 
  http://issues.apache.org/jira/secure/attachment/12405833/hadoop-5705.patch
  against trunk revision 767643.

    +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/228/testReport/
Findbugs warnings: http://hudson.zones.apache.org/hudson/job/Hadoop-Patch-vesta.apache.org/228/artifact/trunk/build/test/findbugs/newPatchFindbugsWarnings.html
Checkstyle results: http://hudson.zones.apache.org/hudson/job/Hadoop-Patch-vesta.apache.org/228/artifact/trunk/build/test/checkstyle-errors.html
Console output: http://hudson.zones.apache.org/hudson/job/Hadoop-Patch-vesta.apache.org/228/console

This message is automatically generated.

> Improved tries in TotalOrderPartitioner to eliminate large leaf nodes.
> ----------------------------------------------------------------------
>
>                 Key: HADOOP-5705
>                 URL: https://issues.apache.org/jira/browse/HADOOP-5705
>             Project: Hadoop Core
>          Issue Type: Improvement
>          Components: mapred
>    Affects Versions: 0.19.1
>            Reporter: Dick King
>            Assignee: Dick King
>         Attachments: hadoop-5705.patch
>
>
> With the old technology, if a particular node in the trie has many children that contain
no split points, TotalOrderPartitioner creates a separate empty leaf node for each one.  This
takes a lot of space, which in turn limits the depth to which we can grow these trees to avoid
making too many sparse nodes, so there is a parameter that defaults to 2 to control the depth.
 With this patch, I can guarantee that each split point will create only three trie nodes
in the trie: an empty one, a leaf that contains only one split point, and the internal nodes
as needed, for a total space of perhaps 50-200 bytes per split point, even if the entire trie
is elaborated.  There are pathological cases that can cause a recursion overflow during creation,
so i have set the default tree max depth to 200, but I expect almost all tries to be fully
elaborated, which means in turn that each byte of the sought key gets touched at most twice.

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


Mime
View raw message