Écrire des programmes performants en java

C'est une erreur qui pose au moins trois problèmes. Le premier problème est qu'on perd beaucoup de temps à essayer de trouver les meilleurs algorithmes, pourtant le temps est réellement ce qui nous manque le plus. De plus, les meilleurs algorithmes sont souvent très complexes et subtils, et ils deviennent d'autant plus difficiles à déboguer. Par exemple, n'importe quel jeune programmeur peut facilement comprendre le tri par sélection et le déboguer s'il ne marche pas. Mais pour le tri rapide, c'est une autre histoire. Le gain apporté par un meilleur algorithme ne justifie pas toujours l'effort déployé pour y arriver.

Le deuxième problème est que les algorithmes les plus rapides pour un problème donné sont ceux qui exploitent au mieux toutes les spécificités de ce problème. De ce fait, ils ont une nature assez figée et ne peuvent être utilisés en l'état pour d'autres problèmes. Il est donc difficile de réutiliser le code des meilleurs algorithmes. Pourtant, dans bon nombre de cas, il sera plus important de pouvoir réutiliser le code que d'atteindre certains niveaux de performance.

Le troisième problème est que pour pouvoir réellement optimiser, il faut savoir où se perd le temps. C'est une information qu'on peut avoir en analysant l'algorithme, mais c'est une information qu'on a surtout en exécutant l'algorithme. Par exemple, en analysant un algorithme, vous pouvez avoir une idée vous permettant d'exécuter 100 fois plus vite une portion de cet algorithme. Vous faites alors de grosses modifications pour y arriver. Si cette portion s'exécutait avant en 1ms, en allant 100 fois plus vite, vous aurez gagné moins d'1ms. Si elle est appelée une seule fois dans votre programme, on peut considérer qu'en fait vous n'avez rien gagné.

Est-ce à dire qu'il ne faut pas se soucier au départ de la performance ? Non.

Personnellement, j'ai plusieurs fois dû réécrire des programmes parce que dès le départ je voulais juste faire ce qui marche. J'ai réellement obtenu des programmes qui marchaient, mais qui étaient si lents qu'ils étaient au final inutilisables. En réécrivant, j'ai mis en place des optimisations simples auxquelles j'avais pensé dès le départ, et qui n'ont pas vraiment compliqué le programme final.

Vous pourrez ainsi avoir souvent à réécrire, si dès le départ vous n'essayez pas de faire bien. Le temps et le coût liés à ce choix de départ sont suffisamment importants pour qu'on puisse réellement le déconseiller.

C'est là toute la nuance. Il ne s'agit pas de faire au mieux dès le départ, mais de faire bien. Ecrire des programmes performants sans qu'ils soient forcément les meilleurs programmes. Nous ne cherchons pas la perfection, mais l'efficacité.

La première technique consiste naturellement à rechercher s'il n'y a pas dans la littérature ou dans les programmes existants une solution simple et performante pour votre problème. Vous pourrez ainsi trouver des algorithmes que vous vous contenterez de programmer ou qui seront même déjà programmés.

Si vous devez absolument écrire un algorithme, choisissez les structures de données adaptées pour manipuler les collections. L'API de java (collections) fournit pas mal de collections que vous pouvez utiliser dans vos programmes. Vous gagneriez donc à apprendre à vous servir de ces collections. Nous donnons ici juste quelques considérations générales pour leur choix :

Utiliser les BitSet pour réduire l'occupation mémoire, lorsque cela est possible. Comme exemple, nous allons rapidement voir comment utiliser les BitSet dans la simulation d'un problème appelé "problème de la famille". L'énoncé de ce problème est le suivant. Une famille comprend n personnes qui s'assoient une fois par jour autour d'une table de n chaises, en choisissant chaque fois les chaises parfaitement au hasard. En moyenne après combien de jours chaque membre se sera assis sur toutes les chaises ? Dans une tentative de résolution du problème par simulation, on choisit d'associer à chaque membre un vecteur de n entiers. La position i du vecteur aura la valeur 1 si le membre s'est déjà assis sur la chaise i et 0 sinon. La simulation s'achève lorsque le vecteur de chaque membre a la valeur 1 à toutes ses positions.

Il est évident qu'utiliser un BitSet à la place d'un vecteur ferait économiser énormément d'espace, puisqu'au final l'espace utilisé correspondrait à n² bits plutôt qu'à n² entiers.

