vendredi 30 octobre 2009

ThreadLocal

La classe ThreadLocal (java.lang.ThreadLocal) permet d'implanter un singleton par thread.


Il est possible d'utiliser des objets instances d'une classe non synchronisée dans un environnement multi-thread si on s'assure que chaque instance n'est utilisée que par un unique thread.

Par exemple, un objet Connection (java.sql.Connection) n'est pas thread-safe. Un même objet Connection ne doit donc pas être manipulé par différents threads. Mais si chaque thread possède son propre objet Connection, ils peuvent effectuer des requêtes simultanées de manière sûre. La classe ThreadLocal permet d'obtenir un unique objet (un singleton) par thread.

Un excellent article sur le sujet a été rédigé par Brian Goetz : Threading lightly, Part 3: Sometimes it's best not to share

Dans les exemples ci-dessous, on utilise un objet Counter pour numéroter des objets. La classe Counter est très simple et non synchronisée.

class Counter{
    private int next = 1;

    public int next(){
        return next++;
    }
}


Pour les besoins des exemples, on se dote d'une classe qui étend la classe Thread (java.lang.Thread). Elle permet d'afficher sur la sortie standard un certain nombre d'objets qu'elle instancie par introspection. Elle préfixe chaque trace par son nom.


class PrintNewObjectThread extends Thread{
    private Class aClass;
    private int nbPrint;

    public PrintNewObjectThread(String name, Class aClass, int nbPrint) {
        super(name);
        this.aClass = aClass;
        this.nbPrint = nbPrint;
    }

    @Override
    public void run() {
        for(int i = 0 ; i < nbPrint ; i++){
            try {
                System.out.println(getName() + ":" + aClass.newInstance());
            } catch (InstantiationException e) {
                e.printStackTrace();
            } catch (IllegalAccessException e) {
                e.printStackTrace();
            }
        }
    }
}
Le premier exemple utilise un CountedObject, une classe non synchronisée. Cette classe encapsule un objet Counter de manière statique pour numéroter chaque nouvelle instance.
class CountedObject{
    private static final Counter COUNTER = new Counter();
    private int number = COUNTER.next();

    public String toString() {
        return "Object #" + number;
    }
}
Le second exemple utilise un CountedPerThreadObject, une classe non synchronisée. Cette classe est semblable à la classe CountedObject mais encapsule de manière statique un objet ThreadLocal. La classe interne qui étend ThreadLocal est chargée d'instancier un objet Counter par thread.
class CountedPerThreadObject{
    private static final ThreadLocal COUNTER = new ThreadLocal(){
        protected Counter initialValue() {
            return new Counter();
        }
    };

    private int number = COUNTER.get().next();

    public String toString() {
        return "Object #" + number;
    }
}
Le programme ThreadLocalExemple exécute les deux exemples. L'exemple 1 lance deux threads chargés d'afficher des objets CountedObject, l'exemple 2 lance deux threads chargés d'afficher des objets CountedPerThreadObject.
public class ThreadLocalExemple {
    public static void main(String[] args) throws Exception {
        exemple1();
        exemple2();
    }

    private static void exemple1() throws Exception{
        System.out.println("Exemple 1");
        System.out.println("=========");
        Thread t1 = new PrintNewObjectThread("t1", CountedObject.class, 5);
        Thread t2 = new PrintNewObjectThread("t2", CountedObject.class, 5);
        t1.start();
        t2.start();
        t1.join();
        t2.join();
        System.out.println();
    }

    private static void exemple2() throws Exception{
        System.out.println("Exemple 2");
        System.out.println("=========");
        Thread t1 = new PrintNewObjectThread("t1", CountedPerThreadObject.class, 5);
        Thread t2 = new PrintNewObjectThread("t2", CountedPerThreadObject.class, 5);
        t1.start();
        t2.start();
        t1.join();
        t2.join();
        System.out.println();
    }
}
Le résultat, l'exemple 1 affiche des objets numérotés indépendamment des threads qui les créent, l'exemple 2 affiche des objets numérotés par thread.
Exemple 1
=========
t1:Object #1
t1:Object #2
t1:Object #3
t1:Object #4
t1:Object #5
t2:Object #6
t2:Object #7
t2:Object #8
t2:Object #9
t2:Object #10

