Differenza nelle prestazioni lambda?

Question

This non è un duplicato della mia domanda. L'ho controllato ed è più sulle classi anonime interiori.

ero curioso di sapere le espressioni lambda e verificato le seguenti:

• dato un array di diecimila voci, quale sarebbe il più veloce per cancellare alcuni indici: espressione Lamba o Per-Loop con un caso di test interno ?

I primi risultati non sono stati sorprendenti nel fatto che non sapevo cosa stavo andando a venire con:

final int NUMBER_OF_LIST_INDEXES = 10_000; 
List<String> myList = new ArrayList<>(); 
String[] myWords = "Testing Lamba expressions with this String array".split(" "); 

for (int i = 0 ; i < NUMBER_OF_LIST_INDEXES ; i++){ 
    myList.add(myWords[i%6]); 
} 

long time = System.currentTimeMillis(); 

// BOTH TESTS WERE RUN SEPARATELY OF COURSE 
// PUT THE UNUSED ONE IN COMMENTS WHEN THE OTHER WAS WORKING 

// 250 milliseconds for the Lambda Expression 
myList.removeIf(x -> x.contains("s")); 

// 16 milliseconds for the traditional Loop 
for (int i = NUMBER_OF_LIST_INDEXES - 1 ; i >= 0 ; i--){ 
    if (myList.get(i).contains("s")) myList.remove(i); 
} 
System.out.println(System.currentTimeMillis() - time + " milliseconds"); 

Ma poi, ho deciso di cambiare la costante NUMBER_OF_LIST_INDEXES a un milione e qui è il risultato:

final int NUMBER_OF_LIST_INDEXES = 1_000_000; 
List<String> myList = new ArrayList<>(); 
String[] myWords = "Testing Lamba expressions with this String array".split(" "); 

for (int i = 0 ; i < NUMBER_OF_LIST_INDEXES ; i++){ 
    myList.add(myWords[i%6]); 
} 

long time = System.currentTimeMillis(); 

// BOTH TESTS WERE RUN SEPARATELY OF COURSE 
// PUT THE UNUSED ONE IN COMMENTS WHEN THE OTHER WAS WORKING 

// 390 milliseconds for the Lambda Expression 
myList.removeIf(x -> x.contains("s")); 

// 32854 milliseconds for the traditional Loop 
for (int i = NUMBER_OF_LIST_INDEXES - 1 ; i >= 0 ; i--){ 
    if (myList.get(i).contains("s")) myList.remove(i); 
} 
System.out.println(System.currentTimeMillis() - time + " milliseconds"); 

per rendere le cose più semplici da leggere, ecco i risultati:

|  | 10.000 | 1.000.000 | 
| LAMBDA | 250ms | 390ms | 156% evolution 
|FORLOOP | 16ms | 32854ms | 205000+% evolution 

Ho le seguenti domande:

• Qual è la magia dietro questo? Come arriviamo a una così grande differenza per l'array e non per il lambda quando gli indici con cui lavorare è * 100.

• In termini di prestazioni, come sappiamo quando utilizzare Lambdas e quando attenersi ai metodi tradizionali per lavorare con i dati?

• Si tratta di un comportamento specifico del metodo List? Un'altra espressione Lambda produce anche esibizioni casuali come questa?

Answer 1

Ho scritto un benchmark JMH per misurare questo. Ci sono 4 metodi:

• removeIf su un ArrayList.
• removeIf su un LinkedList.
• iteratore con iterator.remove() su un ArrayList.
• iteratore con iterator.remove() su un LinkedList.

Il punto di riferimento è quello di dimostrare che removeIf e un iteratore dovrebbe fornire le stesse prestazioni, ma che non è il caso per un ArrayList.

Per impostazione predefinita, removeIf utilizza un iteratore internamente per rimuovere gli elementi, pertanto dovremmo aspettarci le stesse prestazioni con removeIf e con un iterator.

---

consideri ora un ArrayList che utilizza un array internamente per contenere gli elementi. Ogni volta che chiamiamo remove, gli elementi rimanenti dopo l'indice devono essere spostati di uno; quindi ogni volta devono essere copiati molti elementi. Quando un iteratore viene utilizzato per attraversare il ArrayList e abbiamo bisogno di rimuovere un elemento, questa copia deve accadere ancora e ancora, rendendo questo molto lento. Per un LinkedList, questo non è il caso: quando un elemento viene eliminato, l'unica modifica è il puntatore all'elemento successivo.

