Kotlin + Brainfuck : efficacité, compacité, optimisation

Où l'on teste Kotlin (par rapport à Java) et où l'on essaie de faire efficace

L’une des prétentions de Kotlin, c’est grosso merdo d’être une version moderne et efficace (= sans boilerplate code) de Java.

On va tester ça avec un interpréteur BrainFuck.

La version simple

Le but du jeu est de faire le plus simple possible :

  1. Interprétation bête et méchante du code Brainfuck.
  2. Le code est lu dans un fichier externe dont le chemin est passé en argument.
  3. Si le code BF est pété, le programme fera n’importe quoi (pas de vérification d’intégrité).
  4. Interpréteur BF à 30 000 case mémoire et mots de 16 bits, fixe.

Les points 2, 3 et 4 sont conservés sur toutes les versions.

Le programme Kotlin complet, lecture du fichier inclus.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
package fr.spacefox.brainfuck

import java.io.File
import java.io.IOException
import java.io.InputStreamReader
import kotlin.system.measureTimeMillis

class SimpleBrainFuck(val program: CharArray) {

    private val ram = IntArray(30000)
    private val inputReader = InputStreamReader(System.`in`)

    fun run() {
        var ramPtr = 0
        var programPtr = 0

        do {
            when (program[programPtr]) {
                '>' -> ramPtr++
                '<' -> ramPtr--
                '+' -> ram[ramPtr] = (ram[ramPtr] + 1) % 0xFFFF
                '-' -> ram[ramPtr] = (ram[ramPtr] - 1) % 0xFFFF
                '[' -> if (ram[ramPtr] == 0) programPtr = jump(programPtr, 1)
                ']' -> if (ram[ramPtr] != 0) programPtr = jump(programPtr, -1)
                '.' -> print(ram[ramPtr].toChar())
                ',' -> ram[ramPtr] = try { inputReader.read() } catch (e: IOException) { 0 }
            }
            programPtr++
        } while (programPtr < program.size)
    }

    private fun jump(programPtr: Int, step: Int): Int {
        var i = programPtr
        var loops = 1
        while (loops > 0) {
            i += step
            when (program[i]) {
                '[' -> loops += step
                ']' -> loops -= step
            }
        }
        return i
    }
}

fun main(args: Array<String>) {
    val time = measureTimeMillis { SimpleBrainFuck(File(args[0]).readText().toCharArray()).run() }
    println("Completed in $time ms")
}

On remarque que c’est compact : 49 lignes sans jamais dépasser les 100 caractères par ligne. La lecture du fichier est d’une simplicité impressionnante par rapport aux montages qu’imposent les (vieilles versions de) Java !

Le « formatage standard » aide aussi, des choses comme if (ram[ramPtr] == 0) programPtr = jump(programPtr, 1) qui sont très déconseillées en Java le sont moins en Kotlin.

Métriques sur un « Intel(R) Core(TM) i5-3570K CPU @ 3.40GHz »

  • Hello World : ~4 ms. ← Programme ultra-simple.
  • Tours de Hanoï : 38,8 s ← Programme généré et complètement sous-optimal, donc très optimisable par un interpréteur « intelligent ».
  • Fractale : 85,5 s ← Programme très calculatoire et beaucoup plus complexe à optimiser.

Des optimisations basiques

Bon, ça fonctionne, mais c’est très lent sur les gros programmes. On évalue tous les caractères, commentaires compris, et on passe un temps fou à rechercher les correspondances de saut, qui sont fixes parce que Brainfuck n’est pas auto-modifiant. Donc on va faire quelques améliorations basiques :

  1. Lignes 10 à 12 : on filtre le programme en entrée pour dégager tous les commentaires (pour éviter qu’ils arrivent dans la boucle d’exécution). C’est un montage sur une possibilité de Kotlin avec le constructeur par défaut de la ligne 10, qui prends maintenant un String, qui est utilisé dans la création du champ program.
  2. Lignes 15, 37, 47 et 49 : on ajoute un cache de correspondance des sauts. Une Map serait peut-être plus efficace en mémoire, mais les programmes sont dans le pire des cas tellement petits par rapport à la RAM disponible que c’est beaucoup plus efficace d’utiliser un tableau de la taille du programme (sans les commentaires). En fait, la version avec Map (non représentée ici) est aussi lente que la version « naïve » précédente !
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
package fr.spacefox.brainfuck

import java.io.File
import java.io.IOException
import java.io.InputStreamReader
import kotlin.system.measureTimeMillis

class IntermediateBrainFuck(strProgram: String) {

    private val program: CharArray = strProgram
            .filter { it in listOf('+', '-', '>', '<', '[', ']', '.', ',') }
            .toCharArray()
    private val ram = IntArray(30000)
    private val inputReader = InputStreamReader(System.`in`)
    private val jumpCache: IntArray = IntArray(strProgram.length)