Exemple 2
=========
t1:Object #1
t1:Object #2
t1:Object #3
t1:Object #4
t1:Object #5
t2:Object #1
t2:Object #2
t2:Object #3
t2:Object #4
t2:Object #5
OK, on observe bien l'effet singleton par thread lorsque l'on introduit un objet LocalThread. Mais les deux exemples sont-ils pour autant thread-safe ?
Les threads qui sont exécutés affichent des objets (CountedObject dans l'exemple 1 et CountedPerThreadObject dans l'exemple 2) qu'ils ne partagent pas, mais ces objets modifient un membre privé et statique dans leur constructeur. Dans les deux exemples, l'objet modifié est de type Counter.
L'exemple 2 utilise un ThreadLocal qui garanti un objet Counter par thread, chaque objet Counter ne sera jamais accédé en concurrence. L'exemple 2 est donc thread-safe.
Dans l'exemple 1, les threads partagent un unique objet Counter et le modifient en parallèle un créant des objets CountedObject. L'objet Counter voit sont état modifié chaque fois qu'un objet CountedObject invoque sa méthode next() durant sa création. L'instruction next++ exécutée par la méthode next() n'est pas atomique, elle correspond à deux instructions atomiques : l'addition de next avec l'incrément 1 et l'affectation du résultat de l'addition à next. L'exemple 1 n'est donc pas thread-safe.
Pour que l'exemple 1 soit thread-safe, la méthode next() de la classe Counter doit être synchrosisée.
class Counter{
    private int next = 1;

    public synchronized int next(){
        return next++;
    }
}
Attention, "la classe LocalThread permet d'obtenir un objet singleton par thread" ne signifie pas que l'objet est lui-même un singleton. Au contraire, cela ruinerait l'avantage de l'utilisation d'un ThreadLocal. Imaginons la classe Counter rédigée de la manière suivante.
class Counter{
    private static final Counter singleton = new Counter();
    private int next = 1;

    public static Counter getInstance() {
        return singleton;
    }

    private Counter() {
    }

    public synchronized int next(){
        return next++;
    }
}
La classe CountedObject ou la classe interne ThreadLocal de CountedPerThreadObject ne pourraient obtenir que l'unique singleton Counter via la méthode statique getInstance(). Voici alors la trace que nous obtiendrions.
Exemple 1
=========
t1:Object #1
t1:Object #3
t1:Object #4
t1:Object #5
t1:Object #6
t2:Object #2
t2:Object #7
t2:Object #8
t2:Object #9
t2:Object #10

Exemple 2
=========
t1:Object #11
t1:Object #13
t1:Object #14
t1:Object #15
t1:Object #16
t2:Object #12
t2:Object #17
t2:Object #18
t2:Object #19
t2:Object #20
Dans ce cas de figure, tous les objets partagent le même objet Counter, qu'ils soient de type CountedObject ou CountedPerThreadObject. L'objet LocalThread de la classe CountedPerThreadObject gère une référence par thread pointant sur le même objet Counter.
Liens externes :

jeudi 29 octobre 2009

StringCharacterIterator

La classe StringCharacterIterator (java.text.StringCharacterIterator) est utile lorsque l'on nécessite de parcourir les caractères d'une chaîne. Cette classe implante l'interface CharacterIterator (java.text.CharacterIterator) qui définit un protocole pour itérer de manière bidirectionnele au travers d'un texte.

Un objet de classe StringCharacterIterator s'instancie en confiant un objet de classe String (java.lang.String) à l'un des constructeur de la classe.

CharacterIterator ci = new StringCharacterIterator("Hello world");
traverseForward(ci);
traverseBackward(ci);

Une instance d'une classe CharacterIterator peut ensuite parcourir le texte depuis une position jusqu'à la fin ou jusqu'au début du texte avec les méthodes next() et previous(). Lorsqu'une extrémité de la chaîne est atteinte, ces méthodes retournent le caractère CharacterIterator.DONE. Les deux exemples qui suivent sont issus de la page Javadoc documentant l'inteface CharacterIterator.

