Dizionario rapido lento anche con le ottimizzazioni: esecuzione di mantenimento/rilascio non appropriato?

Question

Il seguente codice, che associa i valori semplici ai valori booleani, esegue oltre 20 volte più velocemente in Java rispetto a Swift 2 - XCode 7 beta3, "Ottimizzazioni più veloci e aggressive [-Ostast]" e "Ottimizzazioni veloci, intero modulo" attivate. Posso ottenere oltre 280 milioni di ricerche/sec in Java, ma solo circa 10 milioni in Swift.

Quando lo guardo in Strumenti, vedo che la maggior parte del tempo sta entrando in una coppia di chiamate di mantenimento/rilascio associate alla ricerca della mappa. Qualsiasi suggerimento sul perché questo sta accadendo o una soluzione alternativa sarebbe apprezzato.

La struttura del codice è una versione semplificata del mio codice reale, che ha una classe di chiavi più complessa e memorizza anche altri tipi (sebbene Boolean sia un caso reale per me). Inoltre, si noti che sto utilizzando una singola istanza di chiave mutabile per il recupero per evitare di allocare oggetti all'interno del ciclo e secondo i miei test questo è più veloce in Swift di una chiave immutabile.

EDIT: Ho anche provato a passare a NSMutableDictionary ma quando usato con gli oggetti Swift come chiavi sembra essere terribilmente lento.

EDIT2: ho provato attuare il test in objc (che non avrebbe l'overhead scartare opzionale) ed è più veloce, ma ancora più di un ordine di grandezza più lento di Java ... Ho intenzione di porre quell'esempio come un'altra domanda per vedere se qualcuno ha idee.

EDIT3 - Risposta. Ho pubblicato le mie conclusioni e la mia soluzione alternativa in una risposta di seguito.

public final class MyKey : Hashable { 
    var xi : Int = 0 
    init(_ xi : Int) { set(xi) } 
    final func set(xi : Int) { self.xi = xi } 
    public final var hashValue: Int { return xi } 
} 
public func == (lhs: MyKey, rhs: MyKey) -> Bool { 
    if (lhs === rhs) { return true } 
    return lhs.xi==rhs.xi 
} 

... 
var map = Dictionary<MyKey,Bool>() 
let range = 2500 
for x in 0...range { map[ MyKey(x) ] = true } 
let runs = 10 
for _ in 0...runs 
{ 
    let time = Time() 
    let reps = 10000 
    let key = MyKey(0) 
    for _ in 0...reps { 
     for x in 0...range { 
      key.set(x) 
      if (map[ key ] == nil) { XCTAssertTrue(false) } 
     } 
    } 
    print("rate=\(time.rate(reps*range)) lookups/s") 
} 

e qui è il codice Java corrispondente:

public class MyKey { 
    public int xi; 
    public MyKey(int xi) { set(xi); } 
    public void set(int xi) { this.xi = xi; } 

    @Override public int hashCode() { return xi; } 

    @Override 
    public boolean equals(Object o) { 
     if (o == this) { return true; } 
     MyKey mk = (MyKey)o; 
     return mk.xi == this.xi; 
    } 
} 
... 
    Map<MyKey,Boolean> map = new HashMap<>(); 
    int range = 2500;  
    for(int x=0; x<range; x++) { map.put(new MyKey(x), true); } 

    int runs = 10; 
    for(int run=0; run<runs; run++) 
    { 
     Time time = new Time(); 
     int reps = 10000; 
     MyKey buffer = new MyKey(0); 
     for (int it = 0; it < reps; it++) { 
      for (int x = 0; x < range; x++) { 
       buffer.set(x); 
       if (map.get(buffer) == null) { Assert.assertTrue(false); } 
      } 
     } 
     float rate = reps*range/time.s(); 
     System.out.println("rate = " + rate); 
    } 

Answer 1

Dopo molti esperimenti sono giunto ad alcune conclusioni e ha trovato una soluzione alternativa (anche se un po 'estrema).

Prima di tutto, ammetto che questo tipo di accesso alla struttura dei dati a grana molto fine all'interno di un circuito chiuso non è rappresentativo delle prestazioni generali, ma influisce sulla mia applicazione e immagino altri come giochi e applicazioni fortemente numeriche . Inoltre, vorrei dire che so che Swift è un bersaglio mobile e sono sicuro che migliorerà - forse la mia soluzione alternativa (hack) qui sotto non sarà necessaria quando leggerete questo. Ma se stai provando a fare qualcosa di simile oggi e stai guardando gli strumenti e vedi la maggior parte del tempo di utilizzo della tua applicazione in retain/release e non vuoi riscrivere l'intera app in objc, continua a leggere.

Quello che ho trovato è che quasi tutto ciò che si fa in Swift che tocca un riferimento oggetto incorre in una penalità di conservazione/rilascio dell'ARC. Inoltre, anche i valori opzionali - anche i primitivi facoltativi - comportano questo costo. Questo praticamente esclude l'uso di Dictionary o NSDictionary.

Qui ci sono alcune cose che sono veloce che è possibile includere in una soluzione:

a) Gli array di tipi primitivi.

b) Array di oggetti finali lungo purché l'array sia nello stack e non nell'heap. per esempio. Dichiara una matrice all'interno del corpo del metodo (ma al di fuori del tuo ciclo, ovviamente) e copia iterativamente i valori su di essa. Do not Array (array) copialo.

Mettendo insieme questo è possibile costruire una struttura dati basata su array che memorizza ad es. Ints e quindi memorizza gli indici di array sugli oggetti in quella struttura dati.All'interno del tuo loop puoi cercare gli oggetti tramite il loro indice nell'array locale veloce. Prima di chiedere "impossibile che la struttura dati memorizzi l'array per me" - no, perché ciò incorre in due delle sanzioni che ho citato sopra :(

Tutto considerato questa soluzione non è male - Se è possibile enumerare le entità che si desidera archiviare nella struttura Dizionario/dati dovrebbero essere in grado di ospitarle in un array come descritto.Utilizzando la tecnica di cui sopra sono riuscito a superare le prestazioni Java di un fattore 2x in Swift nel mio caso

Se qualcuno è ancora leggendo e interessati a questo punto mi prenderà in considerazione aggiornare il mio codice di esempio e la pubblicazione

EDIT:. mi piacerebbe aggiungere un'opzione: c) e 'anche possibile utilizzare UnsafeMutablePoi nter <> o Unmanaged <> in Swift per creare un riferimento che non verrà mantenuto quando viene passato in giro. Non ero a conoscenza di questo quando ho iniziato e avrei esitato a raccomandarlo in generale perché è un trucco, ma in alcuni casi l'ho usato per avvolgere un array molto usato che stava incorrendo in un retain/release ogni volta che veniva riferimento.