    fun run() {
        var ramPtr = 0
        var programPtr = 0

        do {
            when (program[programPtr]) {
                '>' -> ramPtr++
                '<' -> ramPtr--
                '+' -> ram[ramPtr] = (ram[ramPtr] + 1) % 0xFFFF
                '-' -> ram[ramPtr] = (ram[ramPtr] - 1) % 0xFFFF
                '[' -> if (ram[ramPtr] == 0) programPtr = jump(programPtr, 1)
                ']' -> if (ram[ramPtr] != 0) programPtr = jump(programPtr, -1)
                '.' -> print(ram[ramPtr].toChar())
                ',' -> ram[ramPtr] = try { inputReader.read() } catch (e: IOException) { 0 }
            }
            programPtr++
        } while (programPtr < program.size)
    }

    private fun jump(instructionPtr: Int, step: Int): Int {
        if (jumpCache[instructionPtr] == 0) {
            var i = instructionPtr
            var loops = 1
            while (loops > 0) {
                i += step
                when (program[i]) {
                    '[' -> loops += step
                    ']' -> loops -= step
                }
            }
            jumpCache[instructionPtr] = i
        }
        return jumpCache[instructionPtr]
    }
}

fun main(args: Array<String>) {
    val time = measureTimeMillis { IntermediateBrainFuck(File(args[0]).readText()).run() }
    println("Completed in $time ms")
}

Métriques :

  • Hello world : 25 ms. C’est beaucoup plus lent, mais comme on compte en millisecondes, ça reste virtuellement instantané.
  • Tours de Hanoï : 25 s.
  • Fractale : 45 s. Rien qu’en évitant de calculer les correspondances de saut, on divise le temps d’exécution par 2 !

C’est déjà beaucoup mieux, et on a à peine plus de 50 lignes de code, includes compris. Pas mal.

Optimisation : ajoutons des optcodes cachés !

Un programme Brainfuck contient souvent des motifs, des séries d’instructions, qui font toujours la même chose et donc qu’on peut facilement optimiser au niveau de l’interpréteur.

J’en ai choisi 3 qui sont très faciles à passer dans l’interpréteur :

  • >[-]<[->+<] est un déplacement : la case N+1 prends la valeur de la case N, qui elle est passée à 0.
  • [->+<] est une addition : les cases N et N+1 sont additionnées dans la case N+1, et la case N est passée à 0.
  • [-] est la remise à 0 de la case N.

Attention à l’implémentation ! Le motif du déplacement contient les motifs d’addition et de remise à 0, donc il doit être détecté avant ce deux-ci sous peine d’être remplacé par des versions sous-optimales !

Donc :

  • Lignes 12 à 14 : on détecte ces motifs et on les remplace par de nouveaux « optcode » non-standard dans Brainfuck (et on remercie Kotlin qui a une méthode de remplacement qui n’utilise pas les REGEX, contrairement à celle de Java qui les impose) ;
  • Lignes 30 à 32 : on interprète ces nouveaux optcodes.

À noter que la suppression préalable des commentaires (ligne 11) est maintenant obligatoire, sinon des commentaires pourraient être confondus avec de nouveaux optcodes, et des motifs pourraient ne pas être détectés s’il y avais des commentaires au milieu.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
package fr.spacefox.brainfuck

import java.io.File
import java.io.IOException
import java.io.InputStreamReader
import kotlin.system.measureTimeMillis

class AdvancedBrainFuck(strProgram: String) {

    private val program: CharArray = strProgram
            .filter { it in listOf('+', '-', '>', '<', '[', ']', '.', ',') }
            .replace(">[-]<[->+<]", "m")    // Move
            .replace("[->+<]",      "a")    // Addition
            .replace("[-]",         "0")    // Cell reset
            .toCharArray()
    private val ram = IntArray(30000)
    private val inputReader = InputStreamReader(System.`in`)
    private val jumpCache: IntArray = IntArray(strProgram.length)

    fun run() {
        var ramPtr = 0
        var programPtr = 0

        do {
            when (program[programPtr]) {
                '>' -> ramPtr++
                '<' -> ramPtr--
                '+' -> ram[ramPtr] = (ram[ramPtr] + 1) % 0xFFFF
                '-' -> ram[ramPtr] = (ram[ramPtr] - 1) % 0xFFFF
                '0' -> ram[ramPtr] = 0
                'a' -> { ram[ramPtr + 1] += ram[ramPtr] ; ram[ramPtr] = 0 }
                'm' -> { ram[ramPtr + 1] = ram[ramPtr] ; ram[ramPtr] = 0 }
                '[' -> if (ram[ramPtr] == 0) programPtr = jump(programPtr, 1)
                ']' -> if (ram[ramPtr] != 0) programPtr = jump(programPtr, -1)
                '.' -> print(ram[ramPtr].toChar())
                ',' -> ram[ramPtr] = try { inputReader.read() } catch (e: IOException) { 0 }
            }
            programPtr++
        } while (programPtr < program.size)
    }

