ENIB S3-PRG_C 05_Optimisation - Optimisation des performances

{} Compilation optimisée

Durant toute la phase de mise-au-point de la réalisation, nous invoquions la commande make sans préciser d'options particulières.
Le fichier GNUmakefile✎

Contenu du fichier GNUmakefile

#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# this GNU-makefile relies on the GCC toolchain
# nb: on Windows, the Mingw-w64 package provides the mingw32-make.exe command
#     ( see https://web.enib.fr/~harrouet/dev_tools/#windows.mingw )

#~~~~ control global settings ~~~~
# make opt=2 --> enable optimisation, then disable debug, but keep symbols
# make opt=1 --> enable optimisation, then disable debug
# make opt=0 --> disable optimisation, then enable debug
opt=0
# make clang=1 --> use clang/clang++, not gcc/g++
# make clang=0 --> use gcc/g++, not clang/clang++
clang=0
# make wasm=1 --> target webassembly rather than the native platform
# make wasm=0 --> target the native platform rather than webassembly
wasm=0

#~~~~ build library or programs ~~~~
# if LIB_TARGET is provided, this library will be built (with its
# platform-specific name), otherwise ${EXE_PREFIX}* programs will be built
LIB_TARGET=
EXE_PREFIX=prog

#~~~~ detect operating system ~~~~
ifneq (${OS},Windows_NT)
  ifneq (,${findstring Ubuntu,${shell lsb_release -i 2>/dev/null}})
    OS:=Ubuntu
  else ifneq (,${findstring Raspbian,${shell lsb_release -i 2>/dev/null}})
    # Standard distribution for Raspberry-Pi
    OS:=Raspbian
  else
    OS:=${strip ${shell uname -s}}
  endif
  ifneq (,${findstring Microsoft,${shell cat /proc/version 2>/dev/null}})
    # Windows-Subsystem-for-Linux
    OS:=${OS}_WSL
  endif
endif

#~~~~ adjust project-specific settings ~~~~
CPPFLAGS=
# CPPFLAGS+=-I header/path
LDFLAGS=-lm
# LDFLAGS+=-L library/path -Wl,-rpath,library/path -l library_name
CFLAGS=
CXXFLAGS=
BINFLAGS=
ifneq (,${findstring Windows_NT,${OS}})
  # nothing special for now
else
  ifneq (,${strip ${LIB_TARGET}})
    BINFLAGS+=-fPIC
  endif
  ifneq (,${findstring Darwin,${OS}})
    # nothing special for now
  else
    ifneq (,${findstring Ubuntu,${OS}})
      # sanitizer sometimes requires gold-linker on Ubuntu
      LDFLAGS+=-fuse-ld=gold
    else ifneq (,${findstring Raspbian,${OS}})
      # some warnings may appear when mixing g++-6 and g++-7 on Raspbian
      CXXFLAGS+=-Wno-psabi
    else
      # nothing special for now
    endif
  endif
endif

#~~~~ adjust platform-specific features (Posix/Windows/Emscripten...) ~~~~
ifneq (,${findstring Windows_NT,${OS}})
  LIB_PREFIX=
  LIB_SUFFIX=.dll
  EXE_SUFFIX=.exe
  SKIP_LINE=echo.
  REMOVE=del /q
else
  LIB_PREFIX=lib
  ifneq (,${findstring Darwin,${OS}})
    LIB_SUFFIX=.dylib
  else
    LIB_SUFFIX=.so
  endif
  EXE_SUFFIX=
  SKIP_LINE=echo
  REMOVE=rm -rf
endif
ifeq (${strip ${wasm}},1)
  LIB_PREFIX:=lib
  LIB_SUFFIX:=.bc
  EXE_SUFFIX:=.html
endif

#~~~~ deduce file names ~~~~
ifneq (,${strip ${LIB_TARGET}})
  LIB_TARGET:=${LIB_PREFIX}${strip ${LIB_TARGET}}${LIB_SUFFIX}
  MAIN_C_FILES=
  MAIN_CXX_FILES=
