Perché Scala "per le comprensioni del ciclo" è molto lento rispetto ai loop FOR?

Question

È stato detto che le interpretazioni di Scala For sono in realtà piuttosto lente. La ragione per cui mi è stato dato è che a causa di una limitazione Java, per le comprensioni (come "ridurre", usato di seguito) è necessario generare un oggetto temporaneo con ogni iterazione per chiamare la funzione passata.

IS .. .QUESTO È VERO? I test sottostanti sembrano confermarlo, ma non capisco del tutto perché questo sia il caso.

Questo potrebbe avere senso per "lambda" o funzioni anonime, ma non per funzioni non anonime.

Nel mio test, ho eseguito per loop contro list.reduce (vedi codice di seguito), e li ho trovati ad essere due volte più veloce, anche quando ogni iterazione chiamava la stessa identica funzione che è stata passata per ridurre!

Trovo che questo sia sorprendentemente contro-intuitivo (una volta si pensava che la libreria di Scala sarebbe stata accuratamente creata per essere il più ottimale possibile).

In un test metto insieme, corse stesso anello (riassumere i numeri da 1 a un milione, indipendentemente overflow) cinque modi diversi:

1. per ciclo su matrice di valori
2. per ciclo, ma chiamare una funzione invece di linea aritmetica
3. per ciclo, la creazione di un oggetto che contiene una funzione aggiunta
4. list.reduce, passando i funzione anonima
5. list.reduce, passando membro oggetto funzione

I risultati sono stati i seguenti: prova: min/max/medio (millisecondi)

1. 27/157/64.78 
2. 27/192/65.77 <--- note the similarity between tests 1,2 and 4,5 
3. 139/313/202.58 
4. 63/342/150.18 
5. 63/341/149.99 

Come si può vedere, le versioni "per la comprensione" sono dell'ordine di " per with new per ogni istanza ", il che implica che una" nuova "può essere effettivamente eseguita per entrambe le versioni di funzioni anonime e non anonime.

Metodologia: il seguente codice (chiamata di prova rimosso) è stato compilato in un singolo file .jar per garantire che tutte le versioni eseguissero lo stesso codice di libreria. Ogni test in ogni iterazione è stato chiamato in una nuova JVM (vale a dire scala -cp ... per ogni test) per rimuovere i problemi relativi alle dimensioni dell'heap.

class t(val i: Int) { 
    def summit(j: Int) = j + i 
} 

object bar { 
    val biglist:List[Int] = (1 to 1000000).toList 

    def summit(i: Int, j:Int) = i+j 

    // Simple for loop 
    def forloop: Int = { 
     var result: Int = 0 
     for(i <- biglist) { 
      result += i 
     } 
     result 
    } 

    // For loop with a function instead of inline math 
    def forloop2: Int = { 
     var result: Int = 0 
     for(i <- biglist) { 
      result = summit(result,i) 
     } 
     result 
    } 

    // for loop with a generated object PER iteration 
    def forloop3: Int = { 
     var result: Int = 0 
     for(i <- biglist) { 
      val t = new t(result) 
      result = t.summit(i) 
     } 
     result 
    } 

    // list.reduce with an anonymous function passed in 
    def anonymousfunc: Int = { 
     biglist.reduce((i,j) => {i+j}) 
    } 

    // list.reduce with a named function 
    def realfunc: Int = { 
     biglist.reduce(summit) 
    } 

    // test calling code excised for brevity. One example given: 
    args(0) match { 
     case "1" => { 
        val start = System.currentTimeMillis() 
        forloop 
        val end = System.currentTimeMillis() 
        println("for="+(end - start)) 
        } 
     ... 
} 

Answer 1

Cosa v'è stato detto era vero di "espressioni for", ma il problema con la tua domanda è che hai mischiato "espressioni for" con "funzioni anonime".

"per la comprensione" in Scala è uno zucchero sintattico per una serie di .flatMap, .map e .filter applicazioni. Poiché si stanno testando algoritmi di riduzione e poiché è impossibile implementare un algoritmo di riduzione utilizzando queste tre funzioni, i casi di test non sono corretti.

Ecco un esempio di un "per la comprensione":

val listOfLists = List(List(1,2), List(3,4), List(5)) 
val result = 
    for { 
    itemOfListOfLists <- listOfLists 
    itemOfItemOfListOfLists <- itemOfListOfLists 
    } 
    yield (itemOfItemOfListOfLists + 1) 
assert(result == List(2,3,4,5,6)) 

Il compilatore desugars la parte comprensione al seguente:

val result = 
    listOfLists.flatMap(
    itemOfListOfLists => itemOfListOfLists.map(
     itemOfItemOfListOfLists => itemOfItemOfListOfLists + 1 
    ) 
) 

Poi desugars l'Anonimo sintassi Function:

val result = 
    listOfLists.flatMap(
    new Function1[List[Int], List[Int]] { 
     override def apply(itemOfListOfLists: List[Int]): List[Int] = 
     itemOfListOfLists.map(
      new Function1[Int, Int] { 
      override def apply(itemOfItemOfListOfLists: Int): Int = 
       itemOfItemOfListOfLists + 1 
      } 
     ) 
    } 
) 

Dal codice desugarred è ora evidente che ilLa classeviene istanziata ogni volta che viene chiamato il metodo apply(itemOfListOfLists: List[Int]): List[Int]. Ciò accade per ogni voce di listOfLists. Quindi, più complessa è la tua comprensione, più sono le istanze degli oggetti Function che ottieni.