    private fun jump(instructionPtr: Int, step: Int): Int {
        if (jumpCache[instructionPtr] == 0) {
            var i = instructionPtr
            var loops = 1
            while (loops > 0) {
                i += step
                when (program[i]) {
                    '[' -> loops += step
                    ']' -> loops -= step
                }
            }
            jumpCache[instructionPtr] = i
        }
        return jumpCache[instructionPtr]
    }
}

fun main(args: Array<String>) {
    val time = measureTimeMillis { AdvancedBrainFuck(File(args[0]).readText()).run() }
    println("Completed in $time ms")
}

Métriques :

  • Hello World : 58 ms. C’est encore ralenti, mais toujours instantané.
  • Tours de Hanoï : 9,9 s. Vue la quantité délirante de remise à 0 dans le code source de ce programme, l’amélioration n’est pas étonnante.
  • Fractale : 46 s. Il n’y a pratiquement aucun motif détecté dans le code source de ce programme, donc le temps passé en détection/remplacement n’est pas compensé à l’exécution.

Et si on évitait d'exécuter plein de fois de suite la même instruction ?

L’une des propriétés de BrainFuck, c’est qu’aucune instruction n’a de paramètre. Donc quand on veut faire +5, on doit faire 5 fois +1.

Il y a donc un gros potentiel d’amélioration sur ce point en remplaçant toutes les séries de caractères identiques par une seule fois le caractère et un paramètre qui dit combien de fois il faut l’appliquer. Évidemment, ça nécessite une « compilation interne » et une modification de l’interpréteur pour prendre en compte ces paramètres.

  • Ligne 20 : on déclare 2 variables locales (grâce à la fonctionnalité de déstructuration d’objet de Kotlin) qui contiennent le programme « compilé » et les paramètres. Le tableau de paramètres contient aussi le cache de sauts (case de retour en paramètre des cases de saut), qui du coup est pré-calculé.
  • Lignes 26 et 27 : les additions et soustractions sont maintenant la même opération, c’est le paramètre qui va indiquer si on additionne un nombre positif ou négatif. Idem avec les décalages de pointeur à droite ou à gauche.
  • Ligne 40 : la fonction de « compilation » de notre programme (qui a déjà été pré-traité comme dans les versions précédentes).
  • Lignes 42-43 : spécificité de Kotlin, si une liste doit être mutable, il faut l’indiquer spécifiquement.
  • Ligne 46 : on commence par empiler toutes les instructions qu’on peut chainer à la suite.
  • Ligne 68 : ceci fait, on peut pré-calculer les correspondances de saut (ce qui ne peut pas être fait en même temps parce que la longueur du programme, donc les emplacements de sauts, sont inconnus tant que les empilements ne sont pas calculés).
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
package fr.spacefox.brainfuck

import java.io.File
import java.io.IOException
import java.io.InputStreamReader
import kotlin.system.measureTimeMillis

class CompiledBrainFuck(strProgram: String) {

    private val instructions = strProgram
            .filter { it in listOf('+', '-', '>', '<', '[', ']', '.', ',') }
            .replace(">[-]<[->+<]", "m")    // Move
            .replace("[->+<]",      "a")    // Addition
            .replace("[-]",         "0")    // Cell reset
            .toCharArray()
    private val ram = IntArray(30000)
    private val inputReader = InputStreamReader(System.`in`)

    fun run() {
        val (compiled, parameters) = compile(instructions)
        var ramPtr = 0
        var programPtr = 0

        do {
            when (compiled[programPtr]) {
                '>', '<'    -> ramPtr += parameters[programPtr]
                '+', '-'    -> ram[ramPtr] = (ram[ramPtr] + parameters[programPtr]) % 0xFFFF
                '0'         -> ram[ramPtr] = 0
                'a'         -> { ram[ramPtr + 1] += ram[ramPtr] ; ram[ramPtr] = 0 }
                'm'         -> { ram[ramPtr + 1] = ram[ramPtr] ; ram[ramPtr] = 0 }
                '['         -> if (ram[ramPtr] == 0) programPtr = parameters[programPtr]
                ']'         -> if (ram[ramPtr] != 0) programPtr = parameters[programPtr]
                '.'         -> print(ram[ramPtr].toChar())
                ','         -> ram[ramPtr] = try { inputReader.read() } catch (e: IOException) { 0 }
            }
            programPtr++
        } while (programPtr < compiled.size)
    }

