En tant qu'expérience d'apprentissage, j'ai récemment essayé de mettre en œuvre Quicksort avec partitionnement à 3 voies < / a> en c #.
En plus d'avoir besoin d'ajouter une gamme supplémentaire Vérifiez sur les variables gauche / droite avant l'appel récursif, il semble fonctionner très bien.
Je savais à l'avance que le framework fournit un Mise en œuvre QuickSort intégrée la liste <>. Trier (via Array.sort). J'ai donc essayé un profilage de base pour comparer les performances. Résultats: La liste intégrée <>. La méthode de tri, fonctionnant sur les mêmes listes, effectue environ 10 fois plus vite que ma propre implémentation manuelle.
Utilisation du réflecteur, j'ai trouvé que le tri réel de la liste <>. Trier est implémenté dans le code externe, pas IL (dans une fonction nommée Tryszsort ()).
En regardant ma propre implémentation QuicksTort, je m'attendrais à ce que le remplacement des appels récursifs avec itération pourrait donner une certaine amélioration. En outre, la vérification des limites de la graisse désactivée (si possible) pourrait également donner des avantages. Peut-être que cela se rapprocherait de la mise en œuvre intégrée, mais je ne suis pas confiant.
Donc, ma question: est-il réaliste d'attendre des performances dans un algorithme optimisé (écrit en .NET IL, jets au code natif) peut concurrencer des performances d'un algorithme mis en œuvre de manière externe?
Encore une fois, je réalise que le QuickSort est fourni dans le cadre du cadre, il s'agissait simplement d'une expérience d'apprentissage pour moi. Cependant, il existe également de nombreux algorithmes (CRC32 vient à l'esprit) qui ne sont pas fournis, mais pourraient toujours être de beaucoup de valeur pour de nombreuses applications. Voici une question connexe concernant Mise en œuvre CRC32 dans .NET et problèmes de performance.
Donc, si vous devez mettre en œuvre un tel algorithme dans .NET, quelles sont les principales considérations de performance à comprendre, de sorte que votre algorithme puisse au moins aborder les performances du code externe?
[MISE À JOUR]
J'ai une vitesse d'exécution améliorée à l'intérieur d'environ 10% de l'array intégré.sort en modifiant l'algorithme pour fonctionner sur un tableau simple d'int, au lieu de la liste. Dans le réflecteur, je peux voir que cela évite une opération CallVirt () sur chaque get ou défini sur la liste. Je pensais que cela pourrait améliorer les choses, mais je suis surpris par combien.
3 Réponses :
En utilisant un code non récursif et, en particulier en utilisant des blocs "dangereux" et l'arithmétique de pointeur (le cas échéant), vous pourrait voir un gain de performance x5 ou x10 avec un algorithme écrit en C #.
Comme toujours avec la performance (et encore plus lorsqu'il s'agit d'un environnement géré), vous ne savez jamais que vous n'en savez jamais jusqu'à ce que vous l'essiez et que vous l'asseyez.
Maintenant, d'une manière générale, vous devriez surtout écrire des trucs dans C #, puis l'optimiser, l'optimiser d'autres, et si ce n'est toujours pas assez bon, identifiez la pièce de code critique exacte et le portez-le à C ++ (tout en faisant attention à ce que ce soit. limiter le nombre de limites d'appel gérées / natifs).
Points intéressants sur le mode dangereux. J'ai essayé d'éviter cela par défaut, mais dans certains cas, le pointeur arithmétique pourrait être la seule option. Je suis tout à fait d'accord sur l'approche d'optimisation, j'essaie également de ne pas vous faire prendre sur des micro-optimisations; L'amélioration de la conception globale peut donner une amélioration de bien meilleure approche.
+1, mais pourriez-vous élaborer comment un bloc non coché augmenterait les performances ici? Parce que non cochée est la valeur par défaut, et je ne pense pas que cela ait un effet sur les chèques de liaison Array.
Notez que le portage à C ++ ne donnera pas toujours une prestation de perf indemnité, car il y a une pénalité pour les appels gérés à un géré à l'aide de P / invoke, en raison de l'appel d'une inadéquation de la convention, et du fait que CDECL et STDCall poussent les arguments à enregistrer . La plupart des méthodes externe dans la BCL utilisent la convention d'appel "rapide" qui s'appuie sur un code natif implémentant la méthode connaissant les détails de la mise en œuvre du CLR, de sorte qu'ils ne paient pas ce prix.
Bon points Pavel. C'est pourquoi j'ai dit de faire attention aux frontières autochtones / gérées, mais je ne l'ai pas expliqué. Julian, je ne pense pas que "non cochée" est la valeur par défaut, car vous obtenez des exceptions des limites si vous utilisez des index incorrects.
Les matrices sont toujours des liaisons vérifiées, à moins que le compilateur ne puisse déduire, il n'est pas nécessaire ou si vous utilisez le pointeur arithmétique. Les blocs non contrôlés n'ont aucun effet ici Afaik. Ce que je veux dire par "décoché" par défaut "est que les débordements de types primitifs par défaut ne génèrent pas d'exceptions à moins que vous ne l'enveloppez dans un bloc cochée ou utilisez l'option Compiler. Et lors de l'utilisation de l'option Compiler, non coché permet au bloc de se comporter comme la valeur par défaut. Sauf si je me trompe, non coché n'a aucun rôle dans les optimisations de performance.
Ah oui, j'ai eu la chose "non cochée" à nouveau (oui, ce n'est pas la première fois que je pense que ça fait autre chose :)). Merci!
juste hors de curiosité, comme malgré mes 9 années d'expérience avec .net, je fais toujours cette erreur: avez-vous compilé votre code en mode de sortie avec des optimisations? Le code de débogage effectue considérablement pire que le code de libération optimisé.
En supposant que vous avez compilé en mode de sortie, il ne devrait pas y avoir une énorme différence de performance si vous implémentez l'algorithme de la même manière (c'est-à-dire itératif contre itératif ou récursif vs. récursif). Si vous souhaitez voir la mise en œuvre et la sortie .NET, vous pouvez télécharger le SSCLI, Infrastructure de langue commune partagée . Il s'agit d'une mise en œuvre de CLI conformément à la CLI conformément à la CPIM de Microsoft. Ce n'est pas 100% du cadre .NET que nous connaissons et aimons tous, mais c'est une partie importante de celle-ci. Il peut fournir beaucoup d'informations que le réflecteur ne peut pas, y compris les implémentations internes. Tous les types de code sont disponibles, y compris C #, C ++ et même un assembleur dans quelques cas.
Oui, j'ai compilé en mode de sortie, mais je n'ai pas vérifié explicitement aucune optimisation, j'ai supposé que la définition de la définition est suffisante. Je vais devoir regarder cela, alors merci pour le conseil. Merci Aso pour le lien vers le SSCLI aussi. Intéressant de voir si / comment la sorte est implémentée.
"Le code de débogage fonctionne considérablement que le code de libération optimisé." - En réalité, ce n'est pas vrai pour .NET; La performance pour les deux est généralement comparable. Ce qui compte vraiment, c'est que vous avez ou non le débogueur attaché - le JIT (qui fait la plupart des optimisations) n'étitements pas par défaut lorsque le débogueur est attaché (c.-à-d. Lors de la course dans Visual Studio). Vous pouvez modifier ceci dans VS sous Outils-> Options-> Débogage-> Suppress Jit Optimisation
@Blueraja: Ce n'est pas vrai. L'optimisation JIT est un drapeau de métadonnées d'assemblage et désactive entièrement les optimisations, le débogage ou autrement. J'ai effectué des tests assez vastes, en particulier avec WCF et ASP.NET, avec des modes de débogage et de libération, aucun débogueur attaché. Mode de débogage, les optimisations JIT désactivées, sont nettement plus lentes. Par exemple, un simple service de calculatrice WCF (Ajouter, Sub, DIV, MUL) exploité à ~ 180MSG / S lorsque le mode de débogage a été activé ... ~ 30 000 msg / s lorsque le mode de libération a été activé. Aucun débogueur n'a été attaché. Différences similaires avec certains aspects de ASP.NET.
Oui, désolé, j'ai parlé trop de langue dans la joue. Ce que je voulais dire était, ce qui compte vraiment est si l'optimiseur JIT est activé. Ceci est désactivé par défaut lorsque le débogueur est joint. Il est partiellement activé dans la construction de débogage, mais peut être entièrement réactivé avec certaines drapeaux .ini . Toutefois, la raison pour laquelle WCF est de sorte que beaucoup plus lentement dans la construction de débogage n'a rien à voir avec l'une de ces informations - WCF ajoute du code de diagnostic / des messages lorsque le symbole de débogage est trouvé. Il utilise également l'hôte de service VS WCF (plutôt que l'IIS), qui est destiné strictement pour le développement.
Hmm, nos tests ont été hébergés dans IIS 7.0 à l'époque ... Je ne pense pas à quoi la cause de la lenteur pendant le débogage compte vraiment. Je sais que beaucoup de code Microsoft implique beaucoup de traçage et d'autres indésirections de diagnostic lorsque le "mode" de débogage est activé (et tous les indicateurs de compilateur et autres paramètres qui l'accompagnent.) Depuis la grande majorité du code de développeur .NET est construit sur Le .NET Framework, toute la malbouffe de diagnostic de Microsoft est titulaire de votre propre code chaque fois que vous l'appelez. Il y a beaucoup de raisons pour vous assurer que vous construisez le code de libération pour le produit final ... sinon le PERF a frappé pourrait être grand!
Assurez-vous de comparer des pommes et des pommes.
Lors du tri, il est possible que la fonction de comparaison soit dominante, et cela pourrait différer entre les implémentations.
En supposant que la fonction de comparaison dans les deux cas est suffisamment rapide pour ne pas être un problème, le temps peut être dominé par des trucs comme la vérification des limites de la matrice, ce qui peut facilement faire une grande différence.
Bon conseil. Dans ce cas, je n'utilise actuellement que les comparaisons de base int32. J'ai trouvé que le tri d'un tableau Int simple est beaucoup plus rapide qu'une liste
J'ai toujours été sous l'impression que la plupart des implémentations de tri rapides basculeront sur la tresse de fusion après avoir décroissant un nombre prédéterminé de niveaux de récursivité. Souhaitez-vous afficher votre code pour voir les zones d'amélioration?