public void traverseForward(CharacterIterator iter) {
     for(char c = iter.first(); c != CharacterIterator.DONE; c = iter.next()) {
         processChar(c);
     }
}

public void traverseBackward(CharacterIterator iter) {
     for(char c = iter.last(); c != CharacterIterator.DONE; c = iter.previous()) {
         processChar(c);
     }
}

Liens externes :

StringBuffer vs StringBuilder

La classe StringBuffer (java.lang.StringBuffer) est présente dans le JDK (Java Development Kit) depuis sa première version. Les objets de classe StringBuffer permettent de construire des chaînes de caractères avec des performances nettement supérieures à la construction des chaînes de caractères par concaténation de chaînes prémisses.

Le spécification Java SE 5 introduit la classe StringBuilder (java.lang.StringBuilder) proposant un service comparable et une interface similaire à celle de la classe StringBuffer. 

Les méthodes de la classe StringBuffer sont synchronisées tandis que celle des StringBuilder ne le sont pas. Ainsi les objets de classe StringBuilder sont sensiblement plus performant que les objets de classe StringBuffer mais ne doivent pas être modifiés de manière concurrente par différents threads.

Il reste rare qu'un StringBuffer soit modifié en parallèle dans les applications et il est conseillé d'opter pour un objet de classe StringBuilder lorsque c'est possible. Quant aux codes sources existants, la similitude des interfaces des classes StringBuffer et StringBuilder permet un remaniement du code sans douleur.

Le programme ci-dessous donne un exemple de différence des performances entre les objets de classe StringBuffer et ceux de classe StringBuilder.

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        for(int i = 0 ; i < 3 ; i++){
            System.out.print("Waiting StringBufferTechnic ... ");
            main.buildStringWithStringBufferTechnic();
            System.out.print(" : ");
            main.printChrono();

            System.out.print("Waiting StringBuilderTechnic ...");
            main.buildStringWithStringBuilderTechnic();
            System.out.print(" : ");
            main.printChrono();

            System.out.println();
        }
    }

    private static final int LOOPS = 6000000;
    private static final int A_OFFSET = (int)'A';
    private static final int MODULO = 26; // Nb caractères dans l'alphabet
    
    // Gestion du chrono
    private long time;

    private void start() {
        Runtime.getRuntime().gc();
        this.time = System.currentTimeMillis();
    }

    private void stop() {
        time = System.currentTimeMillis() - time;
    }

    public void printChrono(){
        System.out.println(time + " ms");
    }

    // Méthodes de construction de chaînes

    public String buildStringWithStringBufferTechnic(){
        start();
        StringBuffer sb = new StringBuffer();
        for(int i = 0 ; i < LOOPS ; i++){
            sb.append((char)(i%MODULO)+A_OFFSET);
        }
        String s = sb.toString();
        stop();
        return s;
    }

    public String buildStringWithStringBuilderTechnic(){
        start();
        StringBuilder sb = new StringBuilder();
        for(int i = 0 ; i < LOOPS ; i++){
            sb.append( (char)(i%MODULO)+A_OFFSET );
        }
        String s = sb.toString();
        stop();
        return s;
    }
}
Ci-dessous, un exemple d'exécution de ce programme.
Waiting StringBufferTechnic ...  : 907 ms
Waiting StringBuilderTechnic ... : 453 ms

Waiting StringBufferTechnic ...  : 812 ms
Waiting StringBuilderTechnic ... : 453 ms

Waiting StringBufferTechnic ...  : 844 ms
Waiting StringBuilderTechnic ... : 453 ms
Liens externes :

lundi 12 octobre 2009

Calcul du montant des intérêts annuels générés par un LDD

J'ai ouvert l'année passée (2008) un LDD (Livret à Développement Durable). Ma banque vient de me fournir le montant des intérêts cumulés sur ce compte.

Après quelques efforts pour comprendre le calcul de ces intérêts, je suis parvenu à retrouver le montant qui m'a été versé.

Ci-dessous, le détail du calcul à effectuer pour calculer les intérêts 2008 d'un LDD.

Mouvements effectués sur le LDD

Date Valeur

Dépensé

Reçu

Solde

Commentaire

01/05/2008

 

4000.00 €

4000.00 

Création LDD

15/07/2008

2500.00 

 