P.S. Une résolution naïve de ce problème par simulation conduit à une solution qui s'exécute au moins en O(n³), pourtant, il est bien possible de faire beaucoup mieux. Notons ici qu'il est possible de combiner plusieurs structures de données selon les besoins. Cela implique que chaque objet manipulé soit inséré dans chacune des structures de données. A priori, on pourrait penser à une duplication des données. Il n'en est rien. Java manipule les références des objets. Ainsi, lorsque vous placez un objet dans un vecteur et dans une table de hachage, seules les références à cet objet y sont placées. L'objet n'est pas dupliqué. De ce fait, toute manipulation faite sur l'objet à partir d'une structure apparaît immédiatement à celui qui accède à l'objet à partir d'une autre structure, car toutes les structures font référence au même objet.

Dans plusieurs problèmes, on est amené à faire des tris. L'Api standard java fournit un tri par fusion stable et performant, s'exécutant en O(n ln(n)). Ce tri peut être utilisé pour la plupart des cas. Néanmoins, dans certains problèmes où les tris sont très récurrents, il est parfois possible d'utiliser des tris plus efficaces. On pourra donc penser au tri par dénombrement, au tri par paquets ou au tri par base qui sont des tris linéaires.

Par exemple, supposons que l'on ait à trier les individus d'une population d'étudiants d'après leur âge. On peut raisonnablement supposer que l'âge d'un étudiant est compris entre 15 et 100 ans. Pour ce cas, le tri par dénombrement se révélera particulièrement efficace.

On peut également avoir à faire à un programme sur un graphe ayant un très grand nombre de noeuds, chacun ayant un nombre de voisins n'excédant pas un entier relativement faible (40 par exemple), et on s'intéresse pour certains traitements aux noeuds ayant le plus petit nombre de voisins. Dans certains cas, il peut être utile de trier les noeuds selon le nombre de leurs voisins. L'utilisation d'un tri linéaire ici sera très bénéfique si l'opération de tri se fait souvent.

En java, la création d'un objet est une opération coûteuse en temps. Aussi, dans la mesure du possible, il est recommandé de créer le minimum d'objets possibles. On fera le maximum d'efforts pour réutiliser les objets. Notons qu'il ne s'agit pas de créer le minimum de classes possibles. Un objet est créé par l'appel à un constructeur ou à une méthode qui en appelle un. Déclarer un objet ou écrire une nouvelle classe n'est pas la création d'objets. Il s'agit donc essentiellement de minimiser le nombre d'appels à l'opérateur new dans le programme.

IV-D-1. Quelques cas▲

/*déclaration d'une variable quelque part dans la classe du type de l'exception à propager s'il y a erreur*/
Exception badValue = new BadValueExeption() ;

/**
* cette méthode est censée propager une exception du type badvalueException
*/
public void testValue throws BadValueExeption {

	//ici on a constaté une erreur et on va propager l'exception ayant le message msg
	badValue.setMessage(msg) ;/*si cette méthode n'existe pas, écrivez la dans la classe BadValueException*/
	throw badValue ;
	/*magique ! on ne crée pas un nouvel objet, même si cette erreur survient 1000 fois. 
	Naturellement si on doit gérer les accès concurrents, il peut être nécessaire d'utiliser les caches 
	pour éviter de mélanger les messages destinés à des utilisateur différents (voir caches plus bas)*/
}

//notre dataset s'appelle ds
ds.enableDataSetEvents(false) ;// on annule ainsi la création et la propagation des évènements
try{
	makeAllProcesses() ;//on écrit tous les traitements à faire (boucle while,etc)
} catch(Exception exp) {
	//traiter l'exception. Si necessaire, la propager par throw exp ;
} finally {
	enableDataSetEvents(true) ;//remettre le dataset dans son état normal
}

public String toString(){
	StringBuffer bf = new StringBuffer();
	//traitement de remplissage du buffer
	//?.
	//renvoi du resultat
	return bf.toString();
}

StringBuffer bf = new StringBuffer();
public String toString(){
	bf.setLength(0);
	//traitement de remplissage du buffer
	//?
	//renvoi du resultat
	return bf.toString();
}

On pourrait définir un cache comme un objet dans lequel on stocke le résultat d'une opération coûteuse en temps, afin de ne pas avoir à reprendre cette opération si on avait à nouveau besoin du dit résultat. En général, un objet contenu dans un pool est censé être utilisé de manière exclusive par celui qui le prend du pool, tandis que les objets mis dans un cache doivent pouvoir simultanément être accédés par autant de clients que nécessaire.

Vu que dans plusieurs problèmes, il y a toujours des opérations qui reviennent, les caches sont l'un des moyens les plus performants pour améliorer la performance des systèmes informatiques.

IV-E-1. Quelques exemples d'utilisation de caches▲

IV-E-2. Problèmes posés par les caches▲

