attuare manualmente algoritmi ad alte prestazioni in NET

Question

come esperienza di apprendimento Recentemente ho provato attuazione Quicksort con partizionamento a 3 vie in C #.

A parte la necessità di aggiungere un controllo di gamma in più sulle variabili sinistra / destra prima della chiamata ricorsiva, sembra funzionare abbastanza bene.

Sapevo in anticipo che il quadro fornisce un incorporato implementazione Quicksort in List <>. Sort (via Array.Sort). Così ho provato un po 'di profilazione di base per confrontare le prestazioni. Risultati:.. La lista built-in <> metodo Sort, che operano sulle stesse liste, esegue circa 10 volte più velocemente di quanto la mia propria implementazione manuale

Utilizzando riflettore, ho scoperto che l'ordinamento attuale in List <>. Ordina è implementato in codice esterno, non IL (in una funzione denominata tryszsort ()).

Guardando la mia propria implementazione Quicksort Mi aspetterei che sostituendo le chiamate ricorsive con iterazione potrebbe dare qualche miglioramento. Inoltre, limiti di matrice disabilitando controllo (se possibile) potrebbe anche fornire alcuni vantaggi. Forse questo sarebbe ottenere in qualche modo più vicino alla realizzazione built-in ma non ne sono sicuro.

Quindi la mia domanda: E 'realistico aspettarsi che le prestazioni in un algoritmo ottimizzato (scritto in .NET IL, jitted in codice nativo) in grado di competere con le prestazioni di un algoritmo implementato esternamente?

Ancora una volta, mi rendo conto Quicksort è fornito come parte del quadro, questo era solo un'esperienza di apprendimento per me. Tuttavia ci sono anche molti algoritmi (CRC32 viene in mente) che non sono forniti, ma ancora potrebbe essere di grande valore per molte applicazioni. Ecco una domanda relativa per quanto riguarda attuazione CRC32 in .NET e problemi di prestazioni.

Quindi, se è necessario implementare un tale algoritmo in .NET, quali sono le principali considerazioni sulle prestazioni per capire, in modo che il vostro algoritmo può almeno avvicinare le prestazioni del codice esterno?

[Aggiornamento]

Ho migliorato la velocità di esecuzione entro circa il 10% del costruito in Array.Sort modificando l'algoritmo di operare su un semplice array di Int, anziché List. In Riflettore, posso vedere questo evita un'operazione callvirt () su ogni ottenere o impostare sulla lista. Ho pensato che questo potrebbe migliorare le cose, ma sono sorpreso di quanto.

Answer 1

Utilizzando il codice non ricorsiva e, in particolare, utilizzando blocchi "non sicuri" e l'aritmetica dei puntatori (se applicabile) potrebbero effettivamente vedere un guadagno di prestazioni x5 o x10 con un algoritmo scritto in C #. Come sempre con le prestazioni (e ancora di più quando si tratta di un ambiente gestito), non si sa mai fino a quando lo si prova e benchmark.

Ora, in generale, si dovrebbe per lo più scrivere cose in C #, quindi ottimizzarlo, ottimizzare ancora un po ', e se non è ancora abbastanza buono, di identificare l'esatto pezzo critico di codice e la porta in C ++ (facendo attenzione su limitando il numero di gestite / confini delle chiamate native).

Answer 2

Solo per curiosità, come nonostante i miei 9 anni di esperienza con .NET, ho ancora costantemente fare questo errore: Forse si compila il codice in modalità di rilascio con le ottimizzazioni su? codice di debug esegue significativamente peggiore rispetto codice di rilascio ottimizzato.

Supponendo che hai fatto compilazione in modalità di rilascio, non ci dovrebbe essere una grande differenza in termini di prestazioni se si implementa l'algoritmo simile (cioè iterativo vs. iterativa o ricorsiva vs ricorsiva). Se si desidera vedere l'implementazione .NET e capire, è possibile scaricare lo SSCLI, Share-Source Common Language Infrastructure . Questo è disponibile software di pubblico implementazione ECMA standard compliant CLI di Microsoft. Non è al 100% del framework .NET che tutti noi conosciamo e amiamo, ma è una parte significativa di esso. E 'in grado di fornire un sacco di informazioni che non può Reflector, tra cui le implementazioni interne. Tutti i tipi di codice sono disponibili, tra cui C #, C ++, e anche alcuni Assembler in un paio di casi.

Answer 3

Assicurarsi che si sta confrontando le mele e le mele.

Quando l'ordinamento, è possibile che la funzione Compare essere dominante, e che potrebbe differire tra le implementazioni.

assumendo la funzione di confronto in entrambi i casi è abbastanza veloce da non essere un problema, quindi il tempo può essere dominato da cose come limiti di matrice controllo, che può facilmente fare una grande differenza.