Idées Distribuées – Distributed Ideas

Starting version 4.7 JUnit introduces a powerful new concept allowing to hook directly inside JUnit’s test execution workflow.

A number of hooks are already available:

* bundled ones: ExpectedException, Timeout, ErrorCollector, TemporaryFolder …
* concurrent test execution
* fit facility

Following is my addition facilitating tests execution under different logging level.

public class LoggerRule implements MethodRule {

    private final Logger logger;
    private final Level[] levels;

    public LoggerRule(final Logger logger) {
        this(logger, Level.OFF, Level.ALL);
    }

    public LoggerRule(final Logger logger, final Level ... levels) {
        this.logger = logger;
        this.levels = levels;
    }

    public Statement apply(final Statement base, final FrameworkMethod method, final Object target) {
        return new Statement() {
            public void evaluate() throws Throwable {
                for (final Level level : LoggerRule.this.levels) {
                    LoggerRule.this.logger.setLevel(level);
                    base.evaluate();
                }
            }
        };
    }

}

Simply declare it in your test class and tests will be executed levels.length time, each time with a different Level. No more bugs due to bad logs!

public class MyTest {

    @Rule
    public final LoggerRule loggerRule = new LoggerRule(Logger.getLogger("myLogger"), Level.OFF, Level.ALL);

    @Test
    public void test() {
        ...
    }

}

Il y a quelques temps déjà, je discutais avec un collègue dans ce lieu de socialisation qu’est la machine à café. Nous ne parlions pas de notre travail, mais nous parlions tout de même d’informatique. Nous eûmes l’échange suivant :

• Les langages fonctionnels, c’est nul ; les fonctions récursives ça peut casser la pile d’exécution.
• Bah non, si tu utilises une fonction récursive terminale…
• Une quoi ?

Les mots ne sont pas exacts, mais je crois être fidèle à nos intentions. Depuis j’ai eu d’autres occasions de vérifier que cette notion de programmation était souvent très mal connue. D’où mon idée d’écrire un article sur le sujet.

Qu’est-ce qu’une fonction récursive terminale ?

Une fonction récursive terminale est une fonction qui lorsqu’elle fait appel à elle-même, le fait en tout dernier. Concrètement il n’y a pas de calcul entre l’appel récursif et l’instruction return. Le terme anglais est « tail-end recursion ».

Il s’agit donc d’une manière d’écrire votre fonction récursive.

À quoi ça sert ?

Cela sert à produire du code efficace, clair, et qui ne risque pas de faire déborder la pile d’exécution.

D’un point de vue algorithmique, une fonction récursive terminale est équivalente à une simple boucle. Écrire ainsi vos fonctions récursives permettra au compilateur d’optimiser efficacement le code produit.

Dans un langage impératif, le programmeur a souvent l’idée d’utiliser une boucle, donc la question est moins importante. En revanche, dans un langage fonctionnel comme OCaml ou parallelC#, qui vous invite par sa syntaxe et son esthétisme à user de fonctions, il est primordial d’écrire des fonctions terminales.

Un exemple commenté : la fonction ‘factorielle’ en langage C

Pour illustrer mon propos, j’ai choisi de commenter plusieurs implémentations de la fonction « factorielle », écrites en langage C.

La plupart des programmeurs (dé)formés par des années de pratique du C, préfèrent utiliser une boucle for :

int factorial(int n) {
    int res=1;
    for(; n; --n) res *= n;
    return res;
}

Ce code fonctionne parfaitement bien. Il a l’unique défaut d’être finalement assez éloigné de la définition mathématique de la factorielle, c’est-à-dire que la plupart des gens le jugeront peu naturel.

Considérons maintenant une implémentation plus naturelle, très proche de la définition apprise sur les bancs d’école. C’est aussi la façon dont la plupart des programmeurs débutants écrivent cette fonction :

int factorial (int n) {
    if (n == 0) return 1;
    else return n * factorial(n - 1);
}

Cette implémentation récursive est assurément très mauvaise. Elle consomme beaucoup de mémoire en pile, donc c’est lent et ça peut aussi se terminer prématurément si on l’appelle avec un paramètre trop grand (stack overflow). La version récursive terminale pallie précisément ce problème :

int factorial (int n, int accu) {
    if (n == 0) return accu;
    else return factorial(n - 1, n * accu);
}

C’est une tail-end recursion car l’appel récursif est le dernier statement. Vous avez certainement remarqué que pour ce faire, j’ai dû introduire un paramètre supplémentaire ; ceci est discuté plus loin.

Comment ça marche ?

Comme vous le savez certainement, lorsque l’on effectue un appel de fonction, la fonction appelante stocke sur la pile d’exécution les paramètres de la fonction appelée et l’adresse de retour. La fonction appelée utilise ses paramètres pour effectuer ses calculs et, à la toute fin, saute à l’adresse précédemment sauvegardée. On revient alors dans le code de la fonction appelante qui dépile avant de continuer…

Sachant cela, il est facile de comprendre qu’un grand nombre d’appels de fonctions imbriqués fait grossir la pile, et que les fonctions récursives représentent un risque important de débordement de pile (stack overflow).

L’optimisation opérée par le compilateur consiste à produire un code qui, lors de l’appel récursif, au lieu d’empiler… et de dépiler plus tard, va remplacer les paramètres actuels et simplement boucler. Ceci est possible dans le cas particulier d’une fonction récursive terminale car il n’y a plus rien à faire dans la fonction appelante.

En fait cette optimisation n’est pas propre aux fonctions récursives. Toute fonction se terminant par un appel de fonction (appel récursif ou pas) est susceptible de profiter de la même optimisation. On parle de sibling call ou tail call.

