How to iterate int range concurrently

Question

For purely educational purposes I created a base58 package. It will encode/decode a uint64 using the bitcoin base58 symbol chart, for example:

b58 := Encode(100)  // return 2j

num := Decode("2j") // return 100

While creating the first tests I came with this:

func TestEncode(t *testing.T) {
    var i uint64
    for i = 0; i <= (1<<64 - 1); i++ {
        b58 := Encode(i)
        num := Decode(b58)
        if num != i {
            t.Fatalf("Expecting %d for %s", i, b58)
        }
    }
}

This "naive" implementation, tries to convert all the range from uint64 (From 0 to 18,446,744,073,709,551,615) to base58 and later back to uint64 but takes too much time.

To better understand how go handles concurrency I would like to know how to use channels or goroutines and perform the iteration across the full uint64 range in the most efficient way?

Could data be processed by chunks and in parallel, if yes how to accomplish this?

Thanks in advance.

UPDATE:

Like mention in the answer by @Adrien, one-way is to use t.Parallel() but that applies only when testing the package, In any case, by implementing it I found that is noticeably slower, it runs in parallel but there is no speed gain.

I understand that doing the full uint64 may take years but what I want to find/now is how could a channel or goroutine, may help to speed up the process (testing with small range 1<<16) probably by using something like this https://play.golang.org/p/9U22NfrXeq just as an example.

The question is not about how to test the package is about what algorithm, technic could be used to iterate faster by using concurrency.

Note that this test also doesn't prove your implementation is actually correct; only that decode/encode match. If they're both wrong in the same way, the test will pass. You need to test against canonical values to prove correctness. — Adrian, Aug 16 '17 at 19:34
If your encode/decode can do 1 billion conversions in a second on one CPU (which is extremely optimistic), you'd need 60 CPUs to finish this task in 10 years. And that's assuming no overhead from goroutines and channels. — Paul Hankin, Aug 16 '17 at 19:42
@PaulHankin you are totally right, but my idea is trying to understand how to solve this like when dealing with prime numbers by using channels goroutines despite takes years I want to learn more about how this could be optimized. — nbari, Aug 17 '17 at 07:20

Adrian · Answer 1 · 2017-08-16T20:46:40.897

1

This functionality is built into the Go testing package, in the form of T.Parallel:

func TestEncode(t *testing.T) {
    var i uint64
    for i = 0; i <= (1<<64 - 1); i++ {
        t.Run(fmt.Sprintf("%d",i), func(t *testing.T) {
            j := i            // Copy to local var - important
            t.Parallel()      // Mark test as parallelizable
            b58 := Encode(j)
            num := Decode(b58)
            if num != j {
                t.Fatalf("Expecting %d for %s", j, b58)
            }
        })
    }
}

edited Aug 16 '17 at 20:46

answered Aug 16 '17 at 19:38

Adrian

42,911
6
107
99

Thanks for pointing T.Parrallel, but could you please fix the example to make it work, if I am right `t.Run()` is missing a `)` second Itoa seems not to work for `uint64`: `cannot use i (type uint64) as type int in argument to strconv.Itoa` – nbari Aug 16 '17 at 20:04
Corrected code sample, but it seems like you get the idea. – Adrian Aug 16 '17 at 20:46
Any idea of why when running in parallel takes more time (is slower) than when not running in t.Parallel() ? – nbari Aug 17 '17 at 07:31
There's overhead involved in parallel processing which, depending on the operation being paralellized, the hardware, the operating system, etc., could result in slower total execution time. – Adrian Aug 17 '17 at 13:09

score 0 · Accepted Answer · answered Aug 19 '17 at 18:31

I came up with this solutions:

package main

import (
    "fmt"
    "time"

    "github.com/nbari/base58"
)

func encode(i uint64) {
    x := base58.Encode(i)
    fmt.Printf("%d = %s\n", i, x)
    time.Sleep(time.Second)
}

func main() {
    concurrency := 4
    sem := make(chan struct{}, concurrency)
    for i, val := uint64(0), uint64(1<<16); i <= val; i++ {
        sem <- struct{}{}
        go func(i uint64) {
            defer func() { <-sem }()
            encode(i)
        }(i)
    }
    for i := 0; i < cap(sem); i++ {
        sem <- struct{}{}
    }
}

Basically, start 4 workers and calls the encode function, to notice/understand more this behavior a sleep is added so that the data can be printed in chunks of 4.

Also, these answers helped me to better understand concurrency understanding: https://stackoverflow.com/a/18405460/1135424

If there is a better way please let me know.

How to iterate int range concurrently

2 Answers2