else
  LIB_TARGET:=
  MAIN_C_FILES=${wildcard ${strip ${EXE_PREFIX}}*.c}
  MAIN_CXX_FILES=${wildcard ${strip ${EXE_PREFIX}}*.cpp}
endif
COMMON_C_FILES=${filter-out ${MAIN_C_FILES},${wildcard *.c}}
COMMON_CXX_FILES=${filter-out ${MAIN_CXX_FILES},${wildcard *.cpp}}
#
MAIN_OBJECT_FILES=${sort ${patsubst %.c,%.o,${MAIN_C_FILES}} \
                         ${patsubst %.cpp,%.o,${MAIN_CXX_FILES}}}
COMMON_OBJECT_FILES=${sort ${patsubst %.c,%.o,${COMMON_C_FILES}} \
                           ${patsubst %.cpp,%.o,${COMMON_CXX_FILES}}}
OBJECT_FILES=${MAIN_OBJECT_FILES} ${COMMON_OBJECT_FILES}
DEPEND_FILES=${patsubst %.o,%.d,${OBJECT_FILES}}
EXE_FILES=${sort ${patsubst %.c,%${EXE_SUFFIX},${MAIN_C_FILES}} \
                 ${patsubst %.cpp,%${EXE_SUFFIX},${MAIN_CXX_FILES}}}
#
GENERATED_FILES=${DEPEND_FILES} ${OBJECT_FILES} ${LIB_TARGET} ${EXE_FILES}
ifneq (,${findstring Darwin,${OS}})
  GENERATED_FILES+=${wildcard *.dSYM}
endif
ifeq (${strip ${wasm}},1)
  GENERATED_FILES+=${patsubst %.html,%.js,${EXE_FILES}}
  GENERATED_FILES+=${patsubst %.html,%.html.mem,${EXE_FILES}}
  GENERATED_FILES+=${patsubst %.html,%.wasm,${EXE_FILES}}
  GENERATED_FILES+=${patsubst %.html,%.wast,${EXE_FILES}}
endif
GENERATED_FILES+=${wildcard output_* *~}

#~~~~ compiler/linker settings ~~~~
CPPFLAGS+=-MMD -pedantic -Wall -Wextra -Wconversion -Wno-sign-conversion
CPPFLAGS+=-Wno-unused -Wno-unused-parameter
CPPFLAGS+=-Werror -Wfatal-errors
CFLAGS+=-std=c99 -Wc++-compat -Wwrite-strings -Wold-style-definition -Wvla
CXXFLAGS+=-std=c++17 -Wno-missing-braces
LDFLAGS+=
BINFLAGS+=
ifeq (${strip ${wasm}},1)
  CC=emcc
  CXX=em++
  CPPFLAGS+=-Wno-dollar-in-identifier-extension
  LDFLAGS+=-s ALLOW_MEMORY_GROWTH=1
else ifeq (${strip ${clang}},1)
  CC=clang
  CXX=clang++
else
  CC=gcc
  CXX=g++
endif
#
ifneq (,${strip ${MAIN_CXX_FILES} ${COMMON_CXX_FILES}})
  # force c++ link if there is at least one c++ source file
  LD:=${CXX}
else
  LD:=${CC}
endif

#~~~~ debug/optimisation settings ~~~~
ifneq (${strip ${opt}},0)
  CPPFLAGS+=-DNDEBUG
  BINFLAGS+=-O3 -ffast-math
  # BINFLAGS+=-fopt-info-vec-optimized
  ifneq (${strip ${wasm}},1)
    BINFLAGS+=-march=native
  endif
  ifeq (${strip ${opt}},2)
    # optimise but keep symbols for profiling
    BINFLAGS+=-g -fno-omit-frame-pointer
  else
    BINFLAGS+=-fomit-frame-pointer
  endif
