I linguaggi OO moderni possono competere con le prestazioni dell'Array Store di C ++?

40

Ho appena notato che ogni linguaggio di programmazione OO moderno con cui ho almeno una certa familiarità (che è fondamentalmente solo Java, C # e D) consente matrici covarianti. Cioè, un array di stringhe è un array di oggetti:

Object[] arr = new String[2];   // Java, C# and D allow this

Gli array di covarianti sono un buco nel sistema di tipi statici. Rendono possibili errori di tipo che non possono essere rilevati in fase di compilazione, quindi ogni scrittura su un array deve essere verificata in fase di runtime:

arr[0] = "hello";        // ok
arr[1] = new Object();   // ArrayStoreException

Questo mi sembra un terribile colpo di prestazioni se faccio un sacco di negozi di array.

C ++ non ha array covarianti, quindi non c'è bisogno di fare un tale controllo di runtime, il che significa che non c'è penalità di prestazioni.

Esiste qualche analisi per ridurre il numero di controlli di runtime necessari? Ad esempio, se dico:

arr[1] = arr[0];

si potrebbe sostenere che il negozio non può fallire. Sono sicuro che ci sono molte altre ottimizzazioni possibili a cui non ho pensato.

I compilatori moderni eseguono effettivamente questi tipi di ottimizzazioni, oppure devo convivere con il fatto che, ad esempio, un Quicksort esegue sempre O (n log n) controlli di runtime non necessari?

I moderni linguaggi OO possono evitare l'overhead creato supportando gli array in co-variante?

    
posta fredoverflow 17.01.2012 - 22:48
fonte

8 risposte

33

D non ha matrici covarianti. Li ha consentiti prima della versione più recente ( dmd 2.057 ), ma bug è stato corretto.

Un array in D è effettivamente solo una struttura con un puntatore e una lunghezza:

struct A(T)
{
    T* ptr;
    size_t length;
}

Il controllo dei limiti viene eseguito normalmente durante l'indicizzazione di un array, ma viene rimosso quando si compila con -release . Quindi, in modalità di rilascio, non c'è una reale differenza di prestazioni tra gli array in C / C ++ e quelli in D.

    
risposta data 17.01.2012 - 23:19
fonte
21

Sì, un'ottimizzazione fondamentale è questa:

sealed class Foo
{
}

In C #, questa classe non può essere un supertipo per alcun tipo, quindi puoi evitare il controllo di un array di tipo Foo .

E alla seconda domanda, in array di co-variant F # non sono consentiti (ma suppongo che il controllo rimarrà nel CLR a meno che non sia trovato non necessario nelle ottimizzazioni in fase di runtime)

let a = [| "st" |]
let b : System.Object[] = a // Fails

link

Un problema in qualche modo correlato è il controllo dei limiti dell'array. Questa potrebbe essere una lettura interessante (ma vecchia) sulle ottimizzazioni fatte nel CLR (la covarianza è anche menzionata in 1 posizione): link

    
risposta data 17.01.2012 - 22:51
fonte
13

Risposta Java:

Suppongo che tu non abbia effettivamente messo a confronto il codice, vero? In generale il 90% di tutti i cast dinamici in Java sono gratuiti perché il JIT può elidirli (quicksort dovrebbe essere un buon esempio per questo) e il resto sono una sequenza ld/cmp/br che è assolutamente prevedibile (se no, beh, perché diavolo è il tuo codice che lancia tutte quelle eccezioni di cast dinamico?).

Facciamo il carico molto prima del confronto effettivo, il ramo è correttamente previsto nel 99,999% (statistiche inventate!) di tutti i casi quindi non blocchiamo la pipeline (supponendo che non colpiamo la memoria con il caricare, se non bene che sarà evidente, ma poi il carico è necessario comunque). Quindi il costo è 1 ciclo di clock SE il JIT non può evitare il controllo.

Qualche overhead? Certo, ma dubito che te ne accorgerai mai ...

Per aiutare a supportare la mia risposta, consulta questo Dr. Cliff Click blogpost che discute prestazioni Java vs. C.

    
risposta data 17.01.2012 - 23:19
fonte
10

D non consente matrici covarianti.

void main()
{
    class Foo {}
    Object[] a = new Foo[10];
}  
/* Error: cannot implicitly convert expression (new Foo[](10LU)) of type Foo[]
to Object[] */

Come dici tu, sarebbe un buco nel sistema dei tipi per consentire questo.

Puoi essere perdonato per l'errore, poiché questo bug è stato corretto solo nel ultimo DMD, pubblicato il 13 dicembre.

L'accesso alla matrice in D è veloce come in C o C ++.

    
risposta data 17.01.2012 - 23:19
fonte
5

Da test effettuato su un laptop economico, la differenza tra l'utilizzo di int[] e Integer[] è di circa 1,0 ns. La differenza è probabilmente dovuta al controllo extra per il tipo.

Generalmente gli oggetti vengono utilizzati solo per la logica di livello superiore quando non conta ogni ns. Se hai bisogno di salvare ogni ns, eviterei di usare costrutti di livello superiore come Oggetti. Le assegnazioni da sole sono probabilmente un fattore molto piccolo in qualsiasi programma reale. per esempio. la creazione di un nuovo oggetto sullo stesso computer è di 5 ns.

Le chiamate da confrontarePuò essere molto più costose, specialmente se si utilizza un oggetto complesso come String.

    
risposta data 18.01.2012 - 00:11
fonte
2

Hai chiesto informazioni su altre lingue OO moderne? Bene, Delphi evita completamente questo problema avendo string essere un primitivo, non un oggetto. Quindi una serie di stringhe è esattamente una serie di stringhe e nient'altro, e qualsiasi operazione su di esse è veloce quanto il codice nativo può essere, senza alcun tipo che controlli l'overhead.

Tuttavia, gli array di stringhe non vengono utilizzati molto spesso; I programmatori Delphi tendono a preferire la classe TStringList . Per un importo minimo di overhead fornisce una serie di metodi string-group che sono utili in così tante situazioni che la classe è stata confrontata con un coltellino svizzero. Quindi è idiomatico usare un oggetto lista di stringhe invece di un array di stringhe.

Come per altri oggetti in generale, il problema non esiste perché in Delphi, come in C ++, gli array non sono covarianti, al fine di prevenire il tipo di buchi di sistema del tipo qui descritto.

    
risposta data 18.01.2012 - 00:01
fonte
1

or do I have to live with the fact that, for example, a Quicksort always does O(n log n) unnecessary runtime checks?

Le prestazioni della CPU non sono monotone, il che significa che i programmi più lunghi possono essere più veloci di quelli più corti (dipende dalla CPU, ed è vero per le architetture x86 e amd64 comuni). Quindi è possibile che un programma che esegue il controllo dei vincoli sugli array sia effettivamente più veloce del programma dedotto dal precedente rimuovendo questi controlli associati.

Il motivo di questo comportamento è che il controllo associato modifica l'allineamento del codice in memoria, modifica la frequenza degli accessi alla cache, ecc.

Quindi sì, convivi con il fatto che Quicksort esegue sempre controlli spuri di O (n log n) e ottimizza dopo la profilazione.

    
risposta data 09.01.2014 - 13:01
fonte
1

Scala è un linguaggio OO che ha matrici invarianti, piuttosto che covarianti. Si rivolge alla JVM, quindi non ci sono prestazioni vincenti, ma evita una disfunzione comune a Java e C # che compromette la sicurezza del proprio tipo per motivi di compatibilità con le versioni precedenti.

    
risposta data 09.01.2014 - 16:02
fonte

Leggi altre domande sui tag