Di Kotlin se ne è parlato a linee generali in questo articolo così come una descrizione basilare del suo Object-Model in quest’altro.

Cosa si intende con “ottimizzare”

Si intende il raggiungimento di una maggiore velocità d’esecuzione del codice che scriviamo oppure un utilizzo di memoria più economico.

Cosa si intende con “con pochi sforzi”

Si intendono accorgimenti. In un’applicazione non si dovrebbe focalizzare troppo sulle performance senza una reale necessità dietro (problema, ad esempio esecuzione lenta o uso di risorse più alto di quanto non ci si possa permettere). Focalizzarsi sulle performance prematuramente può produrre a scrivere codice peggiore e meno funzionalità, eventualmente per migliorare certe routines che già funzionano molto bene, e poi magari sono ben altri i colli di bottiglia che rallentano l’applicativo.

In questo articolo dunque, ci dedicheremo a features del linguaggio Kotlin, che non degradano il codice che scriviamo, ma anzi, o rendono la leggibilità del codice la stessa, o la migliorano persino; ad esempio: Avete mai sentito un programmatore lamentarsi del rallentamento d’esecuzione presunto nei paradigmi funzionali? È davvero un motivo di preoccuparsi? Ma soprattutto (visto che l’articolo tratta le performance e non solo il design del codice), è davvero vero?

 

Introduzione

Si è fatto riferimento, in precedenza, al fatto che in Kotlin non esistono tipi primitivi a differenza di Java, ma solo oggetti. Comporta sempre un costo in più in ambiente JVM come l’autoboxing in Java? (Per intenderci, quando in Java Integer al posto di int ad esempio). Oppure, qual è il costo delle funzioni lambda nei paradigmi funzionali al posto dei cicli? Delle funzioni ricorsive? Vediamo un po’.

 

Tipi primitivi e Auto-Boxing (JVM)

Ricordiamo che Kotlin è un linguaggio che si appoggia su diversi possibili ambienti. In questa sezione, facciamo riferimento alla sua principale, la JVM. Lo stesso non accade in JavaScript che ha un object-model differente. Kotlin Native sarà eventualmente trattato in futuro.

Sicché la prima cosa che si fa con un linguaggio quando vi si interagisce, spesso consiste nell’interagire anche con i tipi primitivi, diamo uno sguardo a questi.

 

Dichiarazioni locali e parametri nelle funzioni

Allora, cominciamo col dire, che quando abbiamo a che fare con un Int , dove Intè la classe primitiva e predefinita in Kotlin, in caso di variabili locali, queste non saranno auto-boxed in un Integer ma corrisponderanno al tipo primitivo int di Java nel byte-code. Quindi dichiararne una non comporterà un’allocazione nell’heap (un po’ più costosa), ma nello stack (molto poco costosa), equivalentemente la de-allocazione rispetto al Garbage Collector.

Possiamo leggerlo noi stessi nella Docs di Kotlin ufficiale oppure nell’estratto di codice di interfaccia accessibile dall’IDE.

/**
 * Represents a 32-bit signed integer.
 * On the JVM, non-nullable values of this type are represented as values of the primitive type `int`.
 */
public class Int private constructor() : Number(), Comparable<Int> {
    companion object { ... }
...
}

Diverso caso invece, quando utilizziamo i tipi nullabili, in quel caso, avremo a che fare con oggetti istanziati nella memoria dinamica.

Per esempio in questo codice

fun main(args: Array<String>) {
    val myInt: Int
    val myNullableInt: Int?

    myInt = 10
    myNullableInt = null
    println(myInt)
    println(myNullableInt)
}

myInt sarà dichiarato come di tipo primitivo nel bytecode Java, mentre myNullableIntcome oggetto vero e proprio (di classe Integer).  Va da sé, che a fini di più corretto design del codice, non solamente riferendosi alle performance, è meglio evitare i tipi nullabili quando possibile, a meno che ciò non comporti un compromesso ancora “peggiore” (ad esempio usare -1 come valore nullo).

 

Dichiarazioni di array e Generics

