How to use go concurrency for a better runtime in Go [closed]

Question

I am trying concurrency in Go with simple problem example which is the nth prime palindrome numbers, eg: 1st to 9th palindrome sequence is 2, 3, 5, 7, 11, 101, 131, 151. I am stuck and have no idea what to do with it.

My current code is like this:

n := 9999999

count := 0

primePalindrome := 0

for i := 0; count < n; i++ {
    go PrimeNumber(i)
    go PalindromeNumber(i)
    
    if PrimeNumber(i) && PalindromeNumber(i) {
        primePalindrome = i
        count++
    }
}

How do I know that function PrimeNumber(i) and PalindromeNumber(i) already executed and done by go routine so that I can give IF CONDITION to get the number?

Answer 1

Here's my solution: https://go.dev/play/p/KShMctUK9yg

The question is, what if I want to find the 9999999th palindrome with faster runtime using Go concurrency, how to apply concurrency in PrimeNumber() and PalindromeNumber() function?

Similar to Torek, I add concurrency by creating multiple workers that can each check a number, thereby checking several numbers in parallel.

Algorithmically, the program works like this. One goroutine generates possible prime palindromes. A pool of multiple goroutines all check candidates. The main goroutine collects results. When we have at least enough results to provide the nth prime palindrome, we sort the list and then return the answer.

Look closely at the use of channels and a wait group to communicate between the goroutines:

• multiple worker goroutines. Their job is to run palindrome and then prime checks for candidate numbers. They listen on the candidates channel; when the channel is closed, they end, communicating that they're done to the wg sync.WaitGroup.

• a single candidate generator. This goroutine sends each candidate to one of the workers by sending to the candidates channel. If it finds the done channel to be closed, it ends.

• the main goroutine also functions as the collector of results. It reads from the resc (results) channel and adds the results to a list. When the list is at least the required length, it closes done, signaling the generator to stop generating candidates.

The done channel may seem redundant, but it's important because the main results collector knows when we are done generating candidates, but isn't the one sending to candidates. IF we closed candidates in main, there's a good chance the generator would attempt to write to it and that would crash the program. The generator is the one writing candidates; it is the only goroutine that "knows" no more candidates will be written.

Note that this implementation generates at least n prime palindromes. Since it generates the prime palindromes in parallel, there's no guarantee that we have them in order. We might generate up to prime palindrome n+m where m is the number of workers minus one, in the worst case.

There's a lot of room for improvement here. I'm pretty sure the generator and collector roles could be combined in one select loop on candidate and result channels. The program also seems to have a very hard time if n is as big as 9999999 when I run it on my windows machine - see if your results vary.

Edit: Performance enhancements

If you're looking to improve performance, here's a few things I found and noticed last night.

• No need to check even numbers. for i := start; ; i += 1 + (i % 2) skips to the next odd number, then adds 2 every other time to keep on the odd numbers.

• all palindromes of even numbered decimal length are divisble by 11. So whole sets of numbers of even length can be skipped. I do this by adding math.Pow10(len(str)) to even numbered decimal representations to add another digit. This is what caused the program to stop outputting numbers for large amounts of time - every even numbered set of numbers cannot produce prime palindromes.

• if the number's decimal notation starts with an even number it can't be a prime palindrome unless it's only one digit long. Same is true of 5. In the code below I add math.Pow10(len(str)-1) to the number to move to the next odd numbered sequence. If the number starts with 5, I double that to move to the next odd numbered sequence.

These tricks make the code a lot more performant, but it's still a brute force at the end of the day and I still haven't gotten even close to 9999999.

  // send candidates
  go func() {
    // send candidates out
    for i := start; ; i += 1 + (i % 2) {
      str := strconv.FormatInt(i, 10)
      if len(str) % 2 == 0 && i != 11 {
        newi := int64(math.Pow10(len(str)))+1
        log.Printf("%d => %d", i, newi)
        i = newi
        continue
      }
      if first := (str[0]-'0'); first % 2 == 0 || first == 5 {
        if i < 10 {
          continue
        }
        nexti :=  int64(math.Pow10(len(str)-1))
        if first == 5 {
          nexti *= 2
        }
        newi := i + nexti
        log.Printf("%d -> %d", i, newi)
        i = newi-2
        continue
      }
      select {
      case _, ok := <-done:
        if !ok {
          close(candidates)
          return
        }

      case candidates <- i:
        continue
      }
    }
  }()

Answer 2

There are multiple issues to solve here:

