Benchmarking Scala

La questione delle prestazioni è sempre cruciale per i nuovi
linguaggi che cercano di affermarsi. Ho quindi voluto fare un piccolo
esperimento, molto casereccio e senza alcuna pretesa di scientificità,
per confrontare Scala e Java. Quale elementare banco di prova ho scelto
l’ordinamento di Array. Come primo passo ho creato un micro programma
Java che sfruttasse le funzioni di libreria per l’ordinamento di
vettori.

//File Timer.java
package net.fl.performance;

public final class Timer {

  private long start;
  private long end;

  public Timer() {
    reset();
  }

  public void start() {
    start = System.currentTimeMillis();
  }

  public void stop() {
    end = System.currentTimeMillis();
  }

  public long duration() {
    return (end - start);
  }

  public void reset() {
    start = 0;
    end = 0;
  }

}
//File RandomArray.java
package net.fl.performance;

import java.util.Random;

public class RandomArray {

  public int[] randomIntArray(int size) {
    int [] result = new int[size];
    Random random = new Random();
    for (int i = 0; i < result.length; i++) {
      result[i] = random.nextInt();
    }
    return result;
  }
}
//File SortingArrayPerformance.java
package net.fl.performance;

import java.util.Arrays;

public class SortingArrayPerformance {

  public static void main(String[] args) {
    int lenght = (int) Math.pow(10, 6);
    int[] toSort = new RandomArray().randomIntArray(lenght);
    Timer timer = new Timer();
    timer.start();
    Arrays.sort(toSort);
    timer.stop();
    System.out.println(timer.duration());
  }
}

Sulla macchina utilizzata per i test, un Pentium XEON a 3.8GHz con
Windows 2003 e JDK 1.5.2_03, il tempo medio di esecuzione per ordinare
un milione di elementi è circa di 260 ms, mentre per dieci milioni di
occorrono approssimativamente 3.000 ms. Ho quindi creato un programma
Scala che svolgesse lo stesso compito. Sfruttando la completa
interoperabilità con Java, ho utilizzato all’interno del codice Scala le
classi RandomArray e Timer appena viste. Per
fare il brillante, ho voluto mettere sotto esame la versione di Quick
Sort scritta in stile funzionale che possiamo trovare in Scala
by example
.

//File SortingArrayPerformanceScala1.scala
package net.fl.performance;

object SortingArrayPerformanceScala1 extends Application {

  def sort(xs: Array[Int]): Array[Int] =
    if (xs.length <= 1) xs
    else {
      val pivot = xs(xs.length / 2)
      Array.concat(
        sort(xs filter (pivot >)),
        xs filter (pivot ==),
        sort(xs filter (pivot <)))
    }
  
  val length = Math.pow(10, 6).asInstanceOf[int]
  val toSort = new RandomArray().randomIntArray(length)
  val timer = new Timer()
  timer.start()
  sort(toSort)
  timer.stop()
  println(timer.duration())
}

Non c’è che dire: l’algoritmo è chiarissimo, contrariamente a
quello che possiamo ad esempio leggere nel sorgente del metodo
java.util.Arrays.sort.
Le prestazioni, però, sono alquanto diverse: per un milione di record
occorrono circa 5.700 ms, mentre per dieci milioni sono necessari 63.000
ms. Anche con questo algoritmo i tempi di esecuzione crescono quasi
linearmente, ma con un coefficiente di moltiplicazione ben diverso da
quello Java. Inoltre la memoria richiesta da questa versione di quick
sort è notevolmente maggiore rispetto a quella necessaria nel primo
esempio: per dieci milioni di record è necessario utilizzare non meno di
256 Mb per lo heap della JVM. Un lettore attento non rimane stupito da
questi risultati: mentre la versione di Quick Sort utilizzato dalla
libreria Java modifica “sul posto” i valori dell’array, la versione
Scala, scritta in stile funzionale, restituisce ad ogni iterazione una
nuova copia dell’array passato come parametro al metodo sort.
Ciò, oltre a comportare una maggiore richiesta di memoria, allunga anche
i tempi di risposta.

Ma non è possibile fare di meglio? Ovviamente anche Scala ha una
funzione di libreria che effettua l’ordinamento di array in stile
imperativo. Ecco un programmino che la utilizza:

//File SortingArrayPerformanceScala2.scala
package net.fl.performance;

import scala.util.Sorting