Un dessin valant mieux que des mots, voici un exemple d’optimisation de tail call sur une machine windows x86 : la méthode foo se termine par un appel à la méthode bar, donc on libère la place réservée pour l’exécution de foo avant d’exécuter bar.

 As soon as foo          While foo        When foo is about to
   is called            is executing        tail call to bar

                      |              |
                      +--------------+
                      |              |
                      |              |
                      | foo's frame  |
                      |              |      |              |
                      |              |      +--------------+
|              |      |              |      |return address|
+--------------+      +--------------+      +--------------+
|return address|      |return address|      |              |
+--------------+      +--------------+      |              |
|              |      |              |      |              |
|  stack args  |      |  stack args  |      |  stack args  |
|    of foo    |      |    of foo    |      |    of bar    |
|              |      |              |      |              |
+--------------+      +--------------+      +--------------+
|              |      |              |      |              |
|              |      |              |      |              |
|              |      |              |      |              |
|   Frame of   |      |   Frame of   |      |   Frame of   |
| foo's caller |      | foo's caller |      | foo's caller |
|              |      |              |      |              |
|              |      |              |      |              |

Ce dessin suggère un algorithme assez grossier pour libérer la pile de foo. En fait le compilateur peut faire quelque chose de très subtile grâce à un calcul de dépendances des variables et expressions. On produit alors un code en tout point semblable à la meilleure des boucles (un décompilateur ne pourra pas faire la différence).

Pour ce faire, le compilateur doit effectuer des analyses compliquées. Ces analyses sont biens connues : factorisation, élimination du code mort, une allocation optimales des registres, l’analyse d’échappement, le calcul de causalité (élimination des synchronisations inutiles, invalidation des caches mémoires), et bien d’autres. Cependant elles font toujours l’objet d’une recherche intense. Le défi est d’être capable d’effectuer une optimisation de qualité dans un temps raisonnable (utilisable dans un JIT) et/ou en consommant très peu de mémoire (carte à puce, téléphone). Mais je me perds dans mes digressions, revenons à notre sujet principal.

A-t-on raison de parler d’optimisation ?

Certains auteurs contestent, à tort, le terme d’« optimisation ». L’argument avancé est qu’un programme qui se termine par une erreur stack overflow n’a visiblement pas le même comportement qu’un programme qui se termine en retournant un résultat (ou qui ne se termine pas).

En effet, pour être correcte une optimisation ne doit pas modifier la sémantique d’un programme (et ce n’est pas toujours simple, cf. la gestion de la sécurité, les interactions avec le ramasse miettes, la gestion des exceptions et des signaux etc.) Mais en algèbre de compilation on considère toujours que la machine cible possède une mémoire infinie. Sans cela, la plupart des optimisations ne pourraient pas être effectuées par le compilateur au prétexte que cela pourrait prévenir une erreur au runtime…

Voici un exemple pour les réfractaires :

a = 1 + 1 + 1 + 1; // ça fait 4

La plupart des compilateurs effectuent les calculs à la compilation quand c’est possible. Pourtant, ce faisant on change effectivement le comportement du programme à l’exécution : il est possible que l’évaluation de cette expression arithmétique provoque un stack overflow dans certaines conditions.

Le terme consacré est Tail Call Optimization (TCO).

Que faire du paramètre supplémentaire ?

Comme je l’ai déjà fait remarquer dans l’exemple de la factorielle, pour écrire une fonction récursive sous forme terminale, il est souvent nécessaire de modifier sa signature en y ajoutant un paramètre.

Que faire de ce paramètre ?

• On peut le considérer comme une astuce qu’il convient de cacher. Dans notre exemple, le paramètre accu joue le même rôle que la variable de boucle res.
• On peut aussi le considérer comme un paramètre qui fait sens et qui améliore notre fonction. Ainsi dans notre exemple, le second paramètre accu sert à choisir la valeur du cas de base (factorielle(0)).

En général, on souhaite masquer ce paramètre en trop. On définit alors deux fonctions : la première que l’on cache et qui prend deux paramètres, la seconde qui appelle la première et expose la signature voulue. Pour faire cela, il existe diverses méthodes selon le langage (et les paradigmes) utilisé.

On peut définir la fonction récursive dans la fermeture (closure) de la fonction principale. C’est une technique couramment utilisée dans les langages fonctionnels.

(* Exemple en OCaml *)
let factorielle = function n ->
    let rec __factorielle = function n -> function accu ->
        if n = 0
        then accu
        else __factorielle (n-1) (n*accu)
    in __factorielle n 1
;;

Plus classique, on peut restreindre la portée de la fonction récursive. Ainsi en C, on peut utiliser le mot static pour empêcher une fonction d’être exposée dans l’interface du module.

// Exemple en C
static int __factorielle (int n, int accu) {
    if (n == 0) return accu;
    else return __factorielle(n-1, n*accu);
}
int factorielle (int n) {
    return __factorielle(n, 1);
}

La plupart des langages objets offrent des modificateurs d’accès. En Java, on utilisera les modificateurs public et private :

/* Exemple en Java */
public Mathematiques {
    private static __factorielle(int n, int accu) {
        if (n == 0) return accu;
        else return __factorielle(n-1, n*accu);
    }
    public static factorielle (int n) {
        return __factorielle(n, 1);
    }
}

Certains langages, tels que Python ou C#, permettent de donner une valeur par défaut à un paramètre. Ceci est particulièrement utile dans notre cas.

# Exemple en Python
def factorielle(n, accu=1):
    if n == 0: return accu
    else: return factorielle(n-1, n*accu)

Évidemment il n’y a pas une seule bonne manière de faire. Vous devrez juger quelle est la technique la plus pertinente, la mieux adaptée à votre cas. C# est sans doute le langage qui offre le plus de possibilités.

Est-ce que toutes les fonctions récursives peuvent être écrites sous une forme terminale ?

Oui, toute. Les preuves : les théories de la calculabilité, la logique combinatoire, combinateur de point fixe.

Un second exemple commenté : les nombres de Fibonacci

Considérons ensemble une fonction un peu plus difficile à écrire : la fonction qui calcule les nombres de Fibonacci.