Come probabilmente ben saprete, o in caso contrario, saprete adesso, in Java non esistono primitivi quando si ha a che fare con collezioni generiche. La sola concezione di collezione generica infatti, in Java si fonda sul concetto di type-erasure, dove la collezione generica, nel byte-code, contiene solo riferimenti ad oggetti di tipo Object. Mentre quindi possiamo avere un array di interi primitivi (int[]), non esiste la concezione di ArrayList<int> ma solamente di ArrayList<Integer>. Convertire quindi un array di primitivi in lista, comporterà un costo aggiuntivo di allocazione nell’auto-boxing.

In Kotlin, l’array è una classe generica (Array), e dunque un Array<MyObject> è sostanzialmente simile a un Array<Int>, che assomiglierà per l’appunto a un Integer[] di Java.

Tuttavia, va da sé che Kotlin ha previsto delle funzioni per dichiarare array sfruttando di nuovo la presenza dei tipi primitivi nel Java bytecode.

Stiamo parlando di funzioni come intArrayOf, charArrayOf, doubleArrayOf, eccetera per ogni tipo primitivo.

val intArr    = intArrayOf(1, 2, 3)         // di tipo IntArray in Kotlin, di tipo int[] nel bytecode
val charArr   = charArrayOf('a','b','c')    // di tipo char[] nel bytecode
val doubleArr = doubleArrayOf(1.0,2.0,3.0)  // di tipo double[] nel bytecode
// ...
val integerArr: Array<Int> = arrayOf(1,2,3) // di tipo Integer[] nel bytecode

println(intArr::class == integerArr::class) // false

Lo stesso vale dunque quando si ha a che fare con funzioni generiche, e riferimenti a funzione, implementati in Kotlin con una classe.

Prendiamo in esempio la dichiarazione

val unaryOperation: (Int) -> Int

riferimento a funzione con un parametro intero che restituisce un altro intero. Consideriamo adesso una funzione che restituisca una funzione di questo tipo.

enum class UnaryOperation {
    FACTORIAL,
    INCREMENT,
    DECREMENT
}

fun getFunctionForUnaryOp(type: UnaryOperation): (Int) -> Int {
    when (type) {
        UnaryOperation.FACTORIAL -> return ::recursiveFactorial
        UnaryOperation.INCREMENT -> return fun(x: Int): Int { return x+1 }
        UnaryOperation.DECREMENT -> return { x -> x - 1 }
    }
}

fun recursiveFactorial(n: Int): Int {
    n <= 1 && return 1
    return n * recursiveFactorial(n-1)
}

La funzione in questione è getFunctionForUnaryOp, che restituisce, non un valore primitivo ma una funzione. Restituisce rispettivamente o una funzione pre-dichiarata (che tratta tipi primitivi), oppure due funzioni lambda.

L’utilizzo nel main in Kotlin è questo.

val factorial: (Int) -> Int = getFunctionForUnaryOp(UnaryOperation.FACTORIAL)
val increment = getFunctionForUnaryOp(UnaryOperation.INCREMENT)

println(factorial(increment(3))) // (3+1)! = 24

Come affermare che la variabile factorial sta trattando oggetti e non primitivi? Un modo semplice per scoprirlo è provare a osservare la firma di questa funzione in Java. Infatti, in un differente main di esempio in Java, avremo

import kotlin.jvm.functions.Function1; // <----- Porre attenzione al package

public class JavaCode {

    public static void main(String[] args) {
        UnaryOperation unaryOperation = UnaryOperation.FACTORIAL;

        // classe Function1 da Kotlin, con primo parametro generico il tipo di input e secondo, il tipo di output
        Function1<Integer, Integer> fact = MainKt.getFunctionForUnaryOp(unaryOperation);

        System.out.println(fact.invoke(4)); // 24
    }
}

Sarebbe raccomandabile a fini di design tuttavia, non preoccuparsi di questi costi aggiunti in casi di programmazione funzionale, ma sono costi che si potrebbero tenere in conto se si programma ad esempio in Android per dispositivi di fascia bassa.

Ecco comunque giusto a fini dimostrativi, un decompilato del Kotlin compilato in Byte-code Java di nuovo in Java

