Why is this double loop so slow?-CodePudding

So I only started with Golang today so I have just about no knowledge of its inner workings but the following double for loop seems slow.

func image() {
    height := 256
    width := 256

    start := time.Now()

    var output string = "P3\n"   strconv.Itoa(width)   " "   strconv.Itoa(height)   "\n255\n"

    for w := width; w > 0; w-- {
        for h := height; h > 0; h-- {
            r := w - 1
            g := h - 1
            b := 1

            output  = strconv.Itoa(r)   " "   strconv.Itoa(g)   " "   strconv.Itoa(b)   "\n"
        }
    }
    elapsed := time.Since(start)
    fmt.Printf("Generating data took %s", elapsed)
}

I added the timer to time the function and it takes about 2 seconds to complete. This seems quite slow right?

Even when I remove the strconv.Itoa() conversions and just replace it with normal strings the average time is about 600ms which is much better but I thought it would be quicker.

My questions are the following:

Does these speeds seem slow?
How can I fix it ? Perhaps an alternative to strconv.Itoa()?

CodePudding user response：

Repetitive output = is going to cause a lot of memory re-allocation for the underlying string. You should save your "parts" in a []string and join them only once.

On my machine, your code runs for 2.9-3.1s. This optimized version runs in 8.5ms:

func main() {
    height := 256
    width := 256

    start := time.Now()

    var output string = "P3\n"   strconv.Itoa(width)   " "   strconv.Itoa(height)   "\n255\n"
    var contents []string

    for w := width; w > 0; w-- {
        for h := height; h > 0; h-- {
            r := w - 1
            g := h - 1
            b := 1

            contents = append(contents, strconv.Itoa(r) " " strconv.Itoa(g) " " strconv.Itoa(b) "\n")
        }
    }
    output  = strings.Join(contents, "")
    elapsed := time.Since(start)
    fmt.Printf("Generating data took %s\n", elapsed)
}

Pre-allocating contents further brings it down to 6.4ms:

// replace "var contents []string"
contents := make([]string, 0, width*height)

CodePudding user response：

You can use a string Builder too, which will allocate memory on demand and minimize copying. You can find a doc about it here.

Example code:

func main() {
    height := 256
    width := 256

    start := time.Now()

    var output string = "P3\n"   strconv.Itoa(width)   " "   strconv.Itoa(height)   "\n255\n"
    var contents strings.Builder

    for w := width; w > 0; w-- {
        for h := height; h > 0; h-- {
            r := w - 1
            g := h - 1
            b := 1

            contents.WriteString(strconv.Itoa(r)   " "   strconv.Itoa(g)   " "   strconv.Itoa(b)   "\n")
        }
    }
    output = contents.String()
    elapsed := time.Since(start)
    _ = output
    fmt.Printf("Generating data took %s\n", elapsed)
}