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 
  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

    +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.

View raw message