1500.00 

 

15/09/2008

400.00 

 

1100.00 

 

30/11/2008

200.00 

 

900.00 

 

30/11/2008

500.00 

 

400.00 

 

31/12/2008

 

49.35 €

449.35 €

Intérêts

Taux d'intérêt LDD

Mois

Taux

janvier 2008

3.0 %

février 2008

3.5 %

août 2008

4.0 %

février 2009

2.5 %

Calcul des intérêts du LDD en 2008

Le montant des intérêts annuel est la somme des intérêts calculés chaque quinzaine. Une année comporte 24 quinzaines (2 quinzaines/mois). 

Calcul des intérêts d'une quinzaine : Capital en fin de quinzaine x Taux d'intérêt applicable à la quinzaine / 24


Mois/2008

Quinzaine

Solde

Taux

Intérêts quinzaine

Intérêts cumulés

janvier

1

0.00 €

3.00 %

0.00 €

0.00 €

janvier

2

0.00 €

3.00 %

0.00 €

0.00 €

février

1

0.00 €

3.50 %

0.00 €

0.00 €

février

2

0.00 €

3.50 %

0.00 €

0.00 €

mars

1

0.00 €

3.50 %

0.00 €

0.00 €

mars

2

0.00 €

3.50 %

0.00 €

0.00 €

avril

1

0.00 €

3.50 %

0.00 €

0.00 €

avril

2

0.00 €

3.50 %

0.00 €

0.00 €

mai

1

4000.00 €

3.50 %

5.83 €

5.83 €

mai

2

4000.00 €

3.50 %

5.83 €

11.67 €

juin

1

4000.00 €

3.50 %

5.83 €

17.50 €

juin

2

4000.00 €

3.50 %

5.83 €

23.33 €

juillet

1

4000.00 €

3.50 %

5.83 €

29.17 €

juillet

2

1500.00 €

3.50 %

2.19 €

31.35 €

août

1

1500.00 €

4.00 %

2.50 €

33.85 €

août

2

1500.00 €

4.00 %

2.50 €

36.35 €

septembre

1

1500.00 €

4.00 %

2.50 €

38.85 €

septembre

2

1100.00 €

4.00 %

1.83 €

40.69 €

octobre

1

1100.00 €

4.00 %

1.83 €

42.52 €

octobre

2

1100.00 €

4.00 %

1.83 €

44.35 €

novembre

1 

1100.00 €

4.00 %

1.83 €

46.19 €

novembre

2

1100.00 €

4.00 %

1.83 €

48.02 €

décembre

1

400.00 €

4.00 %

0.67 €

48.69 €

décembre

2

400.00 €

4.00 %

0.67 €

49.35 €

 

 


mardi 29 septembre 2009

Dijkstra, Hoare

Dijkstra, Hoare







Weakest Predicate de Dijkstra : wp(S, Q) la précondition la plus faible de S par rapport à Q ; décrit tous les états initiaux tels qu'une exécution de S qui débute dans un de ces états termine OBLIGATOIREMENT dans l'état Q.