object SortingArrayPerformanceScala2 extends Application {
  val toSort = new RandomArray().randomIntArray(1000000)
  val timer = new Timer()
  timer.start()
  Sorting.quickSort(toSort)
  timer.stop()
  println(timer.duration())  
}

Il tempo medio di esecuzione è di circa 280 ms per un milione di
elementi e di poco più di 3.000 ms per dieci milioni: che sospiro di
sollievo! E’ possibile scrivere programmi Scala con tempi di esecuzione
paragonabili a quelli di Java. Ovviamente, chi volesse spulciare il
sorgente del metodo Sorting.quickSort non troverebbe un
codice molto lineare, ma è importante sapere che, quando le prestazioni
sono un vincolo, Scala sa comunque dire la sua.

Bene, ma Scala sa fare qualcosa di più? Parte del valore aggiunto
di questo linguaggio è la facilità di gestione della programmazione
concorrente. Con poche righe di codice è infatti possibile creare una
versione parallela degli algoritmi appena visti.

//File SortingArrayPerformanceScala3.scala
package net.fl.performance;

import scala.actors.Actor
import scala.actors.Actor._

class ParallelSort {
   
  def sort(xs: Array[int]) = 
    if (xs.length <= 1) xs
    else {
      val pivot = xs(xs.length / 2)
      
      val lessSorter = new Sorter(xs filter (pivot >), self)
      val greaterSorter = new Sorter(xs filter (pivot <), self)
      
      lessSorter.start
      greaterSorter.start
      
      var activeWorkers = 2
      while(activeWorkers > 0) {
        receive {
          case Finished =>  activeWorkers -= 1
        }
      }
      
      Array.concat(
        lessSorter.sortedArray,
        xs filter (pivot ==),
        greaterSorter.sortedArray)
    }
}

case object Finished  //Il messaggio che le classi Sorted inviano a ParallelSort

case class Sorter(toSort: Array[int], client: Actor) extends Actor {
  var sortedArray: Array[int] = null;
  
  def sort(xs: Array[Int]): Array[Int] = //Qui potrei anche usare Sorting.quickSort
    if (xs.length <= 1) xs
    else {
      val pivot = xs(xs.length / 2)
      Array.concat(
        sort(xs filter (pivot >)),
        xs filter (pivot ==),
        sort(xs filter (pivot <)))
    }
  
  def act() = {
    sortedArray = sort(toSort)
    client ! Finished
  }
}

object SortingArrayPerformanceScala3 extends Application {
  val length = Math.pow(10, 6).asInstanceOf[int]
  val toSort = new RandomArray().randomIntArray(length)
  val timer = new Timer()
  timer.start()
  new ParallelSort().sort(toSort)
  timer.stop()
  println(timer.duration())  
}

Sulla macchina di prova, che pur dispone di un processore
multi-core, le prestazioni di questo nuovo programma sono comunque
inferiori a quelle di tutti gli altri: 8.100 ms per un milione di
elementi e 65.000 ms per dieci milioni. Questo avviene anche se il task
manager mostra che la versione parallela è l’unica tra quelle proposte a
saturare completamente entrambe le istanze del processore. A questo
punto si dovrebbe aprire un’analisi su come il sovraccarico della
gestione della concorrenza influisca sulle prestazioni degli algoritmi
paralleli, ed anche su quale effettivo livello di parallelismo possano
fornire i processori multi-core, ma entrambi i temi sfuggono alla mia
portata ;-). Come parziale nota positiva si ha che i tempi di
esecuzione, pur non esaltanti, sembrerebbero crescere in modo
leggermente sub-lineare.

Si noti ad ogni modo che, facendo ricorso alle classi del package
scala.actors.remote, potrei distribuire l’elaborazione su
macchine diverse.

Ho quindi verificato di persona che Scala introduce costrutti che
possono rendere molto più espressivi i programmi, anche se questo va a
volte a scapito delle prestazioni. Il linguaggio consente comunque di
produrre codice con tempi di risposta paragonabili a quelli di Java.
Inoltre vi sono gli strumenti per rendere scalabili le nostre
applicazioni tramite parallelismo, sfruttando eventualmente anche forme
di elaborazione distribuita.

Policy per i commenti: Apprezzo moltissimo i vostri commenti, critiche incluse. Per evitare spam e troll, e far rimanere il discorso civile, i commenti sono moderati e prontamente approvati poco dopo il loro invio.