Pour écrire la fonction de Fibonacci sous forme récursive terminale, nous avons besoin d’utiliser non pas un, mais deux paramètres supplémentaires (accu0 et accu1). Ceci est à rapprocher du fait que, pour l’implémentation itérative, nous utilisons deux variables de boucle (res0 et res 1) et du fait que la définition récursive de la fonction donne deux cas de base (fibonacci(0) et fibonacci(1)).

# Pour changer, voici du Ruby
# Nombre de Fibonacci, implémentation naïve
def fibonacci_naive(n)
    if n == 0
        0
    elsif n == 1
        1
    else
        fibonacci_naive(n-1) + fibonacci_naive(n-2)
    end
end

# Nombre de Fibonacci, implémentation avec une boucle
def fibonacci_boucle(n)
    res0, res1 = 1, 0 # Pour n'avoir qu'un seul test, on commence au rang -1
    (1..n).each do res0, res1 = res1, res0+res1 end
    res1
end

# Nombre de Fibonacci, implémentation récursive terminal
def fibonacci_recursive(n, res0=1, res1=0)
    if n == 0
        res1
    else
        fibonacci_recursive(n-1, res1, res0+res1)
    end
end

La fonction de fibonacci est particulière à bien des égards. L’implémentation naïve, outre le fait de ne pas être terminale, présente le défaut de nous faire calculer de nombreuses fois les mêmes valeurs (par exemple Fibonacci(4) = Fibonacci(3) + Fibonacci(2) et Fibonacci(3) = Fibonacci(2) + Fibonacci(1), donc nous calculons deux fois Fibonacci(2)…)

Ici, l’implémentation récursive terminale apporte beaucoup plus qu’une bonne gestion de la pile d’exécution. C’est souvent le cas. Ceci ne signifie pas qu’il faille systématiquement utiliser des fonctions récursives terminales (par exemple, je trouve plus lisible d’utiliser une syntaxe for each pour parcourir une collection). Mais je crois que l’étude des fonctions terminales est très formatrice, et qu’elle aide les développeurs à concevoir des algorithmes concis et optimaux.

Est-ce que ça marche pour tous les langages ?

Malheureusement non !

En fait, d’un point de vue technique, cela dépend non pas du langage mais du compilateur. Cependant, on peut remarquer que certains langages, tels que F# et OCaml, définissent ce comportement dans leur spécification.

Pour les langages fonctionnels, ne pas optimiser correctement les appels terminaux est généralement considéré comme un bogue. C’est pleinement justifié car ces langages promeuvent l’utilisation de fonctions récursives. En revanche, la chose est plus discutée pour les autres langages. D’ailleurs, nous allons voir que les plateformes Java et .NET ne sont pas très satisfaisantes sur ce point.

Faisons ensemble un petit tour d’horizon parmi les technologies les plus utilisées.

Langage C

La norme C ne dit rien. Mais tous les bons compilateurs (VS, gcc) proposent une option pour effectuer cette optimisation. Voici un extrait de l’aide de gcc, le fameux compilateur C :

-foptimize-sibling-calls
        Optimize sibling and tail recursive calls. Enabled at levels -O2, -O3, -Os.

Notons au passage que le choix des options de compilation est vraiment très important. Beaucoup de programmeurs ont l’habitude de compiler le programme de release avec l’option « -O2 » et de déboguer avec les options « -O0 -g ». Ce faisant on change le comportement du programme et il est possible de provoquer une erreur stack overflow qui n’était pas l’objet des tests.

Plateforme Java

Java pour les nuls

Une des techniques essentielles de Java est l’utilisation d’un langage intermédiaire appelé bytecode Java. Un programmes Java est transformé (traduit, compilé) par le JDK en bytecode Java qui pourra être exécuté (interprété ou compilé à la volée et exécuté) par toutes les JVMs.

Un bytecode est un langage neutre, facile à parser et à projeter sur les architectures courantes. Le bytecode Java est un langage à pile exposant certaines abstractions caractéristique du paradigme objet tels que les appels de méthodes virtuelles et statiques.

L’optimisations des tail calls en Java

Le JDK peut optimiser les fonctions récursives terminales en les transformant en simple boucle. Mais il est beaucoup plus intéressant d’optimiser tous les appels de méthodes terminaux (tail calls) car c’est un cas plus général qui traite aussi la récursivité croisée et la programmation par continuation. Mais le JDK ne peut pas optimiser les tail calls en général car le bytecode Java n’offre pas les instructions nécessaires (on ne manipule pas directement la pile et on ne peut pas faire de jump n’importe où). Ceci ne peut donc être fait que par la JVM lors du chargement des classes.

Dites moi ce dont vous avez besoin et je vous expliquerai comment vous en passer

The Java Language Specification ne dit rien au sujet des tail recursive calls.

Chaque vendeur de Java VM fait ce qu’il veut. La JVM fournie par Sun, qui est de fait l’implémentation de référence, n’effectue pas cette transformation au grand damne des faiseurs de langages dynamiques fondés sur Java (script Groovy, JRuby, etc.)

public class Main {
    public static void main(String[] args) { main(args); }
}

Si vous exécutez le programme ci-dessus sur une JVM de Sun, il se terminera toujours rapidement et lamentablement par une exception Stack Overflow. Heureusement certaines implémentations de Java gère les appels de méthodes terminaux, c’est le cas notamment de la JVM d’IBM.

Sun ne communique pas beaucoup autour de ce sujet. On peut tout de même voir que ce problème est noté en very very very low priority (Votez pour ce bug !) Tant que que Sun/Oracle ne supportera pas officiellement les tail recursive calls, je crains qu’il ne nous faille renoncer à ce type de programmation en Java.

Voici quelques billets très intéressant sur le sujet : java closures controversy, non java languages on jvm et tail calls in the VM.

Plateforme .NET