public static final void main(@NotNull String[] args) {
  Intrinsics.checkParameterIsNotNull(args, "args");
  int myInt = 10;
  Integer myIntOpt = (Integer)null;
  System.out.println(myInt);
  System.out.println(myIntOpt);
  int[] intArr = new int[]{1, 2, 3};
  char[] var10000 = new char[]{'a', 'b', 'c'};
  double[] var13 = new double[]{1.0D, 2.0D, 3.0D};
  Integer[] integerArr = new Integer[]{1, 2, 3};
  boolean var7 = Intrinsics.areEqual(Reflection.getOrCreateKotlinClass(intArr.getClass()), Reflection.getOrCreateKotlinClass(integerArr.getClass()));
  System.out.println(var7);
  Function1 factorial = getFunctionForUnaryOp(UnaryOperation.FACTORIAL);
  Function1 increment = getFunctionForUnaryOp(UnaryOperation.INCREMENT);
  int var9 = ((Number)factorial.invoke(increment.invoke(3))).intValue();
  System.out.println(var9);
}

Si può osservare, che effettivamente, le variabili trattate in merito a primitive ed array, sono effettivamente primitive, così come che i riferimenti a funzione sono classi di tipo Function1 (che per type-erasure, hanno perso la specializzazione).

 

Ricapitolazione

• Vantaggi uso di primitivi e array di primitivi anziché collezioni generiche:
  • maggiore velocità di un ciclo for, anche di 15 volte, se l’iteratore è un riferimento a oggetto (java.lang.Integer o Int? anziché Int). (articolo da kotlin-academy);
  • allocazione di memoria 5 volte inferiore in un IntArray rispetto a un List<Int> (test di un milione di elementi, fonte articolo del punto precedente);
  • esecuzione più veloce sugli elementi (es. funzione average() 25% più veloce, fonte articolo del punto precedente).
• Svantaggi:
  • impossibilità di usare la nullabilità;
  • una lista è più flessibile come struttura dati di un array in quanto permette di aggiungere nuovi elementi;

È evidente dunque che se scrivete codice Kotlin particolari routine performance-critical, l’uso dei tipi primitivi conviene.

 

Funzioni inline

• Vantaggi uso di inlining:
  • Esecuzione del codice più veloce perché non ci sarà un dispatch di chiamata a funzione o aggiunta nello stack, ma il codice della funzione nel bytecode sarà “ricopiato” laddove la funzione viene chiamata. Miglioramento consistente quando una funzione è chiamata in un loop.
• Svantaggi:
  • In caso di funzioni molto grandi, e chiamate in tanti punti del codice, la dimensione del compilato (bytecode) sarà maggiore.
  • Una funzione inline in un API pubblica non può usare dichiarazioni API non-pubbliche (es. private e internal) e le loro parti, nel suo body, per eliminare il rischio di incompatibilità binaria causata da modifiche nel modulo con la funzione inline (fatta eccezione per le dichiarazioni internal annotate con @PublishedApi).

Un argomento più interessante forse, e talvolta discusso, è quello dell’inlining dei metodi. Ho visto talvolta criticato l’uso degli stream in Java, o in generale dei metodi forEach piuttosto che un for-each standard, oppure un for nello stile C.

La critica, per linguaggi come JavaScript ad esempio, è che chiamando in un array un .forEach, si assiste all’overhead di una chiamata a funzione per iterazione, mentre col for classico non accade.

Osserviamo questo codice Java