Le profiler est un outil qui permet de suivre l'exécution d'un programme et par conséquent de déterminer quel temps le programme a passé dans chaque méthode. Grâce au profiler, on détermine rapidement les 20% du code dans lesquels le programme passe 80% de son temps, et on peut mettre en place une stratégie efficace d'optimisation basée uniquement sur cette partie du code.

Java offre un profiler intégré. Pour savoir comment vous en servir, utiliser la commande :

java -Xrunhprof:help

ou la commande

java -prof:help

Un exemple d'utilisation de cette commande est

java -Xrunhprof:cpu=samples,depth=6 com.develop.demos.TestHprof

où depth=6 indique une pile de profondeur 6. Par défaut, les sorties du profiler vont dans le fichier java.hprof.txt. Vous y trouverez un tableau donnant le pourcentage du temps passé par le programme dans chaque partie. Vous pouvez plus aisément exploiter ce fichier en l'important sous Excel. Il existe également de nombreux outils sur le marché spécialisé dans le profiling (les profilers). Ils vous aideront à la fois à identifier les parties qui prennent le plus de temps, mais également celles qui occupent le plus la mémoire. Pour en savoir plus, visiter java performance tuning. A défaut d'utiliser un véritable profiler, la méthode System.currentTimeMillis() est utile pour savoir quel est le temps présent. La différence de valeur entre deux appels de cette méthode définit le temps écoulé entre ces deux appels.

Les collections dynamiques de java (Vector, ArrayList, StringBuffer,etc) utilisent très souvent en interne des tableaux, qui sont redimensionnés chaque fois que la collection est pleine. Lorsque vous utilisez un constructeur vide pour créer ces collections, ce tableau initial est créé avec une taille dépendant de la collection (consulter l'api java pour savoir). Chaque fois que la collection est pleine, un nouveau tableau est créé avec une taille deux fois supérieure à celle de l'ancien, puis les données sont recopiées de l'ancien vers le nouveau. Ce processus peut être couteûx en temps, et si vous avez une idée de la taille maximale que votre collection aura, il convient de l'éviter en créant directement une collection de cette taille (surtout si vous êtes sûr que dans la quasi-totalité des cas votre collection finit par atteindre cette taille). Sinon, utilisez la taille maximale moyenne que votre collection atteint.

// Ainsi, si vous voulez par exemple créer un vecteur qui contiendra 10000 éléments, évitez de le créer avec 
Vector v = new Vector() ; /*ceci risque vous entraîner des dizaines de recopies et ralentir d'autant votre programme*/
// Créez le plutôt avec 
Vector v = new Vector(10000) ;// aucune recopie ne sera faite.

/* Si en fait le vecteur n'atteint que très rarement les 10 000 éléments, 
mais que sa taille moyenne se situe autour de 4000 élements, on utilisera */

Vector v = new Vector(4000) ;
/* il arrivera de faire des recopies, mais on évitera de trop souvent perdre inutilement de l'espace. 
Si le facteur le plus critique c'est le temps, il n'est pas sûr que Vector(10000) soit plus rapide, 
car il faut prendre en compte le temps de création d'un vecteur. */

Le mot clé synchronized peut ralentir les threads en obligeant certains à attendre alors que d'autres ne font pas des traitements qui les gênent. Voir le cours sur les threads pour savoir comment optimiser l'utilisation de ce mot pour les performances.

Même sur un seul processeur, l'utilisation des threads peut améliorer les performances globales d'un programme s'il y a un grand nombre d'accès sur le disque dur, sur le réseau ou à l'écran. Ainsi, lorsqu'un thread fait l'une de ces opérations, il libère le processeur qui peut alors être utilisé par un autre thread.

Supposons que l'on ait les tableaux indices et temp, et que l'on veuille copier nb éléments du tableau indices dans le tableau temp, en les prenant à partir de la position a. On pourrait procéder par la boucle suivante :

for(int j=a ; j<a+nb ; j++)	indices[j] = temp[j];

Il est plus rapide d'écrire :

System.arrayCopy(temp, a, indices, 0, nb);

De manière générale, Pour effectuer la copie d'un tableau dans un autre, utiliser System.arrayCopy permet d'aller plus vite.
De même vous pourrez transformer vos collections en tableau du type qu'ils contiennent par la méthode toArray (collection) (A partir du jdk 1.5)

Pour concaténer les chaînes de caractères, utiliser la classe StringBuffer.

// Plutôt que de faire par exemple 
String s = " a " ;
int n = 100 ;
for(int i=0 ; i<n ; i++) s+="a";

// faire : 

StringBuffer bf = new StringBuffer(101) ;
/*  bien initialiser les collections à la taille convenable pour éviter les recopies*/
bf.append("a");
for(int i=0 ; i<n ; i++) bf.append("a");

L'utilisation de StringBuffer est recommandé lorsque l'objet peut être manipulé par plusieurs Threads. Lorsque l'objet est manipulé par un seul Thread (ce qui est très souvent le cas), il est plus convenable d'utiliser la classe StringBuilder (depuis le jdk 1.5). Cette classe, à la différence du StringBuffer n'est pas synchronisée et est par conséquent plus rapide. Mais si l'objet StringBuilder doit être accèdé par plusieurs Threads, il vaut mieux utiliser StringBuffer.

Pour le flux d'entrées/sorties, utiliser les classes BufferedReader, BufferedOutputStream et toutes les autres classes utilisant des buffers. Rappelez-vous que la taille initiale de votre Buffer est capitale (de préférence une puissance de 2 pour la lecture des flots d'entrée/sortie). Pour en savoir plus : JDCTechTips.