Pour les mêmes raisons qu’en Java, l’optimisation des tail recursive calls peut être effectuée aussi bien par le compilateur que par la plateforme d’exécution (CLR). En revanche, l’optimisation des tail calls ne peut être effectuée que par le CLR, au moment du chargement des bibliothèques.

L’optimisation des tail calls étant requis pour traiter correctement la récursivité croisée et, plus généralement, les continuations, choses couramment utilisée dans les langages fonctionnels, la plateforme .NET qui se veut être une plateforme multi-langages et multi-paradigmes, doit optimiser correctement les tail calls.

Voici ce que dit la documentation de CIL (le langage intermédiaire commun utilisé par .NET) :

CIL ECMA 335 spec “use a tail. prefix to specify that the current stack frame should be released before transferring control. If the call would transfer control to a method of higher trust than the original method the stack frame will not be released.”

Malheureusement, le comportement de la plateforme .NET de Microsoft est loin d’être satisfaisant. Pour des raisons qui me sont obscures (ordre des paramètres sur la pile, compatibilité binaire avec du code natif, concurrence avec le GC), la plate-forme .NET ne sait pas, en général, optimiser correctement les tail calls.

Voici une liste des conditions requises pour que le JIT du CLR2 effectue une TCO :
http://blogs.msdn.com/davbr/pages/tail-call-jit-conditions.aspx. J’ai été étonné par certaines de ces limitations qui me semblent mal fondées. Microsoft s’est visiblement montré très défensif dans les deux premières versions du CLR.

Concrêtement les comportements du compilateur et de la VM dépendent de l’architecture de la machine. L’implémentation de la CLR pour x86, au lieu d’une savante manipulation, utilise une fonction magique et affreusement lente qui décale le sommet de pile (cf. le dessin au début de l’article). Par conséquent, la plupart des compilateurs .NET ne produisent jamais le préfixe tail. et les compilateurs de langages fonctionnels tels que F# ou parallelC# transforment les fonctions récursives terminales en boucles. Mais il s’agit plus d’un workaround qu’autre chose. En effet cela ne traite pas les cas de co-récursivités et plus généralement de la correcte optimisation d’un programmation écrit par continuation.

L’implémentation pour x64 est meilleure. En générale, tous les arguments d’une fonction peuvent être stockés dans les registres processeurs car ils sont beaucoup plus nombreux sur cette architecture. Grâce à cela, les performances des tail calls sur sont acceptables. Par conséquent, sur x64, le CLR effectue des TCO même quand le prefix tail. n’a pas été spécifié dans le code CIL, si les conditions requises sont réunies…

Microsoft a bien conscience du problème. Un effort significatif a été apporté à l’optimisation des tail calls dans la CLR4 sur x86_64. Maintenant les optimisations faciles sont toujours effectives et, pour les rares cas restant, on utilise la fonction magique dont je parlais tantôt afin de toujours tenir compte du prefix .tail dans le code IL.

Oyez, programmeur. F# fonctionne correctement (enfin) sur CLR4/x86_64 !

Remarquez que l’optimisation correcte des tail calls a été l’occasion pour Microsoft d’améliorer son compilateur en supprimant certaines actions inutiles (copie de buffer de values, etc.) Je me répète sûrement : la récursivité aide les développeurs, mêmes les très bons, à concevoir des algorithmes concis et optimaux.

Python

Guido van Rossum, le créateur et leader du langage de programmation Python a publié un billet horrible où il tente d’expliquer pourquoi les TCO sont le mal et ne devraient surtout jamais être effectuées en Python.

Certains des arguments avancés sont tout simplement faux. Vous trouverez quelques arguments bien construits dans les commentaires de cet autre billet.

Python est un langage qui a été pensé pour être facile à utiliser, et non pas pour produire des programmes rapides. En cela je comprends parfaitement que les TCO ne soient pas une priorité, mais il n’y a aucune raison valable pour s’y opposer par principe.

Ruby

La spécification de Ruby ne dit rien au sujet des tail recursive calls.

Yukihiro Matsumoto (le créateur de Ruby) semble être favorable au TCO, mais, il n’a pas souhaité forcer toutes les implémentations de Ruby à le supporter. Voilà une position qui me semble sage .

YARV, qui est l’interpréteur Ruby officielle, supporte le TCO depuis la version 1.9. Notons que c’est très récent et que l’option, considérée encore instable, est désactivée par défaut (il est nécessaire de commenter une ligne et de recompiler l’interpréteur).

Quant à JRuby et Ruby.NET, ils dépendent évidemment des capacités de la plateforme sous-jacentes..

Ceci signifie que vos programmes Ruby ne devraient pas se fonder sur le TCO, car sinon il ne seront pas portables sur toutes les RubyVM.

Bonjour à tous,

j’ai réalisé un compte rendu des Rencontres Spring 2009 pour le Journal Du Net.
L’événènement était riche en informations, allez faire un tour ici pour le détail.

Java and other mainstreams programming languages rely on shared state concurrency for concurrent programming. Race conditions between different threads are prevented using synchronization structures.
Traditionally in Java synchronized blocks along with wait and notify methods are used but Java 5 introduces new easier concepts.

Still it is quite difficult to implement correctly those patterns and there is no way to prove the code is correct.

New paradigms are slowly introduced intending to simplify or replace locking constructions.
This article will focus on Transactional Memory.

Transactional Memory

Transactional memory is an alternative to lock based synchronization relying on shared states.
This is achieved by applying the concept of transaction and ACID properties to your programming structures. Key points here are Atomicity and Isolation. Concurrent executions effects are equivalent to individual serial executions.

The main idea is to wrap a block of code in a transaction which is committed at the end. Read/write memory accesses can be dealt differently (optimistic/pessimistic locking) depending on concurrency control algorithm. If a conflict is detected during the execution of the atomic block by a thread the whole operation is roll-backed and retried. Details on retries strategies are implementation specific.

