crunch-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Gabriel Reid (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (CRUNCH-351) Improve performance of Shard#shard on large records
Date Mon, 24 Feb 2014 16:29:21 GMT

    [ https://issues.apache.org/jira/browse/CRUNCH-351?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13910448#comment-13910448
] 

Gabriel Reid commented on CRUNCH-351:
-------------------------------------

{quote}
I think I have missed something here. I guess there must be some optimization in MR for such
case. Could you explain more how this works?
{quote}

My thinking was that the best-case scenario is where the collection keys handled by each partition
would all be equal, with the thinking that the sorting of a collection of equal elements would
be the fastest possible. After a quick look at the quicksort used in Hadoop, it looks like
it suffers from the same issue that a lot of quicksort implementations have, in that sorting
a collection of equal elements is the worst-case scenario, i.e. O(n*n), so it looks like my
idea for this micro-optimization would likely slow things down more than speed them up.

{quote}
Is it identical to "count = ++count % numPartitions", given the partition function is "key
% numPartitions"?
{quote}

The partition function is actually "key.hashCode() % numPartitions", and my thinking behind
this was that multiplying the numPartitions by 3 (or something similar) it would make up for
a hashCode implementation that wasn't perfectly evenly distributed. However, I now see/realize
that the Integer hashCode is just the value of the integer, so this is also an uneccessary
micro-optimization.

> Improve performance of Shard#shard on large records
> ---------------------------------------------------
>
>                 Key: CRUNCH-351
>                 URL: https://issues.apache.org/jira/browse/CRUNCH-351
>             Project: Crunch
>          Issue Type: Improvement
>            Reporter: Chao Shi
>            Assignee: Chao Shi
>         Attachments: crunch-351-v2.patch, crunch-351.patch
>
>
>     This avoids sorting on the input data, which may be long and make
>     shuffle phase slow. The improvement is to sort on pseudo-random numbers.



--
This message was sent by Atlassian JIRA
(v6.1.5#6160)

Mime
View raw message