Integer[] arr = new Integer[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
List<Integer> list = Arrays.asList(arr);
list.forEach(element -> {
   System.out.print(element);
});

Vi dico sulla fiducia che il decompilato di questo codice è praticamente lo stesso. Ci si aspetta allora che effettivamente il forEach chiamerà il nostro metodo n volte, e che l’inlining spetti a runtime alla JVM.

Osserviamo adesso l’equivalente codice Kotlin

val myList = listOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
myList.forEach { element ->
    print(element)
}

Il codice dietro la funzione forEach in Kotlin è questo

@kotlin.internal.HidesMembers
public inline fun <T> Iterable<T>.forEach(action: (T) -> Unit): Unit {
    for (element in this) action(element)
}

Poniamo attenzione a quella keyword inline: comporta che sia la funzione forEach che la funzione lambda action non esisteranno nel bytecode, ma si commetterà una vera e propria sostituzione nel codice.

Osserviamo infatti nel de-compilato Java (da bytecode Java emesso da codice Kotlin).

List myList = CollectionsKt.listOf(new Integer[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10});
Iterable $receiver$iv = (Iterable)myList;
Iterator var12 = $receiver$iv.iterator();

while(var12.hasNext()) {
    Object element$iv = var12.next();
    int element = ((Number)element$iv).intValue();
    System.out.print(element);
}

e osserviamo, che effettivamente, non esiste nessuna chiamata a funzione forEach, né a funzioni lambda. Per chi non lo sapesse, il costrutto while-hasNext-next, è esattamente il costrutto nel bytecode Java del foreach.

Per chi non mi dovesse credere, osservi il decompilato da bytecode Java di questo codice

for (int element : list) {
    System.out.print(element);
}

L’uso delle funzioni inline quindi, si presenta particolarmente di vantaggio quando si ha a che fare con higher-order functions, limitando il “danno” dell’overhead della chiamata a funzione. Lo stesso si ha nelle funzioni flat e map che nel byte-code saranno dei loops semplici senza chiamate a funzione alla funzione lambda.

Nota: abbastanza intuitivamente, le funzioni inline non possono essere ricorsive.

 

Tail Call Optimization (funzioni ricorsive)

Questa è una delle mie preferite aggiunte in Kotlin. Quanto spesso si sente un programmatore imperativo criticare aspramente la ricorsione nella programmazione? Fin troppo!

“La ricorsione è una tecnica poco efficiente, ricorda sempre che ogni funzione che richiama sé stessa non si chiude finché non si chiude la funzione chiamata, che a sua volta non si richiude finché non si chiude la funzione che lei ha chiamato etc…”

“la ricorsione è da evitare se non necessaria”

“…”

Dopotutto, se il consumo di memoria e la lentezza possono passare in secondo piano in presenza di calcolatori molto potenti, lo stack overflow è un problema: Un algoritmo che matematicamente è formulato in maniera corretta, potrebbe fallire solamente per una ricorsione troppo profonda per essere supportata dalla macchina/interprete. Ciò porta talvolta, in linguaggi dove non è supportata la TCO (Tail-call optimization), a scrivere soluzioni iterative e meno eleganti che compensino questo gap.

Cos’è allora la TCO? Ecco, è l’anello mancante in questo discorso, ovvero quando scrivendo la funzione ricorsiva in un certo modo, è possibile permettere al compilatore o interprete, di trasformare la funzione ricorsiva in un ciclo essenzialmente, e non incorrere nello stack di chiamate a funzione. Si ottengono i vantaggi di entrambi gli approcci iterativi e ricorsivi: Funzione scritta elegantemente da un punto di vista matematico, e allo stesso tempo performante e non porterà a crash o StackOverflow Error in esecuzione.

C e C++ nella maggior parte dei compilatori più utilizzati, godono di questo beneficio. Java invece no. Va da sé che ci sono anche linguaggi senza supporto ai cicli, dove la ricorsione è l’unico modo per risolvere un problema (tra cui Erlang su cui si basa il backend WhatsApp)

Vediamo dunque una funzione ricorsiva che potrebbe creare problemi

fun <Element>reverseArray(array: Array<Element>, pos: Int = 0) {
    val n = array.size
    if (pos > n/2) return   // Caso base

    val tmp = array[pos]
    array[pos] = array[n-1-pos]
    array[n-1-pos] = tmp
    reverseArray(array, pos+1)
}

La funzione dà un risultato corretto con array non troppo lunghi,

val array = arrayOf(0,1,2,3,4,5,6,7,8,9,10,11)
reverseArray(array)
println(array.asList())

ma termina con uno StackOverflow Error per array molto lunghi.

Proviamo adesso a copiare la funzione di prima, aggiungendo tailrec davanti a fun nella dichiarazione, e rinominare questa in reverseArrayTCO_off per una comparazione. Inoltre, si fornisce una funzione per generare un array di arbitraria lunghezza e di numeri random.

La base della Tail-Call Optimization, si fonda sul fatto che la chiamata a funzione ricorsiva, avviene come ultima riga eseguita della funzione. Per cui deve in genere avvenire in corrispondenza del return. Infatti, l’ottimizzazione sta nel non aggiungere un’ulteriore funzione sullo stack allocando nuove variabili locali, ma riutilizzare lo stack della funzione uscente così da non aumentare la complessità spaziale.

fun main(args: Array<String>)
// ...
    val array2 = generateRandomArray(n = 20000)
    println("TCO OFF reverse (ms): " + measureTimeMillis { reverseArray_TCOoff(array2) })
    val array3 = generateRandomArray(n = 20000)
    println("TCO ON  reverse (ms): " + measureTimeMillis { reverseArray(array3) })

}