Quindi perché removeIf è veloce su un ArrayList come su un LinkedList? Perché in realtà è sovrascritto e non utilizza un iteratore: il codice contrassegna effettivamente gli elementi da eliminare in un primo passaggio e quindi li elimina (spostando gli elementi rimanenti) in un secondo passaggio. In questo caso è possibile un'ottimizzazione: invece di spostare gli elementi rimanenti ogni volta che è necessario rimuoverli, lo facciamo una volta sola quando conosciamo tutti gli elementi che devono essere rimossi.

---

Conclusione:

• removeIf dovrebbe essere usato quando si ha la necessità di rimuovere ogni elemento corrispondenza a un predicato.
• remove deve essere utilizzato per rimuovere un singolo elemento noto.

---

Risultato di riferimento:

Benchmark       Mode Cnt  Score  Error Units 
RemoveTest.removeIfArrayList   avgt 30  4,478 ± 0,194 ms/op 
RemoveTest.removeIfLinkedList  avgt 30  3,634 ± 0,184 ms/op 
RemoveTest.removeIteratorArrayList avgt 30 27197,046 ± 536,584 ms/op 
RemoveTest.removeIteratorLinkedList avgt 30  3,601 ± 0,195 ms/op 

Benchmark:

@Warmup(iterations = 5, time = 1000, timeUnit = TimeUnit.MILLISECONDS) 
@Measurement(iterations = 10, time = 1000, timeUnit = TimeUnit.MILLISECONDS) 
@BenchmarkMode(Mode.AverageTime) 
@OutputTimeUnit(TimeUnit.MILLISECONDS) 
@Fork(3) 
@State(Scope.Benchmark) 
public class RemoveTest { 

    private static final int NUMBER_OF_LIST_INDEXES = 1_000_000; 
    private static final String[] words = "Testing Lamba expressions with this String array".split(" "); 

    private ArrayList<String> arrayList; 
    private LinkedList<String> linkedList; 

    @Setup(Level.Iteration) 
    public void setUp() { 
     arrayList = new ArrayList<>(); 
     linkedList = new LinkedList<>(); 
     for (int i = 0 ; i < NUMBER_OF_LIST_INDEXES ; i++){ 
      arrayList.add(words[i%6]); 
      linkedList.add(words[i%6]); 
     } 
    } 

    @Benchmark 
    public void removeIfArrayList() { 
     arrayList.removeIf(x -> x.contains("s")); 
    } 

    @Benchmark 
    public void removeIfLinkedList() { 
     linkedList.removeIf(x -> x.contains("s")); 
    } 

    @Benchmark 
    public void removeIteratorArrayList() { 
     for (ListIterator<String> it = arrayList.listIterator(arrayList.size()); it.hasPrevious();){ 
      if (it.previous().contains("s")) it.remove(); 
     } 
    } 

    @Benchmark 
    public void removeIteratorLinkedList() { 
     for (ListIterator<String> it = linkedList.listIterator(linkedList.size()); it.hasPrevious();){ 
      if (it.previous().contains("s")) it.remove(); 
     } 
    } 

    public static void main(String[] args) throws Exception { 
     Main.main(args); 
    } 

} 

Answer 2

penso che la differenza di prestazioni che stai vedendo è probabilmente dovuto più ad uso removeIf s' di un iteratore internamente vs. entrare e rimuovere nel ciclo for. Le risposte in questo PAQ hanno alcune buone informazioni sui vantaggi degli iteratori.

La risposta di bayou.io è azzeccata, è possibile vedere lo code for removeIf here esegue due passaggi per evitare di spostare gli elementi rimanenti più e più volte.

Answer 3

Perché remove(index) è molto costoso :) È necessario copiare e spostare il resto degli elementi, e questo è fatto più volte nel tuo caso.

Mentre removeIf(filter) non è necessario. Può spazzare una volta e contrassegnare tutti gli elementi da eliminare; poi la fase finale copia i sopravvissuti in cima alla lista solo una volta.