    private fun compile(unCompiled: CharArray): Pair<CharArray, IntArray> {

        val compiled = mutableListOf<Char>()
        val parameters = mutableListOf<Int>()
        var lastInstruction = '\u0000'

        for (instruction in unCompiled) {
            when (instruction) {
                '>', '+' -> if (instruction == lastInstruction) {
                                parameters[parameters.lastIndex]++
                            } else {
                                compiled.add(instruction)
                                parameters.add(1)
                            }
                '<', '-' -> if (instruction == lastInstruction) {
                                parameters[parameters.lastIndex]--
                            } else {
                                compiled.add(instruction)
                                parameters.add(-1)
                            }
                else -> {
                    compiled.add(instruction)
                    parameters.add(0)
                }
            }
            lastInstruction = instruction
        }

        for (open in 0..compiled.lastIndex) {
            if (compiled[open] == '[') {
                var loops = 1
                var close = open
                while (loops > 0) {
                    close++
                    when {
                        compiled[close] == '[' -> loops++
                        compiled[close] == ']' -> loops--
                    }
                }
                parameters[open] = close    // Match [ → ]
                parameters[close] = open    // Match ] → [
            }
        }

        return Pair(compiled.toCharArray(), parameters.toIntArray())
    }
}

fun main(args: Array<String>) {
    val time = measureTimeMillis { CompiledBrainFuck(File(args[0]).readText()).run() }
    println("Completed in $time ms")
}

Même avec un pré-compilateur interne, on reste sous les 100 lignes, avec include et tout, et à moins de 100 caractères par ligne !

Métriques :

  • Hello world : 50 ms : cette fois-ci, le temps de compilation est gagné à l’exécution, même si on reste plus lent que la version « naïve ».
  • Tours de Hanoï : 1,0 seconde. Ce qui donne une idée du point auquel le programme est peu optimisé.
  • Fractale : 10,9 secondes. C’est très efficace, la preuve que les versions « normales » de BrainFuck passent leur temps à faire la même chose !

Je pourrais détailler beaucoup plus, par exemple faire des stats sur le nombre d’opérations BrainFuck exécutées en fonction des optimisations, ou détailler toutes les techniques Kotlin utilisées.

Mais ce n’est pas le sujet, le but de mon test est triplement atteint :

  1. Kotlin peut être très efficace et compact : on a un interpréteur BF optimisé (et difficile d’aller plus loin sans sortir des techniques de sioux) en moins de 100 lignes propres. Et contrairement à Java (même 8), je n’ai pas eu l’impression d’écrire du code « parce qu’il y a besoin de ça pour que ça marche », mais seulement des lignes utiles.
  2. Kotlin reste lisible avec un peu d’habitude. Je ne pense pas qu’il contienne des lignes vraiment absconses ?
  3. Kotlin est performant. Je ne l’ai pas indiqué dans les métriques, mais le code de la dernière version est plus rapide (sur la même JVM et sur le même PC) que le code Java 8 équivalent. Je n’ai pas creusé ce mystère.

Je ne sais pas (encore ?) ce qu’il vaut sur du Android, mais c’est clair que sur du Java pur ou du Java EE (Spring a une version Kotlin), ça peut carrément valoir le cout !

5 commentaires

Merci pour ce billet intéressant et instructif ! Les techniques d’optimisation présentées sont bien trouvées. Par curiosité, elles sont « classiques » ou ce sont tes trouvailles ?

+2 -0

Les deux en fait :

  • Le cache de saut et le « compactage » d’instructions sont des idées assez évidentes (et qui donc sont « classiques » par réinvention).
  • La détection de motif est une idée plus avancée, en se renseignant s’il existe des motifs on tombe très vite sur ceux-ci, qui sont documentés même sur Wikipedia je crois maintenant.
+2 -0

Sans la conclusion, j’aurais oublié que Kotlin était aussi le sujet de ce billet ! Merci SpaceFox pour cet agréable test.

+1 -0

Une métrique que je crois ne pas avoir publiée ici : en ajoutant un compteur dans la boucle d’exécution (ce qui ne ralentit pas significativement le programme), on peut avoir le nombre d’instructions exécutées.

Les optimisations nous permettent donc de passer :

  • Pour la fractale : de 10 712 557 593 instructions en 81865 ms (131 MIPS) à 2 951 274 897 instructions en 10323 ms (286 MIPS) (facteur 3,6 sur les instructions)
  • Pour les tours de Hanoï : de 6 641 623 533 instructions en 38620 ms (172 MIPS) à 304 410 390 (288 MIPS) (facteur 21,8 (!) sur les instructions).

Le gros du gain en MIPS vient simplement du fait d’éviter de calculer les correspondances de boucle à chaque fois.

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte