Mandelbrot – avec solutions

L’objectif de ce travail est de vous familiariser avec les outils d’analyse des performances d’un programme et d’expérimenter le parallélisme. Commençons avec un programme d’une septantaine de lignes qui produit l’image (élégante ?) suivante :

Voici le code source du programme correspondant :

package main

import (
    "image"
    "image/color"
    "image/png"
    "log"
    "math/cmplx"
    "os"

    "github.com/lucasb-eyer/go-colorful"
)

const (
    output = "mandelbrot.png"
    width  = 2048
    height = 2048
)

func main() {
    f, err := os.Create(output)
    if err != nil {
        log.Fatal(err)
    }

    img := image.NewRGBA(image.Rect(0, 0, width, height))

    buildImage(img, width, height)

    if err = png.Encode(f, img); err != nil {
        log.Fatal(err)
    }
}

func buildImage(m *image.RGBA, width, height int) image.Image {
    for i := 0; i < width; i++ {
        for j := 0; j < height; j++ {
            m.Set(i, j, pixelColor(i, j, width, height))
        }
    }
    return m
}

func mandelbrot(c complex128, maxCount int) int {
    n := 0
    z := complex(0, 0)
    for (cmplx.Abs(z) <= 4) && n < maxCount {
        z = z*z + c
        n++
    }
    return n
}

func norm(x, total int, min, max float64) float64 {
    return (max-min)*float64(x)/float64(total) + min
}

func pixelColor(x, y, width, height int) color.Color {
    maxI := 90
    center := complex(-0.776, .136)
    dx := 1.0e-3
    dy := 1.0e-3

    xi := norm(x, width, real(center)-dx, real(center)+dx)
    yi := norm(y, height, imag(center)-dy, imag(center)+dy)
    i := mandelbrot(complex(xi, yi), maxI)
    if i >= maxI {
        return color.RGBA{98, 20, 17, 255}
    }
    hue := 20 + 340.0*float64(i)/float64(maxI)
    return colorful.Hsv(hue, 1, 1)
}

Profiler

Faites un profilage de votre programme pour trouver la partie à optimiser. Vous pouvez encapsuler le profiler avec le code suivant :

type Profiler struct {
    f *os.File
}

// Start starts the profiler and saves the result in the file name "name"
func (p *Profiler) Start(name string) {
    var err error
    p.f, err = os.Create(name)
    if err != nil {
        log.Fatalf("could not create %v: %v", name, err)
    }
    if err := pprof.StartCPUProfile(p.f); err != nil {
        log.Fatal("could not start CPU profile: ", err)
    }
}

// Stop stops the profiler
func (p *Profiler) Stop() {
    pprof.StopCPUProfile()
    p.f.Close()
}

Dans la fonction main, vous pouvez alors démarrer le profiler :

p := Profiler{}
p.Start("cpu.profile")

et le stopper à la fin :

p.Stop()

Votre programme principal ressemblera donc à ceci :

func main() {
    p := Profiler{}
    p.Start("cpu.profile")
    defer p.Stop()
    ...
}

Exécutez une nouvelle fois le programme avec le profiler. Vous pouvez maintenant étudier le fichier cpu.profile avec la commande suivante :

go tool pprof cpu.profile

Expérimentez avec les commandes suivantes :

• top
• png
• svg
• list main.main

Validez que le point chaud (hot spot) est la méthode buildImage et le fait qu’elle appelle très souvent la méthode mandelbrot :

Tracer

Remplacez le profiler par un tracer :

type Tracer struct {
    f *os.File
}

func (t *Tracer) Start(name string) {
    var err error
    t.f, err = os.Create(name)
    if err != nil {
        log.Fatalf("could not create %v: %v", name, err)
    }
    if err := trace.Start(t.f); err != nil {
        log.Fatal("could not start tracer: ", err)
    }
}

func (t *Tracer) Stop() {
    trace.Stop()
    t.f.Close()
}

et générez un fichier mandelbrot.trace :

func main() {
    t := Tracer{}
    t.Start("mandelbrot.trace")
    defer t.Stop()
    ...
}

Ouvrez le fichier mandelbrot.trace avec l’analyseur de trace 

go tool trace mandelbrot.trace

et cliquez sur View trace :

