19,191 lecturas

Cómo escribir puntos de referencia en Golang como un experto

por Tiago Melo10m2021/05/25

Demasiado Largo; Para Leer

El paquete de prueba de Golang contiene una función de evaluación comparativa que se puede utilizar para examinar el rendimiento de su código de Golang. En este artículo, veremos cómo escribir pruebas comparativas simples que puedan brindarnos buenos conocimientos sobre una solución algorítmica determinada. El cálculo del número de Fibonacci es una serie numérica clásica en la que cada número subsiguiente es la suma de los dos números anteriores: 1 1 2 3 5 8 13... o 1,631 contra 1,875. Compararemos los enfoques recursivo y secuencial calculando la secuencia para 10 y 20.

People Mentioned

Companies Mentioned

featured image - Cómo escribir puntos de referencia en Golang como un experto

La evaluación comparativa de su aplicación suele ser una buena idea cuando se trata de ajustar su rendimiento.

El buen viejo cálculo del número de Fibonacci

El número de Fibonacci es una serie numérica clásica donde cada número subsiguiente es la suma de los dos números anteriores: 1 1 2 3 5 8 13...

Exploremos dos implementaciones diferentes: recursiva y secuencial. Escribiremos pruebas unitarias y comparativas para cada enfoque y luego podremos compararlas.

Enfoque recursivo

Cuando observa el algoritmo de Fibonacci , parece ser muy sencillo de implementar en casi cualquier lenguaje de programación. Y probablemente el primer enfoque para resolverlo es usar recursividad :

 package fibo func RecursiveFibonacci (n uint ) uint { if n <= 1 { return n } return RecursiveFibonacci(n -1 ) + RecursiveFibonacci(n -2 ) }

Cada iteración de la serie descarta los resultados anteriores y luego vuelve a calcular los pasos intermedios para cada iteración posterior.

Agreguemos algunas pruebas unitarias:

 package fibo import "testing" func TestRecursiveFibonacci (t *testing.T) { data := [] struct { n uint want uint }{ { 0 , 0 }, { 1 , 1 }, { 2 , 1 }, { 3 , 2 }, { 4 , 3 }, { 5 , 5 }, { 6 , 8 }, { 10 , 55 }, { 42 , 267914296 }, } for _, d := range data { if got := RecursiveFibonacci(dn); got != d.want { t.Errorf( "got: %d, want: %d" , got, d.want) } } }

Funciona:

 tiago:~/develop/ go /fibonacci/fibo$ go test -run TestRecursiveFibonacci PASS ok bitbucket.org/tiagoharris/fibonacci/fibo 1.875s

Enfoque secuencial

Esta implementación alternativa elimina la recursividad y en su lugar utiliza un bucle for simple y un par de variables. Si lo piensas bien, el algoritmo no es más que una suma de N números. Partimos de 0 y 1 e iremos sumando sumas sucesivas:

 package fibo func SequentialFibonacci (n uint ) uint { if n <= 1 { return uint (n) } var n2, n1 uint = 0 , 1 for i := uint ( 2 ); i < n; i++ { n2, n1 = n1, n1+n2 } return n2 + n1 }

Agreguemos algunas pruebas unitarias:

 func TestSequentialFibonacci (t *testing.T) { data := [] struct { n uint want uint }{ { 0 , 0 }, { 1 , 1 }, { 2 , 1 }, { 3 , 2 }, { 4 , 3 }, { 5 , 5 }, { 6 , 8 }, { 10 , 55 }, { 42 , 267914296 }, } for _, d := range data { if got := SequentialFibonacci(dn); got != d.want { t.Errorf( "got: %d, want: %d" , got, d.want) } } }

También funciona:

 tiago:~/develop/ go /fibonacci/fibo$ go test -run TestSequentialFibonacci PASS ok bitbucket.org/tiagoharris/fibonacci/fibo 0.631s

Tenga en cuenta que aquí tenemos una mejora considerable en el rendimiento; 0,631 s frente a 1,875 s.

evaluación comparativa

Para medir el rendimiento, podríamos medir el tiempo de ejecución y mostrarlo con algunas declaraciones de impresión, por supuesto. Pero Golang ofrece una herramienta muy sofisticada para la evaluación comparativa y es bastante simple de usar.

Escribir un punto de referencia es muy similar a escribir una prueba, ya que comparten la infraestructura del paquete de prueba. Algunas de las diferencias clave son:

Las funciones de Benchmark comienzan con ' Benchmark ', no con ' Test ';
El paquete de prueba ejecuta varias veces las funciones de referencia. El valor de 'bN' aumentará cada vez hasta que el corredor de referencia esté satisfecho con la estabilidad de la referencia;
Cada punto de referencia debe ejecutar el código bajo prueba bN veces. Por lo tanto, un bucle 'for' estará presente en cada función de referencia.