Biggest advantage of this technology is simplicity. Programmer doesn’t have to care about how to implement safe concurrent access (dealing with locks, wait..) but only identify which block of code should be treated as atomic.
Better performances are not ensured but correctness is.

More detailed explanation on transactional memory can be found here, here, here and here.

Usage

In most of languages/libraries transactional memory support will be little intrusive by relying on special keyword or meta-data. For language without built-in transactional memory support this can be achieved by using bytecode manipulation.

Regular synchronized block

public void test() {
  synchronized(map1) {
    synchronized(map2) {
      value = map1.remove("key");
      map2.put("key", value+1);
    }
  }
}

Here you have to synchronize modification of 2 structures. This can be hard to correctly implement especially if several methods have to synchronize on the same structure. In this particular sample you have to take a particular care about potential deadlock which might be introduce if you don’t acquire/release locks in the same order.

Transactional memory

@Atomic
public void test() {
  value = map1.remove("key");
  map2.put("key", value+1);
}

Transactional memory ensures that your atomic block of code will be executed atomically. Still there is no magic and you need to identify atomic blocks of code.
Moreover you don’t have to think about locking optimization, which is hard especially when multiple structure access have to be synchronized from different execution path. Because everything is handled by the language (or library) smart optimization might be applied and you are not responsible for this.

This technique does not solve all concurrency problems but certainly helps for some of them. Still you will have to rely on Semaphore, Barrier and other advanced structures for more complex scenarii.

Language support

Haskell

Haskell was the first language to have builtin support for STM. Details can be found here.

Java

Atomic types, locks (Java 5) and Fork/Join (Java 7) are lock-free structures using compare and swap algorithm. Implementation is similar to transactional memory but for a single element. Details about their implementation choice can be found here and here.

To benefit from atomicity capacity you will have to use a full transactional memory implementation.

A number of Java implementation are available:

• DeuceSTM (Annotation based, bytecode instrumentation, TL2 or LSA algorithm, pluggable algorithm, written by Guy Korland from GigaSpaces)
• Multiverse (Annotation based, bytecode instrumentation, Multi Version Concurrency Control algorithm)
• DSTM2 from SUN scalable team (API based, pluggable algorithm)
• JVSTM

Multiverse’s author discusses similarities between TL2 and Multi Version Concurrency Control (MVCC) algorithms .

.Net

Microsoft also provides STM support with STM.NET.

Fortress

Fortress language supports transactional memory as part of its semantic. Current implementation relies on DTSM2 but plan is to switch to Hybrid Transactional Memory (mix of hardware and software implementation) when available.

On top of atomicity, most of fortress syntaxic structures (loop for instance) are executed in parallel by multiple threads. While powerful this introduces complexity as a simple loop adding numbers will have to manipulate atomic structures.

Clojure

Clojure supports STM based on MVCC.

Hardware Transaction Memory

In the near future transactional memory paradigm will be implemented at hardware level providing even better performance. Rock processor from SUN (recently released paper describes HTM features) and Vega 3 from Azul implement it. Other approaches have been documented here and here.

Cons

Transactional memory is not the panacea and some critics (here and here) appeared recently.
Others techniques aiming at facilitating concurrent programming will be discussed later.

Attach API is a powerful technology introduced in SUN JVM starting JDK6. It provides the ability to list local JVMs, get some information about them and dynamically deploy agent based on Instrument API (Java) or JVMTI (native code).

Those agents are becoming quite popular and can be used for profiling and dynamic bytecode manipulation. A growing number of products rely on one of those technologies: JProfiler, Yourkit, JRat, JavaRebel, OpenJPA, BTrace.

Even so you don’t plan to write your own native profiler or instrument classes by modifying bytecode there can be usage of Attach API. Local JVMs can be detected and manipulated without the need of any particular startup option. Most of the tools shipped with the JDK rely on this API (jconsole, jps, jps, jinfo, jstsat,..).

We will see in this article how to leverage this API to start remote JMX connector dynamically on a running JVM.

Platform MBeanServer

JMX technology provides a Java standard to monitor and manage a JVM. Starting Java 5 internals of the JVM are exposed using it in the platform MBeanServer. More details about how it works here.

To access an MBeanServer it must be exported through a connector, most of the time based on RMI. Several MBeanServer can be created in a single JVM but the platform one is always present and there are good chances that you only manipulated this one. More details about dealing with multiples MBeanServer can be found here.

By default the platform MBeanServer is not exported but setting com.sun.management.jmxremote Java property creates a local JMX connector which allows to browse the platform MBeanServer (only from the same machine with the same user).
Note that setting com.sun.management.jmxremote.local.only Java property to false allows to make this connector remotely available but this is to mimic an old behaviour and should not be considered a good practise.

Setting com.sun.management.jmxremote.port to some numerical value will export the platform MBeanServer to a JMX connector accessible from a remote machine.
Because this facility is implemented as a Java agent, tools like JConsole and visualvm can create dynamically this connector using the Attach API. The monitoring agent can be found under JDK_HOME/lib/management-agent.jar.

More information on JMX monitoring can be found here.

Dynamic export of Platform MBeanServer

Using the Attach API to export locally the platform MBeanServer is straight-forward:

final VirtualMachine virtualMachine = VirtualMachine.attach("PID");
final String home = virtualMachine.getSystemProperties().getProperty("java.home");
final String agent = home + File.separator + "lib" + File.separator + "management-agent.jar";
virtualMachine.loadAgent(agent);
virtualMachine.detach();

This can be extended to export it remotely:

final VirtualMachine virtualMachine = VirtualMachine.attach("PID");
final String home = virtualMachine.getSystemProperties().getProperty("java.home");
final String agent = home + File.separator + "lib" + File.separator + "management-agent.jar";
virtualMachine.loadAgent(agent, "com.sun.management.jmxremote.port=5000," +
"com.sun.management.jmxremote.authenticate=false,com.sun.management.jmxremote.ssl=false");
virtualMachine.detach();