Triplet de Hoare : {P}S{Q} où P est une pré-condition, S un programme (une séquence d'instructions) et Q une post-condition.

{P}S{Q} = (P & wp(S, true) --> wp(S, Q))


Affectation

Dijkstra

P = wp(x := E, Q)
= Q[x <-- E]

Hoare


AFF1 -------------------------
{Q[x <-- E]} x := E {Q}

AFF2 --------------------------------------------
{P} x := E {P[x <-- x0] & x = E[x <-- x0]}

Exemple

P = wp(S,Q) avec
S = i := i - 1
Q = i = 0

P = wp(i := i - 1, i = 0)
= (i = 0)[i <-- i - 1]
= (i - 1 = 0)
= (i = 1)


--------------------------
{i = 1} i := i - 1 {i = 0}

Composition séquentielle

Dijkstra

P = wp(S1 ; S2, R)
= wp(S1, wp(S2, R))

Hoare


{P} S1 {Q} {Q} S2 {R}
SEQ -----------------------
{P} S1 ; S2 {R}

Exemple

P = wp(S, P) avec
S = a := 0 ; b := x
Q = a + b >= 0

P = wp(a:= 0 ; b := x, a + b >= 0)
= wp(a := 0, wp(b := x, a + b >= 0) = wp(a := 0, (a + b >= 0)[b <-- x])
= wp(a := 0, a + x >= 0) = (a + x >= 0)[a <-- 0]
= (0 + x >= 0)


AFF1 -------------------------------- -------------------------------- AFF1
{0 + x >= 0} a := 0 {a + x >= 0} {a + x >= 0} b := x {a + b >= 0}
SEQ -------------------------------------------------------------------
{0 + x >= 0} a := 0 ; b := x {a + b >= 0}

Règle de conséquence

Hoare


P --> P' {P'} C {Q'} Q' --> Q
CONSEQ -------------------------------
{P} C {Q}

Exemple

Prouver la correction du triplet {P}S{Q} avec
P = x >= 0
S = a := 0 ; b := x
Q = a >= -b

AFF1 -------------------------------- -------------------------------- AFF1
{0 + x >= 0} a := 0 {a + x >= 0} {a + x >= 0} b := x {a + b >= 0}
SEQ ------------------------------------------------------------------
x >= 0 --> 0 + x >= 0 {0 + x >= 0} a := 0 ; b := x {a + b >= 0} a + b >= 0 --> a >= -b
CONSEQ --------------------------------------------------------------------------------------
{x >= 0} a := 0 ; b := x {a >= -b}


On peut vérifier P --> P' avec
P' = wp(S, Q)

P' = wp(S, Q)
= wp(a := 0 ; b := x, a >= -b)
= wp(a := 0, wp(b := x, a >= -b)) = wp(a := 0, (a >= -b)[b <-- x])
= wp(a := 0, a >= -x) = (a >= -x)[a <-- 0]
= (0 >= -x)

P --> P' = (0 >= -x --> x >=0) = true

Instruction conditionnelle

Dijkstra

P = wp(if B then S1 else S2, Q)
= B --> wp(S1, Q) & ~P --> wp(S2, Q)

Hoare


{P & B} S1 {Q} {P & ~B} S2 {Q}
COND ---------------------------------
{P} if B then S1 else S2 {Q}

Exemple

P = wp(S, Q) avec
S = if y = 0 then x := y else x := 0
Q = x = 0

P = wp(if y = 0 then x := y else x := 0, x = 0)
= (y = 0 -> wp(x := y, x = 0)) & (~(y = 0) --> wp(x := 0, x = 0))
= (y = 0 --> 0 = Y) & (~(y = 0) --> 0 = 0)
= true & &true
= true


---------------------------------------------------- AFF1
(true & ~(y = 0)) --> (0 = 0) {0 = 0} x := 0 {x = 0}
AFF1 ----------------------------- ---------------------------------------------------- CONSEQ
{true & y = 0} x := y {x = 0} {true & ~(y = 0)} x := 0 {x = 0}
COND ---------------------------------------------------------------------------
{true} if y = 0 then x := y else x := 0 {x = 0}

Boucles

Hoare


{P & B} S {P}
WHILE --------------------------------


{P} while B do S done {P & ~B}




Note : Cette règle de correction partielle ne garantit pas la terminaison de S (cf. Correction totale).

Exemple

-------------------------------- AFF
(x >= 0 & x < b) --> x + 1 >= 0 {x + 1 >= 0} x := x + 1 {x >= 0}
CONSEQ -----------------------------------------------------------------
{x >= 0 & x < b} x := x + 1 {x >= 0}
WHILE ----------------------------------------------------------------
{x >= 0} while x < b do x := x + 1 done {x >= 0 & ~(x < b)}


Correction totale

Dijkstra

P = wp(while B do S end, Q)

P(0) = ~B & Q S n'est pas exécuté
P(1) = B & wp(S, P(0)) S est exécuté une fois et après Q est établie
...
P(k) = B & wp(S, P(k - 1))

et donc
P = wp(while B do S end, Q) = 'E'k >= 0 : P(k)

Hoare



{P & B & (E = n)} C {P & E < n & E >= 0}
WHILET ------------------------------------------
{P} while B do C done {P & ~B}




Crédit image : Wikipedia, http://en.wikipedia.org/wiki/Hoare_logic