else
  CPPFLAGS+=-UNDEBUG
  BINFLAGS+=-g -O0
  ifeq (${strip ${wasm}},1)
    # sanitizer is not available yet with Emscripten
  else ifneq (,${findstring Windows_NT,${OS}})
    # sanitizer is not available yet on Windows
  else
    BINFLAGS+=-fsanitize=address,undefined
    ifneq (,${findstring Raspbian,${OS}})
      # dynamic sanitizer libraries may not be found on Raspbian
      BINFLAGS+=-static-libasan -static-libubsan
    endif
  endif
endif

#~~~~ main target ~~~~
all : ${EXE_FILES} ${LIB_TARGET}

rebuild : clean all

.SUFFIXES:
.SECONDARY:
.PHONY: all clean rebuild

#~~~~ linker command to produce the library (if any) ~~~~
${LIB_TARGET} : ${COMMON_OBJECT_FILES}
	@echo ==== linking [opt=${opt}] $@ ====
	${LD} -shared -o $@ $^ ${BINFLAGS} ${LDFLAGS}
	@${SKIP_LINE}

#~~~~ linker command to produce the executable files (if any) ~~~~
%${EXE_SUFFIX} : %.o ${COMMON_OBJECT_FILES}
	@echo ==== linking [opt=${opt}] $@ ====
	${LD} -o $@ $^ ${BINFLAGS} ${LDFLAGS}
	@${SKIP_LINE}

#~~~~ compiler command for every source file ~~~~
%.o : %.c
	@echo ==== compiling [opt=${opt}] $< ====
	${CC} -o $@ $< -c ${BINFLAGS} ${CPPFLAGS} ${CFLAGS}
	@${SKIP_LINE}

%.o : %.cpp
	@echo ==== compiling [opt=${opt}] $< ====
	${CXX} -o $@ $< -c ${BINFLAGS} ${CPPFLAGS} ${CXXFLAGS}
	@${SKIP_LINE}

-include ${DEPEND_FILES}

#~~~~ remove generated files ~~~~
clean :
	@echo ==== cleaning ====
	${REMOVE} ${GENERATED_FILES}
	@${SKIP_LINE}

#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

fourni utilise par défaut des options de fabrication qui facilitent la mise-au-point (sanitizer pour détecter des erreurs à l'exécution, possibilité d'inspecter avec un débogueur).
Ces facilités sont très appréciables mais impactent lourdement les performances.

Pour nous en convaincre, nous devons nous donner les moyens de mesurer une durée d'exécution significative✍.
Pour cela, nous allons réaliser le script run_perfs.sh :

#!/bin/sh