Observez le comportement de la heap, l’effet du garbage collector ainsi que l’utilisation des cœurs (Proc #).

Zoomez sur le garbage collector et admirez sa performance (seulement 237 µs sur mon PC) :

Notez l’utilisation des goroutines, des threads et des cœurs par le garbage collector.

Optimisation 1 : Le parallélisme

Tentez d’améliorer la performance du programme en introduisant du parallélisme. Dans un premier temps, faites calculer chaque pixel de l’image par une goroutine. Notez que pour une image de 2048 x 2048, vous allez créer 4 millions de goroutines ! Est-ce que Go est capable de gérer ça ?

Vérifiez que l’image est toujours correcte. Mesurez la différence de temps. Combien de temps avez-vous gagné ?

Solution

Pour comparer les performances, on peut mesurer le temps que prend une fonction avec la construction suivante :

start := time.Now()
// Call the function you want to time
elapsed := time.Since(start)
log.Printf("Elapsed time : %s", elapsed)

Solution :

func buildImage(m *image.RGBA, width, height int) image.Image {
    var w sync.WaitGroup
    w.Add(width * height)
    for i := 0; i < width; i++ {
        for j := 0; j < height; j++ {
            go func(i, j int) {
                m.Set(i, j, pixelColor(i, j, width, height))
                w.Done()
            }(i, j)
        }
    }
    w.Wait()
    return m
}

Cette solution génère énormément de goroutines, mais Go est capable de gérer ça. Le gain de performance est cependant limité à cause du supplément de travail dû au démarrage des goroutines.

Observez aussi le tracing obtenu avec ce nouveau programme. Est-ce que vous utilisez les cœurs de manière optimale ?

Optimisation 2 : Un peu moins de parallélisme

Modifiez votre programme pour que les goroutines calculent une ligne entière et pas uniquement un pixel. Vous ne générerez donc que 2048 goroutines.

Vérifiez que l’image est toujours correcte. Mesurez la différence de temps. Observez le tracing obtenu avec ce nouveau programme.

Solution

func buildImage(m *image.RGBA, width, height int) image.Image {
    var w sync.WaitGroup
    w.Add(height)
    for j := 0; j < height; j++ {
        go func(j int) {
            for i := 0; i < width; i++ {
                m.Set(i, j, pixelColor(i, j, width, height))
            }
            w.Done()
        }(j)
    }
    w.Wait()
    return m
}

Cette solution donne d’excellents résultats.

Optimisation 3 : Utilisation de Workers

A la place de créer 2048 goroutines, créez-en le nombre correspondant au nombre de cœurs de votre PC. Vous pouvez obtenir le nombre de CPUs (ou de cœurs) de votre PC avec la fonction runtime.NumCPU(). Les workers recevront les points à calculer par un canal :

type point struct{ x, y int }
c := make(chan point)

Utilisez un sync.WaitGroup pour que la fonction de calcul attende que les workers finissent pour terminer à son tour.

Vérifiez que l’image est toujours correcte. Mesurez la différence de temps. Observez le tracing obtenu avec ce nouveau programme.

Solution

func buildImage(m *image.RGBA, width, height int) image.Image {
    type point struct {
        x, y int
    }
    ch := make(chan point)
    var w sync.WaitGroup

    // Start workers
    for i := 0; i < runtime.NumCPU(); i++ {
        w.Add(1)
        go func() {
            for p := range ch {
                m.Set(p.x, p.y, pixelColor(p.x, p.y, width, height))
            }
            w.Done()
        }()
    }

    // Produce Pixels
    for j := 0; j < height; j++ {
        for i := 0; i < width; i++ {
            ch <- point{i, j}
        }
    }
    close(ch)
    w.Wait()
    return m
}

Cette solution n’est pas optimale car le canal n’a qu’une seule entrée et la synchronisation (involontaire) faite par ce canal ralenti considérablement le processus.

Optimisation 4 : Ajout d’un buffer

Le canal créé au point précédent ne peut contenir qu’un seul point à la fois. Modifiez légèrement le programme pour permettre d’envoyer tous les points d’un seul coup :

type point struct{ x, y int }
c := make(chan point, bufferSize)

Vérifiez que l’image est toujours correcte. Mesurez la différence de temps. Observez le tracing obtenu avec ce nouveau programme.

Solution

func buildImage(m *image.RGBA, width, height int) image.Image {
    type point struct {
        x, y int
    }
    ch := make(chan point, 512)
    var w sync.WaitGroup

    // Start workers
    for i := 0; i < runtime.NumCPU(); i++ {
        w.Add(1)
        go func() {
            for p := range ch {
                m.Set(p.x, p.y, pixelColor(p.x, p.y, width, height))
            }
            w.Done()
        }()
    }

    // Produce Pixels
    for j := 0; j < height; j++ {
        for i := 0; i < width; i++ {
            ch <- point{i, j}
        }
    }
    close(ch)
    w.Wait()
    return m
}

Cette solution est meilleure que la précédente, mais les goroutines ne font que très peu de travail et on peut faire mieux en laissant les goroutines calculer une ligne entière.

Optimisation 5 : Des workers plus efficaces

Modifiez encore votre programme pour que les workers travaillent sur une ligne entière et non sur un seul pixel. Le canal sera utilisé pour envoyer des entiers correspondants à la ligne à produire :

c := make(chan int, bufferSIze)

Vérifiez que l’image est toujours correcte. Mesurez la différence de temps. Observez le tracing obtenu avec ce nouveau programme.

Solution

func buildImage(m *image.RGBA, width, height int) image.Image {
    ch := make(chan int, 512)
    var w sync.WaitGroup

    // Start workers
    for i := 0; i < runtime.NumCPU(); i++ {
        w.Add(1)
        go func() {
            for j := range ch {
                for i := 0; i < width; i++ {
                    m.Set(i, j, pixelColor(i, j, width, height))
                }
            }
            w.Done()
        }()
    }

    // Produce rows
    for j := 0; j < height; j++ {
        ch <- j
    }
    close(ch)
    w.Wait()
    return m
}

Cette solution est très bonne. Elle n’est cependant pas sensiblement meilleure que celle produite lors de l’optimisation 2 (avec 2048 goroutines)