Il metodo più efficiente per le dichiarazioni switch di grandi dimensioni

Spero che questo sia solo un esperimento mentale, perché se si dispone di un programma reale con un percorso di codice distinto di migliaia selezionato da un parametro int, le considerazioni sulle prestazioni dovrebbero essere modo in basso nell'elenco delle preoccupazioni . Sembra completamente irrinunciabile.

Ma per rispondere effettivamente alla domanda: switch è O (n). Se vuoi veramente ridimensionare hai bisogno di un algoritmo O (1), quindi crei un array o un dizionario che mappa i valori interi ai delegati, seleziona il delegato in base a int e lo esegue.

Mi sbagliavo: a quanto pare un interruttore con abbastanza ramificazioni è compilato in una tabella di salto o in una ricerca del dizionario in ogni caso. Quindi non puoi fare più veloce di un interruttore.

Questa è una vera applicazione su cui stai lavorando? 1000 diversi percorsi basati su un parametro, tutti totalmente non correlati? Suppongo che se quel parametro è "codice transazione" potrebbe essere a malapena possibile. Anche lì, 1000 sono molti percorsi diversi.

Ma quello disse ...

Come nota JacquesB, un interruttore C # crea un jump table. Questo è tanto efficiente quanto arriverà fino al dispatching. Se tutti i 1000 blocchi di codice sono in un modulo, potrebbe esserci un problema nel caricare tutto in memoria.

Potresti usare if / then / else ma in media richiederebbe centinaia di test.

La seconda opzione ovvia è una tabella di hash o array in cui il valore di destinazione è un puntatore a una funzione o, in OOP-land, un riferimento a una classe contenente la funzione, in cui tutte le classi implementano la stessa interfaccia.

Se stiamo solo parlando di pura performance e ignorando tutte le nozioni di produttività e manutenibilità, è difficile battere un'istruzione switch con costanti in fase di compilazione per le espressioni del caso.

È potenzialmente persino più veloce di una tabella di salto, almeno sul lato C ++ (immagino che anche gli ottimizzatori C # siano abbastanza intelligenti). Sono stato sorpreso una volta guardando attraverso un disassemblaggio in Godbolt per una dichiarazione switch in questo modo:

switch (opcode)
{
case 0x01:
    call_some_function_which_calls_other_functions(...);
    break;
case 0x2:
    ...
}

Solo per avere un momento in cui ero estremamente confuso. Dov'è il tavolo dei salti? Poi la confusione fu seguita da un momento di stupore. Invece di usare una tabella di salto, l'ottimizzatore ha effettivamente capito che l'intera switch e le chiamate di nidi di funzione possono ridursi a una semplice LUT. Ha trasformato l'equivalente analogico sopra in qualcosa di completamente privo di rami come:

data = some_other_data[opcode];

E sono rimasto così colpito perché non ho mai nemmeno immaginato che tutta questa confusione di istruzioni switch e chiamate di funzioni nidificate con parametri passati potesse ridursi a un semplice compito da una tabella di dati di ricerca. Ho quindi esaminato tutte le chiamate di codice e di funzione e ho realizzato, "Ehi, in realtà potresti usare solo una LUT qui." Quindi, cosa può fare un ottimizzatore con alcune istruzioni switch e chiamate di funzioni nidificate che conosce in anticipo in fase di compilazione è piuttosto sorprendente.

Non mi sono ancora meravigliato quando è coinvolto il dispatch dinamico. Non ho mai visto il disassemblaggio di un tipo che suggeriva che un ottimizzatore potesse inline una chiamata di funzione che includesse dispatch virtuale fornito solo un puntatore / riferimento di riferimento o puntatore a funzione che avrebbe dovuto fare prima di poter eseguire tutte le sue magie con cose come registro assegnazione e selezione delle istruzioni. Se gli ottimizzatori C lo facessero, allora qsort sarebbe pari a std::sort di C ++ invece di prendere il doppio del tempo o più a lungo ( qsort's solo lo svantaggio concettuale è il suo uso dell'invio dinamico sul comparatore). Tuttavia, il polimorfismo spesso produce codice che è molto più facile da mantenere e sembra molto più bello.

Anche se è un po 'grossolano, ci possono effettivamente essere casi in cui è necessario separare oltre 100 diverse condizioni in uno scenario reale. Un primo esempio che ho visto è un emulatore che ha a che fare con un carico imbarcato di opcode per l'hardware di destinazione che supportava un set di istruzioni che conteneva 100 o più istruzioni.

Quindi generalmente penso a qualunque cosa tu faccia, devi fornire all'ottimizzatore tutte le informazioni che può sapere in anticipo al momento della compilazione. L'affermazione switch lo ottiene. Non tutti gli ottimizzatori sono così intelligenti nel capire in anticipo dove una chiamata di funzione che coinvolge dispatch dinamico (funzione virtuale, puntatore di funzione, ecc.) Alla fine porterà al compile-time.