cmd="./prog_part"
for iter in `seq 3` ; do
  for instr in data/*.instrument ; do
    cmd="${cmd} 0.05 ${instr} data/scale.part"
  done
done

echo "~~> ${cmd}"
time ${cmd}

Dans un premier temps, il rédige une commande qui consiste à invoquer notre programme en demandant, à de multiples reprises, à de multiples instruments de jouer la même partition✍.
Après avoir affiché la commande rédigée, elle est invoquée avec la commande time qui sert à mesurer la durée d'exécution.
En exécutant ce script de la façon suivante✍ :

sh run_perfs.sh

vous devriez constater que le programme met plusieurs secondes à s'exécuter✍.
Relancez à plusieurs reprises et notez la durée moyenne obtenue ; elle servira à des comparaisons ultérieures.

Maintenant que la réalisation est complète et fonctionne comme attendu, nous pouvons envisager de nous débarrasser des options de mise-au-point et donner comme consigne au compilateur d'optimiser le code autant que possible.
Nous invoquons alors la commande make de cette façon :

make rebuild opt=1

Cela provoque un nettoyage (comme avec make clean), puis une nouvelle fabrication avec des options d'optimisation (comme avec make opt=1).
En relançant le script run_perfs.sh à plusieurs reprises, vous constaterez une durée moyenne d'exécution significativement inférieure à celle constatée avec les options de mise-au-point.

Sans avoir eu à remanier le code source, le fait de se débarrasser des précautions de mise-au-point permet au compilateur d'appliquer les possibilités d'optimisation qu'on lui demande de trouver.

{} Temps et énergie

Les processeurs modernes donnent des moyens d'estimer leur consommation d'énergie✍.
La commande pyCpuEnergy, disponible dans les salles de Labo de l'ENIB✍ exploite cette possibilité.
Dans votre script run_perfs.sh, remplacez la ligne

time ${cmd}

par

pyCpuEnergy ${cmd}

Reprenez les mesures précédentes avec run_perfs.sh en mode de mise-au-point (après make rebuild), puis en mode optimisé (après make rebuild opt=1).
La commande pyCpuEnergy utilisée doit reporter des temps d'exécution comparables à ce que vous constatiez précédemment avec la commande time.
Les lignes PACKAGE et DRAM (si disponibles sur le matériel) doivent être relevées attentivement puisqu'elles estiment la quantité d'énergie, en Joules, consommée par notre traitement (calcul et accès à la mémoire).
Vous devriez constater que la diminution significative de la durée moyenne d'exécution, grâce à l'optimisation, s'accompagne d'une diminution tout aussi significative de l'énergie consommée par le traitement.

Seulement, cette comparaison simpliste de l'énergie consacrée au calcul pourrait être analysée plus finement.
En effet, même lorsque le processeur n'exécute pas notre programme, il consomme de l'énergie.
Il convient alors de retirer cette part invariable de l'énergie consommée lorsque nous comparons les consommations respectives de deux exécutions (en mise-au-point ou en optimisé).
Relevons tout d'abord la puissance, en Watts, du processeur au repos pendant quelques secondes :

pyCpuEnergy sleep 10

La véritable consommation d'énergie, en Joules, de chaque version du programme (en mise-au-point ou en optimisé) s'obtient en lui retirant la puissance au repos, en Watts, multipliée par la durée d'exécution du programme.
Ce sont ces nouvelles consommations qui doivent être comparées entre-elles.

Voici un exemple relevé sur un poste de travail :

au repos, PACKAGE+DRAM → 3.153 W
en mise-au-point, 4.697 s, PACKAGE+DRAM → 93.868 J
en optimisé, 2.610 s, PACKAGE+DRAM → 50.866 J

Le facteur d'accélération est 1.800 (4.697 / 2.610).
Une comparaison directe des dépenses énergétiques donnerait un facteur 1.845 (93.868 / 50.866).
En corrigeant les dépenses énergétiques nous obtenons :

en mise-au-point, 93.868 J - 4.697 s × 3.153 W → 79.058 J
en optimisé, 50.866 J - 2.610 s × 3.153 W → 42.637 J
le facteur devient 1.854 (79.058 / 42.637)

Nous constatons ici que la correction est négligeable car la consommation au repos du processeur en question est faible devant sa consommation pendant le calcul.

{} Analyse de l'exécution

Nous venons de constater que le compilateur était capable d'optimiser spontanément le code produit lorsqu'on lui en faisait la demande.
Toutefois, le code source peut contenir des maladresses qui entravent le compilateur dans cette démarche.
Il est donc nécessaire d'analyser plus en détail l'exécution d'un programme afin d'en repérer les portions qui pourraient bénéficier d'un effort de reformulation.
Ce sont celles dans lesquelles le programme passe le plus de temps (relativement à la durée totale du programme) ; accélérer, même légèrement, ces portions produira probablement une diminution sensible de la durée du programme, alors qu'améliorer une portion de code qui est peu utilisée n'aura que très peu d'impact sur l'ensemble✍.

Un outil permettant une telle analyse est habituellement désigné par le terme “profiler” et la démarche associé est le “profiling”.
Sous Linux, nous nous appuierons sur l'outil perf ; toutefois, pour faciliter son usage, nous utiliserons le script run_flamegraph.sh✎

Contenu du fichier run_flamegraph.sh

#!/bin/sh

#
# ensure the 'perf' program is installed
#
perf="`which perf 2>/dev/null`"
if [ -z "${perf}" ] ; then
  if [ -n "`which apt 2>/dev/null`" ] ; then
    echo
    echo "!!! missing 'perf' program; please, run the following command:"
    echo
    echo "sudo sh -c 'apt update && apt install linux-tools-generic linux-tools-`uname -r`'"
    echo
  elif [ -n "`which dnf 2>/dev/null`" ] ; then
    echo
    echo "!!! missing 'perf' program; please, run the following command:"
    echo
    echo "sudo dnf install perf"
    echo
  elif [ -n "`which pacman 2>/dev/null`" ] ; then
    echo
    echo "!!! missing 'perf' program; please, run the following command:"
    echo
    echo "sudo pacman -Sy perf"
    echo
  else
    echo
    echo "!!! missing 'perf' program"
    echo
  fi
  exit 1
fi

#
# ensure 'sysctl' setting is set for 'perf'
#
if [ `sysctl -e -n kernel.perf_event_paranoid` != "0" ] ; then
  echo
  echo "!!! missing sysctl setting; please, run the following command:"
  echo
  echo "echo 'kernel.perf_event_paranoid = 0' | sudo sh -c 'tee -a /etc/sysctl.conf | sysctl -q -f -'"
  exit 1
fi

#
# ensure the 'perl' interpreter is installed
#
perl="`which perl 2>/dev/null`"
if [ -z "${perl}" ] ; then
  if [ -n "`which apt 2>/dev/null`" ] ; then
    echo
    echo "!!! missing 'perl' interpreter; please, run the following command:"
    echo
    echo "sudo sh -c 'apt update && apt install perl'"
    echo
  elif [ -n "`which dnf 2>/dev/null`" ] ; then
    echo
    echo "!!! missing 'perl' interpreter; please, run the following command:"
    echo
    echo "sudo dnf install perl"
    echo
  elif [ -n "`which pacman 2>/dev/null`" ] ; then
    echo
    echo "!!! missing 'perl' interpreter; please, run the following command:"
    echo
    echo "sudo pacman -Sy perl"
    echo
  else
    echo
    echo "!!! missing 'perl' interpreter"
    echo
  fi
  exit 1
fi

if [ -z "${*}" ] ; then
  echo
  echo "usage: ${0} program [args...]"
  echo
  exit 1
fi

this_script=`realpath "${0}"`
this_dir=`dirname "${this_script}"`

stackcollapse="${this_dir}/stackcollapse-perf.pl"
if [ ! -r "${stackcollapse}" ] ; then
  echo
  echo "!!! missing '${stackcollapse}' file; please, get it from:"
  echo
  echo "  https://github.com/brendangregg/FlameGraph"
  echo
  exit 1
fi

flamegraph="${this_dir}/flamegraph.pl"
if [ ! -r "${flamegraph}" ] ; then
  echo
  echo "!!! missing '${flamegraph}' file; please, get it from:"
  echo
  echo "  https://github.com/brendangregg/FlameGraph"
  echo
  exit 1
fi

"${perf}" record -F 997 --call-graph dwarf -g "${@}" \
  && "${perf}" script | \
     "${perl}" "${stackcollapse}" --all | \
     "${perl}" "${flamegraph}" > flamegraph.svg
rm -f perf.data*

✍ qui produit un affichage graphique facile à interpréter.
Vous compléterez alors votre script run_perfs.sh en ajoutant cette ligne à sa fin :

run_flamegraph.sh ${cmd}

Pour que les outils évoqués puissent retrouver les noms des fonctions qui correspondent aux différentes portions du code analysé, il faut refabriquer le code exécutable avec la commande make rebuild opt=2✍.
L'invocation de run_perfs.sh doit maintenant effectuer une analyse de l'exécution de votre programme et produire un fichier graphique flamegraph.svg qu'il suffit de visualiser avec firefox flamegraph.svg par exemple.

Les couleurs n'ont pas de signification, elles ne servent qu'à distinguer les multiples barres horizontales.
L'empilement vertical représente les imbrications de fonctions✍.
Les longueurs des barres horizontales représentent les durées relatives passées dans chaque fonction.
Si une barre est très longue et n'en supporte pas d'autres, cela signifie que la fonction correspondante passe beaucoup de temps dans ses propres instructions ; elle mérite donc une attention particulière afin de bénéficier éventuellement d'une reformulation qui permettrait de gagner beaucoup de temps d'exécution.

Voici, à titre d'exemple, un fichier flamegraph.svg correspondant à une version non retravaillée du code source.
Nous constatons que l'essentiel du temps est passé dans la fonction sine_wave() qui elle-même invoque très longuement une fonction de la bibliothèque mathématique✍ ; le nom de la fonction invoquée n'apparaît pas mais nous savons que c'est la fonction mathématique standard sin() puisque notre fonction sine_wave() l'invoque dans son code source.
Sur cet exemple, c'est donc la fonction sine_wave() qui mérite d'être remaniée si nous voulons améliorer les performances de notre programme.

Effectuez une analyse similaire avec le fichier flamegraph.svg produit à partir de votre propre programme.

{} Ajustement du code source

Sur l'exemple utilisé juste avant, nous constations que l'essentiel du temps était passé dans la fonction sin() fournie par le système d'exploitation.
Nous n'y pouvons pas grand-chose, bien entendu, mais si nous estimons que notre problème ne nécessite pas une très grande précision pour ce calcul, nous pouvons décider de nous rabattre sur une version très approximative✍ mais moins coûteuse à calculer.

Voici cette approximation en pseudo-code Python :

# approximate sine of 2π·x with paraboloids
def approx_unit_sine(x):
  x -= int(x)
  y = x - 0.5
  y *= 16.0 * (abs(y) - 0.5)
  # y += 0.225 * y * (abs(y) - 1.0) #  increase precision
  return y

Réalisez-la dans votre code source en langage C et faites en sorte que votre fonction sine_wave() l'utilise à la place de la fonction standard sin().
Remarquez que le facteur 2.0 × π n'est plus nécessaire puisqu'il est implicitement pris en compte dans notre approximation.
Vérifiez, sur un exemple simple, que cette nouvelle version de la fonction sine_wave() génère toujours une sinusoïde convenable.

Après une nouvelle fabrication avec make rebuild opt=2, relancez votre script run_perfs.sh.
Relevez les performances obtenues et analysez le nouveau fichier flamegraph.svg produit à partir de votre programme modifié.
L'amélioration devrait être très sensible.

Pour améliorer encore les performances autour de la génération des sinusoïdes, faîtes en sorte que les fonctions approx_unit_sine() et sine_wave() deviennent inline static.
La justification et la démarche pour cette transformation sont expliquées dans cette section et celle-ci.
Après cette nouvelle intervention dans le code source, reprenez les mesures de performances ; vous devriez constater une nouvelle amélioration✍.

Faite alors le bilan des nouvelles performances obtenues par rapport à la version initiale, que ce soit en temps ou en énergie.

Pour reprendre l'exemple présenté à la fin de cette section, voici ce que nous obtenons après ces améliorations :

code remanié, 0.585 s, PACKAGE+DRAM → 10.723 J

Le facteur d'accélération est 4.462 (2.610 / 0.585).
Une comparaison directe des dépenses énergétiques donnerait un facteur 4.744 (50.866 / 10.723).
En corrigeant les dépenses énergétiques nous obtenons :

code initial, 50.866 J - 2.610 s × 3.153 W → 42.637 J
code remanié, 10.723 J - 0.585 s × 3.153 W → 8.878 J
le facteur devient 4.802 (42.637 / 8.878)

Le travail d'analyse et d'ajustement du code source se révèle extrêmement efficace pour améliorer considérablement les performances en temps et en énergie de notre programme.