GoLang - Sequential vs Concurrent

Question

I have two versions of factorial. Concurrent vs Sequencial.

Both the program will calculate factorial of 10 "1000000" times.

Factorial Concurrent Processing

package main

import (
    "fmt"
    //"math/rand"
    "sync"
    "time"
    //"runtime"
)

func main() {
    start := time.Now()
    printFact(fact(gen(1000000)))
    fmt.Println("Current Time:", time.Now(), "Start Time:", start, "Elapsed Time:", time.Since(start))
    panic("Error Stack!")
}

func gen(n int) <-chan int {
    c := make(chan int)
    go func() {
        for i := 0; i < n; i++ {
            //c <- rand.Intn(10) + 1
            c <- 10
        }
        close(c)
    }()
    return c
}

func fact(in <-chan int) <-chan int {
    out := make(chan int)
    var wg sync.WaitGroup
    for n := range in {
        wg.Add(1)
        go func(n int) {
            //temp := 1
            //for i := n; i > 0; i-- {
            //  temp *= i
            //}
            temp := calcFact(n)
            out <- temp
            wg.Done()
        }(n)
    }
    go func() {
        wg.Wait()
        close(out)
    }()
    return out
}

func printFact(in <-chan int) {
    //for n := range in {
    //  fmt.Println("The random Factorial is:", n)
    //}
    var i int
    for range in {
        i ++
    }
    fmt.Println("Count:" , i)
}

func calcFact(c int) int {
    if c == 0 {
        return 1
    } else {
        return calcFact(c-1) * c
    }
}

//###End of Factorial Concurrent 

Factorial Sequencial Processing

package main

import (
    "fmt"
    //"math/rand"
    "time"
    "runtime"
)

func main() {
    start := time.Now()
    //for _, n := range factorial(gen(10000)...) {
    //  fmt.Println("The random Factorial is:", n)
    //}
    var i int
    for range factorial(gen(1000000)...) {
        i++
    }
    fmt.Println("Count:" , i)
    fmt.Println("Current Time:", time.Now(), "Start Time:", start, "Elapsed Time:", time.Since(start))
}

func gen(n int) []int {
    var out []int
    for i := 0; i < n; i++ {
        //out = append(out, rand.Intn(10)+1)
        out = append(out, 10)
    }
    println(len(out))
    return out
}

func factorial(val ...int) []int {
    var out []int
    for _, n := range val {
        fa := calcFact(n)
        out = append(out, fa)
    }
    return out
}

func calcFact(c int) int {
    if c == 0 {
        return 1
    } else {
        return calcFact(c-1) * c
    }
}

//###End of Factorial sequential processing

My assumption was concurrent processing will be faster than sequential but sequential is executing faster than concurrent in my windows machine.

I am using 8 core/ i7 / 32 GB RAM.

I am not sure if there is something wrong in the programs or my basic understanding is correct.

p.s. - I am new to GoLang.

Answer 1

abhink has given a good answer. I would also like to draw attention to Amdahl's Law, which should always be borne in mind when trying to use parallel processing to increase the overall speed of computation. That's not to say "don't make things parallel", but rather: be realistic about expectations and understand the parallel architecture fully.

Go allows us to write concurrent programs. This is related to trying to write faster parallel programs, but the two issues are separate. See Rob Pike's Concurrency is not Parallelism for more info.

Answer 2

Concurrent version of your program will always be slow compared to the sequential version. The reason however, is related to the nature and behavior of problem you are trying to solve.

Your program is concurrent but it is not parallel. Each callFact is running in it's own goroutine but there is no division of the amount of work required to be done. Each goroutine must perform the same computation and output the same value.

It is like having a task that requires some text to be copied a hundred times. You have just one CPU (ignore the cores for now).

When you start a sequential process, you point the CPU to the original text once, and ask it to write it down a 100 times. The CPU has to manage a single task.

With goroutines, the CPU is told that there are a hundred tasks that must be done concurrently. It just so happens that they are all the same tasks. But CPU is not smart enough to know that.

So it does the same thing as above. Even though each task now is a 100 times smaller, there is still just one CPU. So the amount of work CPU has to do is still the same, except with all the added overhead of managing 100 different things at once. Hence, it looses a part of its efficiency.

To see an improvement in performance you'll need proper parallelism. A simple example would be to split the factorial input number roughly in the middle and compute 2 smaller factorials. Then combine them together:

// not an ideal solution

func main() {
    ch := make(chan int)
    r := 10
    result := 1
    go fact(r, ch)
    for i := range ch {
        result *= i
    }
    fmt.Println(result)
}

func fact(n int, ch chan int) {
    p := n/2
    q := p + 1
    var wg sync.WaitGroup
    wg.Add(2)
    go func() {
        ch <- factPQ(1, p)
        wg.Done()
    }()
    go func() {
        ch <- factPQ(q, n)
        wg.Done()
    }()
    go func() {
        wg.Wait()
        close(ch)
    }()
}

func factPQ(p, q int) int {
    r := 1
    for i := p; i <= q; i++ {
        r *= i
    }
    return r
}

Working code: https://play.golang.org/p/xLHAaoly8H

Now you have two goroutines working towards the same goal and not just repeating the same calculations.

Note about CPU cores:

In your original code, the sequential version's operations are most definitely being distributed amongst various CPU cores by the runtime environment and the OS. So it still has parallelism to a degree, you just don't controll it.

The same is happening in the concurrent version but again as mentioned above, the overhead of goroutine context switching makes the performance come down.