2
\$\begingroup\$

I wrote a piece of code to benchmark the detection of perfect numbers up to 10000. The original code is here, in C:

#include <stdio.h>

int isPerfectNumber(int num) {
    if (num == 1) { return 0; }

    int i, c = num - 1;
    for (i = 2; i <= num / 2; ++i) {
        if (num % i == 0) { c -= i; }
    }

    return c == 0;
}

int main(int argc, char* argv[]) {
    int i;
    for (i = 0; i < 10000; ++i) {
        if (isPerfectNumber(i)) {
            printf("%d\n", i);
        }
    }
    return 0;
}

I then wrote the same code in a number of different languages (C, C#, Java, V8 Javascript, Python and Go).

After benchmarking, I got the following results:

  • C: 92.8 ms
  • C#: 97.9 ms
  • Go: 208.85 ms
  • Java: 130.65 ms
  • V8 Javascript: 279.15 ms
  • Python: 1126.35 ms

I expected pretty much exactly this pattern of fastest to slowest, except for Go. Why is my Go implementation so slow? I admit I know very little about Go but I was under the impression that since it is a compiled language it is likely to be as fast as at least C# was.

Here is my Go implementation:

package main

import "fmt"

func main() {
    for i := 0; i < 10000; i++ {
        if (isPerfectNumber(i)) {
            fmt.Println(i)
        }
    }
}

func isPerfectNumber(num int) bool {
    if num == 1 { return false }

    c := num - 1
    for i := 2; i <= num / 2; i++ {
        if num % i == 0 { c -= i }
    }

    return c == 0
}

Have I just mucked something up or are the results I am seeing accurate?

FYI: I benchmark by running the code 10 times without timing it, then running another 20 times and take the average of those 20 tests.

\$\endgroup\$
  • 1
    \$\begingroup\$ Perhaps the best way to determine what is happening is to run a profiler such as github.com/pkg/profile because looking at the code can only give a BigO analysis. Being Garbage Collected, that's always a possible cause of latency. Compiler flags, debug information, or calculating the constant num/2 each time through the loop are other potential culprits (though maybe the compiler inlines num/2). \$\endgroup\$ – ben rudgers Feb 13 '17 at 4:16
3
\$\begingroup\$

I've bumped the number to 100000 and profiled. It seems that modulo operation is the most expensive here:

ROUTINE ======================== main.isPerfectNumber in /tmp/so/main.go
    31.72s     31.72s (flat, cum)   100% of Total
         .          .     19:   if num == 1 {
         .          .     20:       return false
         .          .     21:   }
         .          .     22:
         .          .     23:   c := num - 1
     2.35s      2.35s     24:   for i := 2; i <= num/2; i++ {
    29.37s     29.37s     25:       if num%i == 0 {
         .          .     26:           c -= i
         .          .     27:       }
         .          .     28:   }
         .          .     29:
         .          .     30:   return c == 0

It seems that C compilers are able to optimize modulo here, while the Go compiler cannot. I'd suggest opening an issue about it on the Go bug tracker. If C can do that, Go should as well.

\$\endgroup\$
3
\$\begingroup\$

I took your code and played with it a bit... and realized a couple of things:

  1. You're not really looking for a code review, but trying to find out why the Go code is slower than expected.
  2. There's no answer that will satisfy you any more than Ainar-G's answer: https://codereview.stackexchange.com/a/155256/31503 .... but, this site is Code Review, and I figured I would review the code (even though that's not what you're specifically asking for).

First up, while your code is not horrible, there are some improvements to be made:

  • Use multi-line statement blocks. Code like :

    if num == 1 { return false }
    

    should be:

    if num == 1 {
        return false
    }
    
  • Use better variable name for c. I realize that you're copying the code from a C program, but that's a simple variable to rename to something like difference. I found the c particularly hard to figure out, it's not obvious what the c is short for, or how the c is even used. I had to walk through the code to identify its purpose. (I am sure that you'll think that it's obvious, but remember you've been looking at the code for a lot longer).

  • input validation should return false for all values less than 2, not just 1. Your check if num == 1 should be if num <= 1

Now, about that algorithm... again, I realize that you are comparing the same algorithm in different languages, but there are some basic optimizations you can do, some more significant than others:

  • use num >> 1 instead of num / 2 for the loop constraint check (0.4% saving)
  • compute num/2 just once. No need to compute it in each loop. This saved 0.2% of the time for me.
  • abandon the loop when c goes negative (i.e. the factors add up to more than the input value) (0.6% saving)
  • use division&multiplication instead of modulo (thanks Ainar-G).. i.e. instead of num%i == 0 use q := num / i; if q * i == num .... - very little 0.0%...

None of these optimizations will make enough difference in your evaluation of Go performance relative to other languages, though.

The bigger optimizations are to be smarter about what you do with the information at various points. Specifically, each factor of a number has a partner (unless the factor is the exact square-root of the value). By computing the upper partner at the same time as discovering the lower factor, you can limit the search space to the square-root of the value. This saves a lot of computation.

For example, this code:

func isPerfectRoot(num int) (b bool) {
    if num <= 1 {
        return
    }
    difference := num - 1
    for fact := 2; difference >= 0 && fact*fact <= num; fact++ {
        quotient := num / fact
        if quotient*fact == num {
            // fact is an actual factor with partner `quotient`
            difference -= fact
            if quotient != fact {
                // not a square root
                difference -= quotient
            }
        }
    }
    return difference == 0
}

This is the fastest I got the code going without also getting in to prime factorization (which is the next step of the process, for the record).

How much faster is the above function (compared to your method)? >50 times faster.

One other comment, Go comes with a powerful benchmarking system that's built in to the test harness system too. When I benchmark various versions of the code I get the results:

rolf@rolftp:~/go/src/perfect$ go test -bench . ./...
BenchmarkPerfect/Perfect-OP-8                        5     261767255 ns/op
BenchmarkPerfect/Perfect-Clean-8                     5     253655127 ns/op
BenchmarkPerfect/Perfect-OneDiv-8                    5     249030400 ns/op
BenchmarkPerfect/Perfect-NegOut-8                    5     237762650 ns/op
BenchmarkPerfect/Perfect-NoMod-8                     5     236858595 ns/op
BenchmarkPerfect/Perfect-Root-8                    300       4805556 ns/op
BenchmarkPerfect/Perfect-RootOne-8                 300       4805588 ns/op
PASS
ok    perfect 20.553s

The above results are based on the following implementations of your function (in the same order as above):

package main

import ()

func isPerfectNumber(num int) bool {
    if num == 1 {
        return false
    }

    c := num - 1
    for i := 2; i <= num/2; i++ {
        if num%i == 0 {
            c -= i
        }
    }

    return c == 0
}

func isPerfectClean(num int) (b bool) {
    if num <= 1 {
        return
    }
    difference := num - 1
    for i := 2; i <= num>>1; i++ {
        if num%i == 0 {
            difference -= i
        }
    }
    return difference == 0
}

func isPerfectOneDiv(num int) (b bool) {
    if num <= 1 {
        return
    }
    difference := num - 1
    limit := num / 2
    for i := 2; i <= limit; i++ {
        if num%i == 0 {
            difference -= i
        }
    }
    return difference == 0
}

func isPerfectNegOut(num int) (b bool) {
    if num <= 1 {
        return
    }
    difference := num - 1
    limit := num / 2
    for i := 2; difference >= 0 && i <= limit; i++ {
        if num%i == 0 {
            difference -= i
        }
    }
    return difference == 0
}

func isPerfectNoMod(num int) (b bool) {
    if num <= 1 {
        return
    }
    difference := num - 1
    limit := num / 2
    for i := 2; difference >= 0 && i <= limit; i++ {
        quot := num / i
        if quot*i == num {
            difference -= i
        }
    }
    return difference == 0
}

func isPerfectRoot(num int) (b bool) {
    if num <= 1 {
        return
    }
    difference := num - 1
    for fact := 2; difference >= 0 && fact*fact <= num; fact++ {
        quotient := num / fact
        if quotient*fact == num {
            // fact is an actual factor with partner `quotient`
            difference -= fact
            if quotient != fact {
                // not a square root
                difference -= quotient
            }
        }
    }
    return difference == 0
}

func isPerfectRootOne(num int) (b bool) {
    if num == 1 {
        return
    }
    difference := num - 1
    for fact := 2; difference >= 0 && fact*fact <= num; fact++ {
        quot := num / fact
        if quot*fact == num {
            difference -= fact
            if quot != fact {
                // not a square root
                difference -= quot
            }
        }
    }
    return difference == 0
}

The test cases and benchmarks for the above are built like:

package main

import (
    "fmt"
    "testing"
)

var perfects = []int{6, 28, 496, 8128}

var perfectFns = map[string](func(int) bool){
    "OP":      isPerfectNumber,
    "Clean":   isPerfectClean,
    "OneDiv":  isPerfectOneDiv,
    "NegOut":  isPerfectNegOut,
    "NoMod":   isPerfectNoMod,
    "Root":    isPerfectRoot,
    "RootOne": isPerfectRootOne,
}

func isP(i int) bool {
    for _, p := range perfects {
        if i == p {
            return true
        }
    }
    return false
}

func testFn(fn func(int) bool) error {
    for i := 1; i < 10000; i++ {
        p := fn(i)
        x := isP(i)
        if p != x {
            return fmt.Errorf("Expected value %v to be perfect: %v but it came back as perfect: %v", i, x, p)
        }
    }
    return nil
}

func TestPerfect(t *testing.T) {
    for n, fn := range perfectFns {
        if err := testFn(fn); err != nil {
            t.Errorf("Error in perfect %v: %v", n, err)
        }
    }
}

func runFn(fn func(int) bool) int {
    cnt := 0
    for i := 1; i < 10000; i++ {
        if fn(i) {
            cnt++
        }
    }
    return cnt
}

func BenchmarkPerfect(b *testing.B) {
    for n, fn := range perfectFns {
        b.Run("Perfect-"+n, func(b *testing.B) {
            for i := 0; i <= b.N; i++ {
                runFn(fn)
            }
        })
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.