tailrec fun <Element>reverseArray(array: Array<Element>, pos:Int = 0) {
    val n = array.size
    if (pos > n/2) return   // Caso base

    val tmp = array[pos]
    array[pos] = array[n-1-pos]
    array[n-1-pos] = tmp
    reverseArray(array, pos+1) // Tail Call-Optimization
}


fun <Element>reverseArray_TCOoff(array: Array<Element>, pos:Int = 0) {
    val n = array.size
    if (pos > n/2) return   // Caso base

    val tmp = array[pos]
    array[pos] = array[n-1-pos]
    array[n-1-pos] = tmp
    reverseArray_TCOoff(array, pos+1)
}

fun generateRandomArray(n: Int, bound: Int = 1000): Array<Int> {
    val list = ArrayList<Int>(n)
    val random = Random()

    for (i in 0 until n) {
        list.add(random.nextInt(bound))
    }

    return list.toTypedArray()
}

Et voilà

E va bene, abbassiamo il limite. Poniamo n = 9999.

val array2 = generateRandomArray(n = 9999)
println("TCO OFF reverse (ms): " + measureTimeMillis { reverseArray_TCOoff(array2) })
val array3 = generateRandomArray(n = 9999)
println("TCO ON  reverse (ms): " + measureTimeMillis { reverseArray(array3) })

Ed ecco la differenza di performance!

TCO OFF reverse (ms): 1
TCO ON  reverse (ms): 0

Non una così grande differenza in performance, lo ammetto! Ma personalmente, mi preoccuperei di più che la variante tailrec funziona in un approccio puramente ricorsivo mentre l’altra no. Non si evincono differenze di performance nemmeno in due milioni di elementi tra quella e la funzione della libreria standard di Kotlin. È evidente dunque, che se apprezzate gli approcci ricorsivi anche quando non sono particolarmente necessari, Kotlin non vi aggiunge costi.

• Vantaggi del tailrec:
  • nessuno stack overflow nelle funzioni ottimizzate per TCO su un numero indefinito di chiamate ricorsive;
  • esecuzione più veloce e minor impatto di memoria (non si crea lo stack di chiamate ricorsive di funzioni con nuove allocazioni di variabili locali, eccetera).
• Svantaggi:
  • Se la si usa si perde il tracciamento nello stacktrace dell’esatto punto in cui è la funzione ha generato un’eccezione, perché per esempio se si solleva un’eccezione alla 25-esima ricorsione, non potremo dedurlo dallo stack-trace ma in altri modi. (Ad es. usando il debugger).

 

Conclusione

Così si conclude l’articolo! Era un articolo di livello medio. Si può trovare curioso tuttavia che Kotlin non solo offre una sintassi innegabilmente (va bene, diciamo argomentabilmente) più bella di Java, almeno in certi aspetti, ma che talvolta offre persino accorgimenti di performance più all’avanguardia! È anche vero che la JVM è di suo già molto ottimizzata, malgrado i luoghi comuni che vi si facciano; tuttavia ritengo che l’articolo può sia essere d’aiuto per chi si sta approcciando a Kotlin, sia chi vuole valutarne la convenienza e si chiede se determinate astrazioni di Kotlin possono impattare sulle performance come in altri linguaggi che compilano sulla JVM ma non ugualmente veloci (come Scala).