Why is this double loop so slow?

Issue

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()?

Solution

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)

Answered By – iBug

Answer Checked By – David Goodson (GoLangFix Volunteer)

Leave a Reply

Your email address will not be published.