Dans un commutateur vs dictionnaire pour une valeur de Func, qui est plus rapide et pourquoi?
Suppose qu'il y a le code suivant:
private static int DoSwitch(string arg)
{
switch (arg)
{
case "a": return 0;
case "b": return 1;
case "c": return 2;
case "d": return 3;
}
return -1;
}
private static Dictionary<string, Func<int>> dict = new Dictionary<string, Func<int>>
{
{"a", () => 0 },
{"b", () => 1 },
{"c", () => 2 },
{"d", () => 3 },
};
private static int DoDictionary(string arg)
{
return dict[arg]();
}Par itération sur les deux méthodes et en les comparant, je suis arriver que le dictionnaire est un peu plus rapide, même lorsque "a", "b", "c", "d" est élargi pour inclure plus de touches. Pourquoi est-ce donc?
Est ce que cela a à voir avec la complexité cyclomatique? Est est parce que la gigue compile le retour des déclarations dans le dictionnaire en code natif qu'une seule fois? Est-ce parce que la recherche du dictionnaire est O(1), qui peut être pas le cas pour une instruction switch? (Ce ne sont que des suppositions)
- Le compilateur peut réellement transformer votre
switchdans un dictionnaire à un certain point, alors assurez-vous de tester avec le réel de l'entrée. - Lors de l'examen du code de langage, il semble que la seule mise en cache anonyme délégués sont pour le dictionnaire, pas pour les instructions de commutation.
- Je me demandais, pourquoi votre dictionnaire <string, Func<int>> au lieu de simplement <string, int>?
- Je veux le rendre plus général, depuis le
Funcs va changer, mais je voulais voir un dictionnaire de la valeur deFuncdans la base de cas. - Le compilateur génère du code différemment sur la base de l'interrupteur/cas.
- Rasmussen: voulez-vous dire que le compilateur ou l'interpréteur? De ce que je vois, le code généré IL est pour l'instruction switch. Cependant, je ne sais pas ce que le CLR convertit au moment de l'exécution.
- Le compilateur C# génère différents IL code en fonction de la taille de la switch/case code est.
- Comme le nombre de cas dans l'instruction switch grandit, le code généré par le compilateur peut changer à mesure que le compilateur commutateurs de tactiques et de tirer parti des tendances observées dans le code source. Je ne sais pas si désinvolte C# ou compilateurs JIT effectuer cette optimisation, mais d'un commun compilateur truc pour les instructions de commutation lorsque le cas des sélecteurs sont pour la plupart séquentielle consiste à calculer un saut de vecteur. Cela exécute en temps constant. Soustraire arg - "un", utiliser le résultat comme index dans la table de saut pour sauter, le cas échéant, bloquer.
Vous devez vous connecter pour publier un commentaire.
La réponse courte est que le commutateur d'instruction s'exécute de façon linéaire, alors que le dictionnaire s'exécute de manière logarithmique.
Au niveau IL, une petite instruction switch est généralement mis en œuvre une série de if-elseif déclarations comparant l'égalité de la commutation variable et pour chaque cas. Ainsi, cette instruction est exécutée dans un temps linéairement proportionnelle au nombre des options valides pour myVar; les cas seront comparés dans l'ordre où ils apparaissent, et le pire scénario est que toutes les comparaisons sont essayé et soit la dernière des matchs ou de aucun ne. Ainsi, avec 32 options, le pire des cas, c'est que c'est aucun d'entre eux, et le code ont fait 32 comparaisons de le déterminer.
Un Dictionnaire, d'autre part, utilise un index-collection optimisée pour stocker des valeurs. Dans .NET est un Dictionnaire est basé sur une table de hachage, ce qui a fait de la constante de temps d'accès (l'inconvénient d'être très pauvres, l'efficacité de l'espace). D'autres options couramment utilisé pour la "cartographie" des collections comme les Dictionnaires comprennent équilibrée de l'arbre de structures comme les arbres rouge-noir, qui fournissent logarithmique accès (linéaire et l'efficacité de l'espace). L'un de ceux-ci permettront le code pour trouver la clé correspondant à la bonne "case" dans la collection (ou de déterminer qu'il n'existe pas) beaucoup plus vite qu'une instruction switch peut faire la même chose.
MODIFIER: d'Autres réponses et les intervenants ont abordé ce, dans l'intérêt de l'exhaustivité, je vais bien. Le compilateur de Microsoft ne pas toujours compiler un commutateur à un if/elseif que j'ai déduit l'origine. Généralement, il le fait avec un petit nombre de cas, et/ou avec "sparse" cas (non incrémentale des valeurs, de 1, 200, 4000). Avec de plus grands ensembles adjacents cas, le compilateur se charge de convertir le commutateur dans un "saut" de table à l'aide d'un CIL déclaration. Avec les grands ensembles des rares cas, le compilateur peut mettre en œuvre une recherche binaire pour réduire le champ, et "tomber dans" un petit nombre des rares cas ou l'exécution d'un saut de table pour adjacentes cas.
Cependant, le compilateur choisit généralement la mise en œuvre qui est le meilleur compromis entre performances et l'efficacité de l'espace, de sorte qu'il n'utilise qu'une table de saut pour un grand nombre de denses cas. C'est parce qu'un saut de table nécessite un espace mémoire sur l'ordre de la gamme de cas, il doit couvrir, ce qui pour éparses cas est terriblement inefficace de la mémoire-sage. À l'aide d'un Dictionnaire dans le code source, vous essentiellement forcer le compilateur à la main; il le fera à votre place, au lieu de compromis sur la performance de gagner de la mémoire de l'efficacité.
Donc, je m'attends à la plupart des cas dans lesquels une instruction switch ou un Dictionnaire peut être utilisé dans la source à mieux performer à l'aide d'un Dictionnaire. Un grand nombre de cas dans les instructions de commutation sont à éviter, de toute façon, comme ils le sont de moins en moins gérables.
C'est un bon exemple de pourquoi la micro-benchmarks peuvent être trompeuses. Le compilateur C# IL génère différents selon la taille de l'interrupteur/cas. Le fait de passer sur une chaîne comme celle-ci
produire de l'IL qui fait essentiellement les éléments suivants pour chaque cas:
et plus tard
I. e. c'est une série de comparaisons. Afin de fonctionner le temps est linéaire.
Cependant, l'ajout d'autres cas, par exemple, pour inclure toutes les lettres de a-z, les changements de la IL a généré à quelque chose de ce genre pour chacun:
et
et enfin
I. e. il utilise maintenant un dictionnaire au lieu d'une série de comparaisons de chaînes, et obtient ainsi la performance d'un dictionnaire.
En d'autres termes le IL code généré pour ces sont différentes et c'est juste au niveau IL. Le compilateur JIT peut optimiser davantage.
TL;DR: Donc, la morale de l'histoire est de regarder les données réelles et de profil, au lieu de chercher à optimiser, à base de micro-benchmarks.
Par défaut, un interrupteur sur une chaîne de caractères est mis en œuvre comme un if /else /si /d'autre de construire.
Comme suggéré par Brian, le compilateur se charge de convertir le commutateur à une table de hachage quand il est plus grand. Bart de Smet montre ce dans cette vidéo de channel 9, (commutateur est discuté à 13:50)
Le compilateur ne le fait pas pour les 4 éléments parce que c'est d'être prudente, pour éviter que le coût de l'optimisation de l'emporter sur les avantages. La construction de la table de hachage des coûts un peu de temps et de mémoire.
Comme avec beaucoup de questions impliquant compilateur codegen décisions, la réponse est "ça dépend".
La construction de votre propre table de hachage sera probablement courir plus vite que le code généré par le compilateur, dans de nombreux cas, parce que le compilateur a d'autres coût des mesures est en essayant d'équilibrer que vous n'êtes pas: d'abord, la consommation de mémoire.
Une table de hachage à utiliser plus de mémoire que d'une poignée de si-alors-sinon IL instructions. Si le compilateur cracher une table de hachage pour chaque instruction switch dans un programme, l'utilisation de la mémoire allait exploser.
Que le nombre de blocs dans l'instruction switch grandit, vous aurez probablement voir le compilateur produire un code différent. Plus de cas, il n'y a plus de raison pour le compilateur d'abandonner les petites et simple si-alors-sinon motifs en faveur de la plus rapide, mais plus gros des solutions de rechange.
Je ne sais pas si désinvolte C# ou compilateurs JIT effectuer cette optimisation, mais d'un commun compilateur truc pour les instructions de commutation lorsque le cas de sélecteurs sont nombreux et la plupart du temps séquentiel est de calculer un saut de vecteur. Ce qui nécessite plus de mémoire (sous la forme d'généré par le compilateur, sauter tables intégrées dans le flux de code) mais s'exécute en temps constant. Soustraire arg - "un", utiliser le résultat comme index dans la table de saut pour sauter, le cas échéant, bloquer. Boom, yer fait, indépendamment de savoir si il y a 20 ou 2000 cas.
Un compilateur est susceptible de passer dans saut de table de mode lorsque l'interrupteur est de type char ou int ou enum et les valeurs de l'affaire, les sélecteurs sont principalement séquentielles ("dense"), étant donné que ces types peuvent facilement être soustrait à créer un décalage ou d'un index. Chaîne de sélecteurs sont un peu plus difficile.
Chaîne de sélecteurs sont des "internés" par le compilateur C#, sens le compilateur ajoute la chaîne de sélecteurs de valeurs à un pool interne de chaînes uniques. L'adresse ou le jeton d'un interné chaîne peut être utilisée comme son identité, permettant int-comme optimisations lors de la comparaison de stagiaire avais chaînes d'identité /octet-sage de l'égalité. Avec un nombre suffisant de cas de sélecteurs, le compilateur C# va produire du code IL qui regarde le stagiaire avais l'équivalent de l'arg chaîne (table de hachage de recherche), puis de comparer (ou sauter tables) les internés jeton avec le précalculées cas sélecteur de jetons.
Si vous pouvez coaxial le compilateur dans la production de sauter-table de code dans le char/int/enum sélecteur de cas, cette exécution est plus rapide que d'utiliser votre propre table de hachage.
Pour la chaîne sélecteur cas, le code IL reste à faire un hachage de recherche de sorte que toute différence de performances à partir de votre propre table de hachage est probablement laver.
En général, cependant, vous ne devriez pas m'attarder sur ces compilateur nuances trop lors de l'écriture de code de l'application. Instructions de commutation sont généralement beaucoup plus facile à lire et à comprendre que le hachage est un tableau de pointeurs de fonction. Instructions de commutation qui sont assez grand pour pousser le compilateur à sauter de la table de mode sont souvent trop gros pour être humainement lisible.
Si vous trouvez une instruction switch est dans une performance hotspot de votre code, et vous avez mesuré avec un générateur de profils qu'il a des impact sur les performances, la modification de votre code pour utiliser votre propre dictionnaire est un compromis raisonnable pour un gain de performance.
L'écriture de votre code pour utiliser une table de hachage depuis le début, sans les mesures de performance pour justifier ce choix, est de plus en plus de l'ingénierie qui va conduire à insondable du code inutilement hausse des coûts de maintenance. Garder Les Choses Simples.