Pour des manipulations sur les fichiers, l'API java.nio permet d'obtenir des performances supérieures à celles de java.io dans pas mal de cas. Pour en savoir plus : nio le magazine de developpez.com de juin 2007 donne également des informations intéressantes sur l'utilisation des classes de java.nio.

Lorsque vous ne devez plus vous servir d'un objet, mettez immédiatement la valeur cet objet à null. Le garbage collector libérera ainsi rapidement la mémoire occupée par cet objet. Vous pouvez également déclencher l'action du garbage collector afin de libérer la mémoire des objets inutilisés par le code suivant :

r = Runtime.getRuntime();
r.gc();

Écrit dans un thread spécial que vous aurez créé pour la circonstance (et non dans votre programme principal).

Cela empêche la mémoire d'être saturée par des objets inutiles. Mais à utiliser avec modération, car le Garbage Collector (GC) est un processus et son exécution demande également les ressources de la machine. Normalement, vous n'avez pas besoin d'appeler explicitement le GC dans votre programme, car il sait bien faire son boulot. Néanmoins, dans certains cas de création très rapide d'objets, nous avons observé que le GC n'éliminait pas toujours à temps les objets passés à null, ce qui conduisait à une saturation de la mémoire. On peut supposer que cela est dû à la très faible priorité du GC par rapport aux autres processus. En présence de tels cas, il peut être nécessaire non seulement de forcer l'appel au GC, mais également de marquer une petite pause dans le processus de création des objets, le temps pour le GC d'en éliminer suffisamment pour que la mémoire ne soit pas saturée par une création rapide d'objets. Dans le cas de tels programmes, il peut être nécessaire de contrôler la quantité de mémoire encore disponible par un appel à la méthode freeMemory() de la classe Runtime (Runtime.getRuntime().freeMemory();) qui renvoie la quantité de mémoire disponible pour la JVM, avant d'appeler le GC si elle est en dessous d'un seuil critique.

Pour les optimisations que vous pouvez faire au niveau du garbage collector, vous référer à JdcTechTip GC

Pour agrandir la quantité de mémoire disponible pour votre programme java, utiliser pour le lancement la commande

java -Xms1024M

Par exemple, pour 1Gb de mémoire (1024Mb), dans le cas d'un lancement par jlnp, utiliser les variables initial-heap-size et max-heap-size pour définir les tailles respectivement initiale et maximale de la mémoire à utiliser par le programme. Cela devrait donner une ligne semblable à celle ci-dessous dans le jnlp.

<j2se version = "1.5+" href = "http://java.sun.com/products/autodl/j2se" initial-heap-size = "256m" max-heap-size = "512m"/>

Ne pas prendre des entiers longs là où les entiers simples seraient suffisants ou les doubles là où les réels suffiraient.

V-J-1. Combiner les techniques▲

V-J-2. Utiliser Serializable plutôt que Externalisable pour l'écriture des objets.▲

V-J-3. Un exemple de cas de combinaisons de techniques : la bibliothèque megasoft.web de MDAL▲

/**
* place dans le buffer le code html correspondant à cet element
* le StringBuffer utilisé a été crée une seule fois dans l'élément au sommet de la hiérarchie, 
* il est passé aux fils afin dene pas recréer des objets stringbuffer  
*/
public void getCode(StringBuffer bf) {
	int j = 0;
	bf.append(getBeginTag());
	int k = getNbItems();
 	//l'element courant construit le code de tous ses fils en leur passant le buffer qu'il a reçu en //paramètre
    for(int i=0 ; i< k ; i++) get(i).getCode(bf);
    bf.append(getEndTag());
  }