Nuestro archivo fibo_test.go final contendrá pruebas unitarias y comparativas:

 package fibo import ( "testing" ) func BenchmarkTestRecursiveFibonacci_10 (b *testing.B) { for i := 0 ; i < bN; i++ { RecursiveFibonacci( 10 ) } } func BenchmarkTestRecursiveFibonacci_20 (b *testing.B) { for i := 0 ; i < bN; i++ { RecursiveFibonacci( 20 ) } } func BenchmarkTestSequentialFibonacci_10 (b *testing.B) { for i := 0 ; i < bN; i++ { SequentialFibonacci( 10 ) } } func BenchmarkTestSequentialFibonacci_20 (b *testing.B) { for i := 0 ; i < bN; i++ { SequentialFibonacci( 20 ) } } func TestRecursiveFibonacci (t *testing.T) { data := [] struct { n uint want uint }{ { 0 , 0 }, { 1 , 1 }, { 2 , 1 }, { 3 , 2 }, { 4 , 3 }, { 5 , 5 }, { 6 , 8 }, { 10 , 55 }, { 42 , 267914296 }, } for _, d := range data { if got := RecursiveFibonacci(dn); got != d.want { t.Errorf( "got: %d, want: %d" , got, d.want) } } } func TestSequentialFibonacci (t *testing.T) { data := [] struct { n uint want uint }{ { 0 , 0 }, { 1 , 1 }, { 2 , 1 }, { 3 , 2 }, { 4 , 3 }, { 5 , 5 }, { 6 , 8 }, { 10 , 55 }, { 42 , 267914296 }, } for _, d := range data { if got := SequentialFibonacci(dn); got != d.want { t.Errorf( "got: %d, want: %d" , got, d.want) } } }

Compararemos los enfoques recursivo y secuencial calculando la secuencia para 10 y 20.

Con las pruebas de referencia implementadas, todo lo que tenemos que hacer es invocarlas a través de "go test -bench=.". De forma predeterminada, se ejecuta utilizando todas las CPU disponibles. Puede cambiar así: "ir a prueba -cpu=4 -bench=.".

Mi máquina tiene 8 CPU, como podemos ver ejecutando htop :

Vamos a ejecutarlo:

 tiago:~/develop/ go /fibonacci/fibo$ go test -bench=. goos: darwin goarch: amd64 pkg: bitbucket.org/tiagoharris/fibonacci/fibo cpu: Intel(R) Core(TM) i7 -7820 HQ CPU @ 2.90 GHz BenchmarkTestRecursiveFibonacci_10 -8 3534949 335.2 ns/op BenchmarkTestRecursiveFibonacci_20 -8 28592 41587 ns/op BenchmarkTestSequentialFibonacci_10 -8 372993714 3.221 ns/op BenchmarkTestSequentialFibonacci_20 -8 193414836 6.175 ns/op PASS ok bitbucket.org/tiagoharris/fibonacci/fibo 8.406s

El formato de salida es:

 Benchmark< test -name>-<number-of-cpus> number of executions speed of each operation

Ahora podemos tener una mejor idea de cómo el enfoque secuencial es mucho más eficiente que el recursivo:

BenchmarkTestRecursiveFibonacci10-8 se ejecutó 3.534,949 veces con una velocidad de 335,2 ns/op, mientras que BenchmarkTestSequentialFibonacci10-8 se ejecutó 372.993,714 veces con una velocidad de 3,221 ns/op;
BenchmarkTestRecursiveFibonacci20-8 se ejecutó 28.592 veces con una velocidad de 41730 ns/op, mientras que BenchmarkTestSequentialFibonacci20-8 se ejecutó 193.414,836 veces con una velocidad de 6,175 ns/op.

Trazado de gráficos

Soy un gran fan de gnuplot . Incluso he escrito un artículo que muestra cómo puede ser útil.

Este es el archivo gnuplot que se usará para trazar un gráfico de caja :

 ## # gnuplot script to generate a performance graphic. # # it expects the following parameters: # # file_path - path to the file from which the data will be read # graphic_file_name - the graphic file name to be saved # y_label - the desired label for y axis # y_range_min - minimum range for values in y axis # y_range_max - maximum range for values in y axis # column_1 - the first column to be used in plot command # column_2 - the second column to be used in plot command # # Author: Tiago Melo ([email protected]) ## # graphic will be saved as 800x600 png image file set terminal png # allows grid lines to be drawn on the plot set grid # setting the graphic file name to be saved set output graphic_file_name # the graphic's main title set title "performance comparison" # since the input file is a CSV file, we need to tell gnuplot that data fields are separated by comma set datafile separator "," # disable key box set key off # label for y axis set ylabel y_label # range for values in y axis set yrange[y_range_min:y_range_max] # to avoid displaying large numbers in exponential format set format y "%.0f" # vertical label for x values set xtics rotate # set boxplots set style fill solid set boxwidth 0.5 # plot graphic for each line of input file plot for [ i =0:*] file_path every ::i::i using column_1:column_2:xtic(2) with boxes