Unfortunately this method does not allow to stop the deployed connector. This could be achieved by creating your own agent that would export the platform MBeanServer itself and listen to remote event to offer the unexport ability. Such an option is extensively covered here.

Attach API can be disabled on your JVM by setting -XX:+DisableAttachMechanism Java property. If com.sun.management.jmxremote Java property is not set then  external tool won’t be able to deploy the management agent remotely. This way you forbid access to the platform MBeanServer, even locally.

Extended jps

When the platform MBeanServer is exported with a local connector com.sun.management.jmxremote.localConnectorAddress Java property is set to the corresponding JMX URL value.
When remotely exported the JMX URL will follow the syntax service:jmx:rmi:///jndi/rmi://host:port/jmxrmi where host is the machine where the JVM runs and port is the value of com.sun.management.jmxremote.port Java property .

By using those 2 informations we can create an extended jps which will print local and remote JMX URL is available.

for (final VirtualMachineDescriptor descriptor : VirtualMachine.list()) {
  System.out.print(descriptor.id());
  System.out.println(" "+descriptor.displayName().split(" ")[0]);
  final VirtualMachine virtualMachine = VirtualMachine.attach(descriptor.id());

  final String localConnectorAddress = virtualMachine.getAgentProperties().getProperty("com.sun.management.jmxremote.localConnectorAddress");
  if (localConnectorAddress != null) {
    System.out.println(localConnectorAddress!=null?"    local jmx ("+localConnectorAddress+")":"");
  }
  final String remoteConnectorPort = virtualMachine.getSystemProperties().getProperty("com.sun.management.jmxremote.port");
  if (remoteConnectorPort != null) {
    final String remoteConnectorAddress = "service:jmx:rmi:///jndi/rmi://"+InetAddress.getLocalHost().getHostName()+":"+remoteConnectorPort+"/jmxrmi";
    System.out.println(remoteConnectorAddress!=null?"    remote jmx ("+remoteConnectorAddress+")":"");
  }
  virtualMachine.detach();
}

Note that when dynamically exporting the platform MBeanServer remotely com.sun.management.jmxremote.port Java property will not be set thus we cannot rely on this code to infer the remote JMX service URL.

Unfortunately those techniques only allow to get information on the platform MBeanServer and not other MBeanServer. Even so you can list newly created MBeanServer there is no way to access connectors used to export them.

As part of our consulting activity, we need a tool to help us track performance issues.
A profiler seems to be the perfect suit for this. So I performed a small survey to find the best tool for our needs.

Mainly we are interested in:

• method calls profiling
• threads contentions profiling including with latest java.util.concurrent
• memory snapshot comparison and dynamic memory usage monitoring

Most of available tools are based on instrumentation which might slightly modify performances of your program (known as Heisenbug). For this survey we neglected this impact as main performance issues are still visible when using instrumentation based profiling.

For a more complete description of impacts of instrumentation refer to this discussion.

Here are my remarks regarding some of the main tools available, both commercial and open source.

VisualVM 1.1.1 and Netbeans profiler

