Finding the longest Collatz sequence using Go, concurrently I am working through this problem on project euler.

Basic purpose of the code:

/*
if n is even n -&gt; n/2
if n is odd n -&gt; 3n + 1
which starting number under 1 million produces the longest sequence?
*/


The trouble with the code is that when I implement concurrency as I have, the program runs considerably more slowly than when I am just returning values directly from the get_seq_len function. Am I implementing concurrency incorrectly? Or is the program just not complex enough that there is speed to be gained from concurrency or something?

package main

import ("fmt";"math";"time")


This function takes a number x and then using the formula described in the above comment block creates a sequence of numbers from it until the number 1 is reached. Originally I had the function simply returning the length of the sequence, but now I have it sending the length to the specified channel.

func get_seq_len(x int, c chan int) {
    var count int = 1
    for {
        if x == 1 {
            break
        } else if x%2 == 0 {
            x = x / 2
        } else {
            x = 3 * x + 1
        }
        count++
    }
    // return count + 1
    c &lt;- count + 1
}


Here the main function just step through every number from 1 to whatever the max is and then tests the length of the sequence for that number. I use channel c to pass the sequenced length back to main().

func main() {
    start := time.Now()
    var max int = int(math.Pow(10,6))
    // var max int = int(math.Pow(3,3))
    var max_length int = 0
    var max_num int = 0
    c := make(chan int, 50)

    for i:=1; i&lt;max; i++ {
        // length := get_seq_len(i, c)
        go get_seq_len(i, c)
        length := &lt;-c

        if length &gt; max_length { max_length = length; max_num = i }
    }

    fmt.Println(max_num)
    t := time.Now()
    elapsed := t.Sub(start)
    fmt.Println(elapsed)

}
Longest Collatz sequence
  
  Problem 14
  
  The following iterative sequence is defined for the set of positive
  integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

  
  Although it has not been proved yet (Collatz Problem), it is thought
  that all starting numbers finish at 1.
  
  Which starting number, under one million, produces the longest chain?




In Go, the testing package includes a benchmark facility. Therefore, if we are concerned about performance, as we often are, we start with a simple implementation and benchmark it. Starting number 837799 produces the longest chain of 525 elements. When I ran a Go benchmark, it took 231,949,902 nanoseconds, about one-quarter of a second.

BenchmarkEuler14-8   5   231949902 ns/op   0 B/op   0 allocs/op


euler14a_test.go:

package main

import "testing"

func lenChain(n int) int {
    c := 1
    for ; n &gt; 1; c++ {
        if n&amp;1 == 0 {
            n &gt;&gt;= 1
        } else {
            n += n&lt;&lt;1 + 1
        }
    }
    return c
}

func euler14() (maxn, maxc int) {
    maxs := 1000000 - 1
    for n := 1; n &lt;= maxs; n++ {
        c := lenChain(n)
        if maxc &lt; c {
            maxn = n
            maxc = c
        }
    }
    return maxn, maxc
}

func BenchmarkEuler14(b *testing.B) {
    for N := 0; N &lt; b.N; N++ {
        euler14()
    }
}


If you you want it to be faster, perhaps we could remember some intermediate results. When I ran a Go benchmark, it took 16.979.849 nanoseconds, about than one-sixtieth of a second.

BenchmarkEuler14-8  100  16979849 ns/op  4005900 B/op  1 allocs/op


euler14b_test.go:

package main

import (
    "testing"
)

func lenChain(n int, a []int) int {
    if n &lt; 1 {
        return 0
    }

    c := 1
    for m := n; m &gt; 1; {
        if m &lt; len(a) &amp;&amp; a[m] &gt; 0 {
            c += a[m] - 1
            break
        }

        if m&amp;1 == 1 {
            // m is odd:
            // m = 3*m + 1
            m += m&lt;&lt;1 + 1
            c++
        }
        // m is even:
        // m = m/2
        m &gt;&gt;= 1
        c++
    }

    if n &lt; len(a) &amp;&amp; a[n] &lt; c {
        a[n] = c
    }

    return c
}

func euler14() (maxn, maxc int) {
    maxs := 1000000 - 1
    a := make([]int, maxs/2)
    for n := 1; n &lt;= maxs; n++ {
        c := lenChain(n, a)
        if maxc &lt; c {
            maxn = n
            maxc = c
        }
    }
    return maxn, maxc
}

func BenchmarkEuler14(b *testing.B) {
    for N := 0; N &lt; b.N; N++ {
        euler14()
    }
}


When I ran your "concurrent" program, using eight threads, it took 639,898,032 nanoseconds, about two-thirds of a second.



Some real-world code review questions: What is concurrency? What is parallelism? What do you expect to accomplish? What is your plan?

In your earlier Go performance question, Finding all prime numbers within a range, I pointed ot the importance of benchmarking and algorithms.

You only timed your program. You did not run Go benchmarks. You have no detail. You only used one simple algorithm. My benchmarks allowed me to peer into my code, often line by line. My code, using an optimized memoization algorithm, runs around nearly forty times faster than your concurrent code.

Efficient solutions to the problem exhibit little concurrency and little parallelism. Using concurrency tools adds overhead without any corresponding benefit.




  Comment:
  You compute a lot of intermediate values in the sequence, yet only
  cache the first (being m). I'd imagine your solution would be a lot
  faster if you made a second pass in lenChain that filled all the
  misses into a. If you bite the bullet with function call overhead for
  a recursive implementation, this change would even be trivial. –
  Dillon Davis




When I ran benchmarks, your idea, despite using more memory, was slower: 22,234,021 versus 16.979.849 nanoseconds.

euler14c_test.go:
BenchmarkEuler14-8   50  22234021 ns/op  8003587 B/op  1 allocs/op

euler14b_test.go:
BenchmarkEuler14-8  100  16979849 ns/op  4005900 B/op  1 allocs/op


euler14c_test.go:

package main

import (
    "testing"
)

func lenChain(n int, a []int) int {
    if n &lt;= 1 {
        if n != 1 {
            return 0
        }

        c := 1
        if n &lt; len(a) {
            if a[n] == 0 {
                a[n] = c
            }
        }
        return c
    }

    if n &lt; len(a) {
        if a[n] &gt; 0 {
            return a[n]
        }
    }

    m := n
    if m&amp;1 == 0 {
        // m is even:
        // m = m/2
        m &gt;&gt;= 1
    } else {
        // m is odd:
        // m = 3*m + 1
        m += m&lt;&lt;1 + 1
    }
    c := 1 + lenChain(m, a)

    if n &lt; len(a) {
        a[n] = c
    }

    return c
}

func euler14() (maxn, maxc int) {
    maxs := 1000000 - 1
    a := make([]int, maxs+1)

    for n := 1; n &lt;= maxs; n++ {
        c := lenChain(n, a)
        if maxc &lt; c {
            maxn = n
            maxc = c
        }
    }

    return maxn, maxc
}

func BenchmarkEuler14(b *testing.B) {
    for N := 0; N &lt; b.N; N++ {
        euler14()
    }
}