Este es el objetivo de referencia en nuestro Makefile que ejecuta las pruebas de referencia y traza gráficos tanto para la cantidad de operaciones como para la velocidad de cada operación, para que podamos compararlas fácilmente:

 benchmark: @ cd fibo ; \ go test -bench=. | tee ../graphic/out.dat ; \ awk '/Benchmark/{count ++; gsub(/BenchmarkTest/,""); printf("%d,%s,%s,%s\n",count,$$1,$$2,$$3)}' ../graphic/out.dat > ../graphic/final.dat ; \ gnuplot -e "file_path='../graphic/final.dat'" -e "graphic_file_name='../graphic/operations.png'" -e "y_label='number of operations'" -e "y_range_min='000000000''" -e "y_range_max='400000000'" -e "column_1=1" -e "column_2=3" ../graphic/performance.gp ; \ gnuplot -e "file_path='../graphic/final.dat'" -e "graphic_file_name='../graphic/time_operations.png'" -e "y_label='each operation in nanoseconds'" -e "y_range_min='000''" -e "y_range_max='45000'" -e "column_1=1" -e "column_2=4" ../graphic/performance.gp ; \ rm -f ../graphic/out.dat ../graphic/final.dat ; \ echo "'graphic/operations.png' and 'graphic/time_operations.png' graphics were generated."

Primero, ejecuta las pruebas de referencia utilizando un tubo con el comando tee , lo que hace posible mostrar la salida en la terminal y guardarla en un archivo.

Luego, usamos el comando awk para analizar nuestro archivo en un formato CSV que se usará para trazar los gráficos. Se parece a esto:

 1 ,RecursiveFibonacci_10 -8 , 3579872 , 334.3 2 ,RecursiveFibonacci_20 -8 , 29028 , 42352 3 ,SequentialFibonacci_10 -8 , 375031484 , 3.238 4 ,SequentialFibonacci_20 -8 , 195996889 , 6.148

A continuación, llamamos a gnuplot dos veces: 1) genera un gráfico para el número de ejecuciones 2) genera un gráfico para la velocidad de cada operación.

Vamos a ejecutarlo:

 tiago:~/develop/go/fibonacci$ make benchmark goos: darwin goarch: amd64 pkg: bitbucket.org/tiagoharris/fibonacci/fibo cpu: Intel(R) Core(TM) i7-7820HQ CPU @ 2.90GHz BenchmarkTestRecursiveFibonacci_10-8 3579872 334.3 ns/op BenchmarkTestRecursiveFibonacci_20-8 29028 42352 ns/op BenchmarkTestSequentialFibonacci_10-8 375031484 3.238 ns/op BenchmarkTestSequentialFibonacci_20-8 195996889 6.148 ns/op PASS ok bitbucket.org/tiagoharris/fibonacci/fibo 8.844s 'graphic/operations.png' and 'graphic/time_operations.png' graphics were generated.

Impresionante.

Número de operaciones:

Velocidad de cada operación:

Bastante genial, ¿no?

Bonificación: cálculo de grandes números de Fibonacci

La primera idea que me viene a la mente sería usar una variable entera de 128 bits. Desafortunadamente, Go no tiene uno (todavía). Pero incluso entonces, hay uno de los números de Fibonacci que no cabe en un entero de 128 bits y necesitaríamos un entero de 256 bits y así sucesivamente. Afortunadamente, Go tiene un paquete llamado math/big y su tipo Int que será muy útil en esta implementación:

 func SequentialFibonacciBig (n uint ) * big . Int { if n <= 1 { return big.NewInt( int64 (n)) } var n2, n1 = big.NewInt( 0 ), big.NewInt( 1 ) for i := uint ( 1 ); i < n; i++ { n2.Add(n2, n1) n1, n2 = n2, n1 } return n1 }

Para probarlo, aquí está nuestro main.go que acepta el número deseado como parámetro:

 package main import ( "flag" "fmt" "bitbucket.org/tiagoharris/fibonacci/fibo" ) func main () { var n uint64 flag.Uint64Var(&n, "n" , 0 , "n" ) flag.Parse() fmt.Printf( "%d: %d\n" , n, fibo.SequentialFibonacciBig( uint (n))) }

Y aquí está nuestro objetivo en Makefile para ejecutarlo:

 ## build: build app's binary build: @ go build -a -installsuffix cgo -o main . ## run: run the app run: build @ if [ -z " $(N) " ]; then echo >&2 please set the number via the variable N; exit 2; fi

Vamos a ejecutarlo por, digamos, 200:

 tiago:~/develop/go/fibonacci$ make run N=200 200: 280571172992510140037611932413038677189525

Conclusión

En este artículo, aprendimos cómo usar la utilidad de referencia de prueba de Golang y cómo usar gnuplot para trazar gráficos para una mejor comparación.