• we want to spin off "is prime" and "is palindrome" tests
• we want to sequentially order the numbers that pass the tests
• and of course, we have to express the "spin off" and "wait for result" parts of the problem in our programming language (in this case, Go).

(Besides this, we might want to optimize our primality testing, perhaps with a Sieve of Eratothenese algorithm or similar, which may also involve parallelism.)

The middle problem here is perhaps the hardest one. There is a fairly obvious way to do it, though: we can observe that if we assign an ascending-order number to each number tested, the answers that come back (n is/isnot suitable), even if they come back in the wrong order, are easily re-shuffled into order.

Since your overall loop increments by 1 (which is kind of a mistake¹), the numbers tested are themselves suitable for this purpose. So we should create a Go channel whose type is a pair of results: Here is the number I tested, and here is my answer:

type result struct {
    tested int  // the number tested
    passed bool // pass/fail result
}
testC := make(chan int)
resultC := make(chan result)

Next, we'll use a typical "pool of workers". Then we run our loop of things-to-test. Here is your existing loop:

for i := 0; count < n; i++ {
    go PrimeNumber(i)
    go PalindromeNumber(i)
    
    if PrimeNumber(i) && PalindromeNumber(i) {
        primePalindrome = i
        count++
    }
}

We'll restructure this as:

count := 0
busy := 0
results := []result{}
for toTest := 0;; toTest += 2 {
    // if all workers are busy, wait for one result
    if busy >= numWorkers {
        result := <-resultC // get one result
        busy--
        results := addResult(results, result)
        if result.passed {
            count++ // passed: increment count
            if count >= n {
                break
            }
        }
    }
    // still working, so test this number
    testC <- toTest
    busy++
}
close(testC) // tell workers to stop working
// collect remaining results
for result := range resultC {
    results := addResult(results, result)
}

(The "busy" test is a bit klunky; you could use a select to send or receive, whichever you can do first, instead, but if you do that, the optimizations outlined below get a little more complicated.)

This does mean our standard worker pool pattern needs to close the result channel resultC, which means we'll add a sync.WaitGroup when we spawn off the numWorkers workers:

var wg sync.WaitGroup
wg.Add(numWorkers)
for i := 0; i < numWorkers; i++ {
    go worker(&wg, testC, resultC)
}
go func() {
    wg.Wait()
    close(resultC)
}()

This makes our for result := range resultC loop work; the workers all stop (and return and call wg.Done() via their defers, which are not shown here) when we close testC so resultC is closed once the last worker exits.

Now we have one more problem, which is: the results come back in semi-random order. That's why we have a slice of results. The addResult function needs to expand the slice and insert the result in the proper position, using the value-tested. When the main loop reaches the break statement, the number in toTest is at least the n'th palindromic prime, but it may be great than the n'th. So we need to collect the remaining results and look backwards to see if some earlier number was in fact the n'th.

There are a number of optimizations to make at this point: in particular, if we've tested numbers through k and they're all known to have passed or failed and k + numWorkers < n, we no longer need any of these results (whether they passed or failed) so we can shrink the results slice. Or, if we're interested in building a table of palindromic primes, we can do that, or anything else we might choose. The above is not meant to be the best solution, just a solution.

Note again that we "overshoot": whatever numWorkers is, we may test up to numWorkers-1 values that we didn't need to test at all. That, too, might be optimizable by having each worker quit early (using some sort of quit indicator, whether that's a "done" channel or just a sync/atomic variable) if they're working on a number that's higher than the now-known-to-be-at-least-n'th value.

---

¹We can cut the problem in half by starting with answers pre-loaded with 2, or 1 and 2 if you choose to consider 1 prime—see also http://ncatlab.org/nlab/show/too+simple+to+be+simple. Then we run our loop from 3 upwards by 2 each time, so that we don't even bother testing even numbers, since 2 is the only even prime number.

Answer 3

The answer depends of many aspects of your problem

For instance, if each step is independent, you can use the example below. If the next step depends on the previous you need to find another solution.

For instance: a palindrome number does not depends of the previous number. You can paralelize the palindrome detection. While the prime is a sequential code.

Perhaps check if a palindrome is prime by checking the divisors until the square root of that number. You need to benchmark it

numbers := make(chan int, 1000) // add some buffer

var wg sync.WaitGroup

for … { // number of consumers 
    wg.Add(1)
    go consume(&wg, numbers)
}

for i … {
    numbers <- i
}

close(numbers)

wg.Wait()

// here all consumers ended properly
…

func consume(wg *sync.WaitGroup, numbers chan int){
    defer wg.Done()
    for i := range numbers {
         // use i
    }
}