• No details on blocked threads.
• History and threads states not useful. (http://profiler.netbeans.org/issues/show_bug.cgi?id=55211)
• No support for java.util.concurrent

Netbeans profiler adds the concept of profiling points and provides integration with source code.
Other concepts are similar.

Yourkit (8.0.13)

• Supports automatic deobfuscation (http://www.yourkit.com/docs/80/help/summary.jsp)
• Keep traces of all exceptions thrown
• No j.u.c support (http://forums.yourkit.com/viewtopic.php?f=2&t=2901). Can be simulated with wall time feature but not easily.

JProfiler (5.2.2)

• Used by our customers.
• Monitor profiling supports java.util.concurrent (reported as blocked threads when waiting).
• Poor documentation.
• No forum.

Appperfect Java Profiler

• Apparently needs a specific agent (only available under Linux?) to profile a remote application.
• Not very clear from documentation.

JRat

• Pretty basic, no dynamic profiling
• Interesting statistics on exception thrown (rates)

dynaTrace

• Apparently demo version not available for France. Didn’t investigate.

JXInsight

• No evaluation version available.
• Didn’t have any answer from sales representative.

So far my tool of choice is JProfiler, mainly because it supports java.util.concurrent features. I would rather switch to Yourkit if this was supported out of the box for the ease of use and exception feature.

Massively concurrent programming will be the future of development. No doubt about that. But manipulating lots of threads sharing resources is not an easy task.
Evenso you managed to make your program correct – and considering the lack of tools or methodology to ensure it this is tricky – you have to take a look at performance.

Using multi thread programming technics is not a garanty to have better performances. Far from it. Recently on customer site I managed to improve performance more than an order of magnitude just by minimizing synchronization cost.

Here are a few simple tips to help you benefit from all your cores:

• Minimize synchronized block length and synchronized method usage
• Replace synchronized keyword by Lock
• Replace Object.wait and Object.notify by Condition
• Limit safe objects usage when not needed (like StringBuffer, old collection implementations)
• Rely on java 5 concurrency features

This last point certainly is the most important. Java 5 introduced lots of concurrency related structures.

Atomic* types allows to manipulate safely primitive like object. Much more efficient than having to synchronize every access to, say, your global statistics. See javadoc for more details.

ConcurrentHashMap, CopyOnWriteArrayList, CopyOnWriteArraySet and others offer safe optimized collection. More lightweight than relying on Collections.synchronized* methods. See javadoc for more details.

New libraries adding more concurrent structures are now available, here are a few:

• http://prometheus.codehaus.org/
• http://high-scale-lib.sourceforge.net/

Interresting new metaphores to split complex tasks into independant subtasks should be added in Java 7.

Salut à tous,
C’est Carole via le compte de Luc…
Article intéressant et simple à comprendre.. )
Enjoy it.
Carole

googlecode.com offers a nice hosting platform for your open source projects. You get SCM (either subversion or mercurial), a wiki, a bug tracker and download facilities.

Here are a few tips to facilitate Maven2 project integration with it (subversion is used as I am not familiar with mercurial yet).

Subversion access configuration

Add those informations in your pom.xml

<scm>
<connection>scm:svn:http://my-project.googlecode.com/svn</connection>
<developerConnection>scm:svn:https://my-project.googlecode.com/svn</developerConnection>
<url>https://my-project.googlecode.com/svn</url>
</scm>

When accessing the subversion repository (for instance while using maven release:prepare and maven release:perform) you must provide googlecode username and password to maven, using command-line parameters

-Dusername=googlecode.username -Dpassword=googlecode.password

or by modifying your settings.xml file

<server>
<!-- Will be used for scm connection -->
<id>googlecode.com</id>
<username>googlecode.username</username>
<password>googlecode.password</password>
</server>

Your googlecode password can be found under source tab of your googlecode.com project website, click on ‘When prompted, enter your generated googlecode.com password.’.

Issue management configuration

Add those informations in your pom.xml

<issueManagement>
<system>Google Code</system>
<url>http://code.google.com/p/my-project/issues/list</url>
</issueManagement>

Repository on subversion configuration

You can rely on googlecode subversion to provide access to your maven artifacts.

Add those informations in your pom.xml

<distributionManagement>
<repository>
<id>my-project-release</id>
<url>dav:https://my-project.googlecode.com/svn/maven2/releases</url>
</repository>
</distributionManagement>

An alternative would be to rely on the subversion wagon implementation as described here.

You will also need to modify your settings.xml file to provide googlecode.com credentials.

<server>
<id>my-project-release</id>
<username>googlecode.username</username>
<password>googlecode.password</password>
</server>

Web pages hosting

If you want to send html/css files to your svn repository and still be able to normally browse them you will have to fix the mime type which is defaulted to ‘text/text’. If you are using subversion you can manually set the mime type with those commands:

svn propset svn:mime-type 'text/html' *.html
svn propset svn:mime-type 'text/css' *.css

In my day to day work at FastConnect I am often dealing with java performance that is mandatory in many of our projects. While digging into my code and java language I found some tips that helped us to perform better. I decided to share some of them with you in this article.

Note that these tips are various, some of them are quite extreme and can create a code complication that is not always welcome. Thus they must be used carefully and only when it is really required. Some other on the other way can also help to reach as well as performance an easier readability. Note that as always a good documentation and structure is necessary to make the overall comprehensible.

Limit Object creations

One aspect that can be easily implemented and that can help in frequently called scenarios is to limit the creation of Objects. As you know creating an Object requires first the JVM to allocate space for it and perform all the linking operations and second to manage this object in the garbage collection process, these two operations can have performance impact when dealing with frequent short-lived object creation.See the following example:

package fr.fastconnect.java.performance;

public class ObjectCreationOverheadDemo {
	/* Static fields and methods */
	/**
	 * 10.000.000
	 */
	private final static int ITERATIONS=10000000;

	public static void main(String[] args) {
		// launch a first test with both and no mesurement to not take
		// JVM initialisations in the measurement
		executeWithNewObject();
		executeWithExistingObject();
		// perform test and measure performance
		long start = System.currentTimeMillis();
		executeWithNewObject();
		long duration = System.currentTimeMillis()-start;
		System.out.println("Duration with new object creation : " + duration);
		start = System.currentTimeMillis();
		executeWithExistingObject();
		duration = System.currentTimeMillis()-start;
		System.out.println("Duration with single object       : " + duration);
	}

	private static void executeWithNewObject() {
		for(int i=0;i<ITERATIONS;i++) {
			ObjectCreationOverheadDemo demoObject = new ObjectCreationOverheadDemo();
			demoObject.intValue = i;
			demoObject.longValue = i;
			/*.. Application usage of the object ..*/
		}
	}

	private static void executeWithExistingObject() {
		ObjectCreationOverheadDemo demoObject = new ObjectCreationOverheadDemo();
		for(int i=0;i<ITERATIONS;i++) {
			demoObject.intValue = i;
			demoObject.longValue = i;
			/*.. Application usage of the object ..*/
		}
	}

	/*
	 * Object fields
	 */
	private int intValue;
	private long longValue;
}

Running the test on my machine I got the following output that confirm the impact of object creation.

Duration with new object creation : 174
Duration with single object : 26

Note that in this situation this is small objects and if the impact exist it is in fact very small. Indeed a few millisecond for so many iterations may seems limited. However think on the impact with bigger objects, I’m thinking on the impact on garbage collection mainly.

Working with String:

Java String methods are very fast, however a bad usage of String features can have a very heavy impact on your program performance.

String concatenation

When you are performing multiple string concatenations, try to use a StringBuilder instead of a ‘+’ between the two strings. StringBuilder class is the ultimate optimized solution to append a string to another.

package fr.fastconnect.java.performance;

public class StringConcatenationDemo {
	/* Static fields and methods */
	/**
	 * 10.000
	 */
	private final static int ITERATIONS=10000;
	private final static String strToAppend = "Str To Append";

	public static void main(String[] args) {
		// launch a first test with both and no mesurement
		// to not take JVM initialisations in the measurement
		executeStringPlus();
		executeStringBuilder();
		// perform test and measure performance
		long start = System.currentTimeMillis();
		String strPlusResult = executeStringPlus();
		long duration = System.currentTimeMillis()-start;
		System.out.println("Duration with '+' concatenation : " + duration);
		start = System.currentTimeMillis();
		String strBuilderResult = executeStringBuilder();
		duration = System.currentTimeMillis()-start;
		System.out.println("Duration with StringBuilder     : " + duration);
		System.out.println("String are the same : "+strPlusResult.equals(strBuilderResult));
	}

	private static String executeStringPlus() {
		String resultString="";
		for(int i=0;i<ITERATIONS;i++) {
			resultString += strToAppend;
		}
		return resultString;
	}

	private static String executeStringBuilder() {
		StringBuilder strBuilder = new StringBuilder();
		for(int i=0;i<ITERATIONS;i++) {
			strBuilder.append(strToAppend);
		}
		return strBuilder.toString();
	}
}

Running this example on my machine I got the following output:
Duration with ‘+’ concatenation : 7685
Duration with StringBuilder : 7
String are the same : true

Here again the benefit impact of StringBuilder is clear.

getBytes vs custom implementation

getBytes method in java is quite slow. This is related mainly to char encoding parameters and validations. In certain circonstances where encoding is the same on every machine and doesn’t cause issues, we can use an optimised custom implementation:

package fr.fastconnect.java.performance;

import java.util.Arrays;

public class StringGetBytesDemo {
	/* Static fields and methods */
	/**
	 * 10.000
	 */
	private final static int ITERATIONS=100000;
	private final static String str = "String to get bytes from";

	public static void main(String[] args) {
		// launch a first test with both and no mesurement
		// to not take JVM initialisations in the measurement
		execute();
		executeCustom();
		// perform test and measure performance
		long start = System.currentTimeMillis();
		byte[] bytes = execute();
		long duration = System.currentTimeMillis()-start;
		System.out.println("Duration with getBytes : " + duration);
		start = System.currentTimeMillis();
		byte[] bytesCustom = executeCustom();
		duration = System.currentTimeMillis()-start;
		System.out.println("Duration with custom impl     : " + duration);
		System.out.println("byte arrays are the same : "+Arrays.equals(bytes, bytesCustom));
	}

	private static byte[] execute() {
		for(int i=0;i<ITERATIONS-1;i++) {
			str.getBytes();
		}
		return str.getBytes();
	}

	private static byte[] executeCustom() {
		for(int i=0;i<ITERATIONS-1;i++) {
			char buffer[] = new char[str.length()];
			int length = str.length();
			str.getChars(0, length, buffer, 0);
			byte b[] = new byte[length];
			for (int j = 0; j < length; j++) {
				b[j] = (byte) buffer[j];
			}
		}
		char buffer[] = new char[str.length()];
		int length = str.length();
		str.getChars(0, length, buffer, 0);
		byte b[] = new byte[length];
		for (int j = 0; j < length; j++) {
			b[j] = (byte) buffer[j];
		}
		return b;
	}
}

Note that in many cases the java getBytes and custom method will just produce the exact same byte array. This is something you must check in your tests (providing a switch to use one or the other can also be a good idea).
Duration with getBytes : 74
Duration with custom impl : 15
byte arrays are the same : true

Serialization tips

In many situations serialization can be costly as well in term of size and as well performance. This is linked as IO operations are related to size of data, and serialization’s goal is as you know to be able to send data on an IO channel.
In such situation when performance is a must it may be useful to use a custom serialization.

Use Externalizable

To enable custom serialization for your object, you must implements the Externalizable interface. This interface will provide you 2 methods writeExternal and readExternal that will allow you to deal by yourself with the object serialization.
When using the native java serialisation on your objects, java will therefore use your Externalizable method instead of native serialization process.
Be careful to use this only if the custom serialization has better performance or footprint than the java classic serialization. This is mostly the case on objects that have complex fields and not only primitive.

Create byte array on your own

In some really extreme situations you may want to go even deeper in the performance optimization and create by yourself a byte array that you will use for writing to a network or file stream. (Or basically any stream). Indeed classic java serialization save some class meta-datas. All this overhead can be avoided by creating a custom byte-array. Using custom byte array creation allow also to perform custom batching etc. Basically this is really powerful but has also an impact on code readability. Thus such implementation must be used carefully, be well documented and must use methods with explicit names.

Try to size your data to avoid buffer resizing

When java developer want to create a byte array (serializing data dealing with various buffer…), the most common used class is the ByteArrayOutputStream. this object allow you to write bytes to a stream and to store it in a byte array. The big point with it is that the goal of it is too be able to resize this array anytime if you keep putting data in it. However as explained before the ByteArrayOutputStream can be costly because of ArrayCopy. If you are able to size the data correctly, or if you can send the data by chunk from a defined size, I encourage you to use the ByteBuffer class that will perform a lot better! It will bring however the constraint of not resizing the byte array.

When working directly with more deep layer native networking etc., it is even possible to create the ByteBuffer in the native heap! This will be even more faster to just put data in it as well as to send to network layer but you won’t be able to get any backing byte array back in you java application!! Also this kind of buffer use Native memory and will not be controlled by the heap so be even more careful regarding memory leaks

Multithreading:

Avoid thread common variables and synchronization of resources

When you can do it try to avoid sharing any ‘thread common variables’. When you use a buffer for example try to create one per thread, even if you have to merge them at the end. To do so you can ether use ThreadLocal variables or even better just use full different instances (when you use spring remember that if singleton is the default object scope, using prototypes can be sometimes a better approach). Even if this sounds basic, keep it in mind: achieving a performing multithreaded implementation can be done only with the very minimum synchronization points.

Queue instead of synchronize

When your process can be done asyncronously and you have a synchronization point then queue your process (java.util.concurrent.BlockingQueue) and use a single consumer. This will allow that you don’t block all other thread because of this synchronization point and can help to make your application perform better. If you are afraid that the queue can grow too much don’t worry: BlockingQueue can limit the size of the queue. When this size will be reached then you will pay for the synchronization… Anyway in many situation this can help

Use optimized concurrent classes

Use the java concurrent package that contains many Collections and tools that contains high performance implementations for concurrency scenario. This package contains lot of very useful classes that will perform a lot better than other implementations or custom basic synchronized.

Links

http://java.sun.com/developer/technicalArticles/Programming/Performance/

This list is of course not exhaustive and I invite each of you to comment the article and add your tips