ReduceTask::closestPowerOf2 is inefficient

• Key: HADOOP-3398
• Type: Improvement
• Status: Closed
• Resolution: Fixed
• Priority: Trivial
• Assignee: Chris Douglas
• Reporter: Chris Douglas
• Fix Version/s: 0.18.0

Description

ReduceTask computes the "closest power of 2" using loops

private static int getClosestPowerOf2(int value) {
  int power = 0;
  int approx = 1;
  while (approx < value) {
    ++power;
    approx = (approx << 1);
  }
  if ((value - (approx >> 1)) < (approx - value)) {
    --power;
  }
  return power;
}

This could be improved.

Comments

[Chris Douglas]

This returns the same results as the original, save for values <= 0, which neither support.

[Hadoop QA]

-1 overall. Here are the results of testing the latest attachment
http://issues.apache.org/jira/secure/attachment/12382141/3398-0.patch
against trunk revision 656852.

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

This message is automatically generated.

[Hadoop QA]

-1 overall. Here are the results of testing the latest attachment
http://issues.apache.org/jira/secure/attachment/12382146/3398-1.patch
against trunk revision 656852.

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

This message is automatically generated.

[Amar Kamat]

Code looks fine. The values are same for both the implementations. Some comments as to what is done could be useful. I compared the two implementations

input	num-iterations	before (milli)	after (milli)
10000	1000000	642	19
5000	1000000	78	9
2500	1000000	74	5
1000	1000000	69	3
500	1000000	51	1
300	1000000	49	1

Assuming that the map runtime can vary from 300sec to 10,000 secs and the maximum number of times getClosestPowerOf2() will be invoked is 1,000,000.

[Chris Douglas]

Thanks for the review and benchmarks. It's obvious that this isn't an important optimization (hence "trivial"), but it was a fun problem.

Added some documentation and an explicit check for value leq 0 to make its behavior clearer.

[Tsz Wo (Nicholas), SZE]

if (value < 0), why not return -getClosestPowerOf2(-value-1)?

[Tsz Wo (Nicholas), SZE]

Mathematically, we should throw an exception (Math.log() returns NaN for -ve numbers and -infinity for 0) when value <= 0 since logarithm is undefined.

[Hadoop QA]

-1 overall. Here are the results of testing the latest attachment
http://issues.apache.org/jira/secure/attachment/12382208/3398-2.patch
against trunk revision 656939.

+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 release audit. The applied patch does not increase the total number of release audit warnings.

-1 core tests. The patch failed core unit tests.

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

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

This message is automatically generated.

[Amar Kamat]

Mathematically, we should throw an exception (Math.log() returns NaN for -ve numbers and -infinity for 0) when value <= 0 since logarithm is undefined.

+1.

[Chris Douglas]

Alright, alright, you pedants.

[Tsz Wo (Nicholas), SZE]

+1 3398-3.patch looks good

[Chris Douglas]

I just committed this.

[Hadoop QA]

-1 overall. Here are the results of testing the latest attachment
http://issues.apache.org/jira/secure/attachment/12382331/3398-3.patch
against trunk revision 657965.

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

This message is automatically generated.

[Hudson]

Integrated in Hadoop-trunk #499 (See http://hudson.zones.apache.org/hudson/job/Hadoop-trunk/499/)