L'optimisation de object pascal

L'optimisation de object pascal

L'optimisation de object pascal : Plusieurs milliers de conseils pour vous faciliter la vie.

Une histoire d'optimisation.

l'Optimisation de Object Pascal
Cet article se penche sur l'optimisation de code Delphi base sur le standard des techniques, la comprehension de la matiere du programme et un cas de pure dumb luck. Un poker bibliotheque est utilisee pour illustrer ces points.
C'est une histoire a propos d'un simple poker de la bibliotheque et de l'optimisation de code en Delphi. Le poker de la bibliotheque a commence comme un Turbo Pascal projet d'annees, que j'avais eu l'intention de se convertir a Delphes pour un certain temps. Comme c'est arrive, Delphi 5 a frappe les etageres avant que je trouve le temps de faire la conversion.
Ma premiere etape a ete la refonte de la bibliotheque comme un objet-oriente le projet. Le code d'origine avait ete purement procedurale. Dans son nouveau format, la bibliotheque dispose de trois classes pour la programmation des jeux de poker. Ces sont, curieusement - une carte de classe, un pont de classe et d'une classe. Le pont et la main sont les descendants d'une carte a la liste de classe. La bibliotheque prend en charge les jeux de poker, qui utilisent des mains de cinq cartes ou plus, a un support pour haute et basse variations et prend en charge les cartes sauvages. C'est cette derniere fonctionnalite qui s'est avere le plus difficile. J'ai fini la construction d'une bibliotheque complete avec pas de wild card support et utilise comme base pour la wild card version.
Pour valider la bibliotheque, j'ai construit une serie de neuf applications de test. Ces programmes inclus pour tester la creation et le brassage d'un jeu de cartes, pour me permettre de choisir cinq cartes et de les evaluer comme une main de poker, un programme qui a traite et evalue les mains de cinq cartes de tous type standard, un programme qui a fait la meme pour les sept mains de cartes, un jeu de video poker et les quatre points de reference pour tester la vitesse de la bibliotheque avec des cartes sauvages et sans.
Il a fallu deux semaines pour construire la bibliotheque et le processus s'est bien deroule. J'ai ete en mesure d'utiliser une bonne partie de la vieille Pascal code. Cela s'est avere etre a la fois bon et mauvais. Bon, parce qu'il a accelere la conversion. Dommage, car j'ai fait une petite erreur qui je l'expliquerai plus tard. Dans un autre couple de semaines, le projet a ete teste et complete, sauf pour un petit probleme. Il etait trop lent pour etre d'une quelconque utilite. Ainsi commence notre aventure. Les resultats de la premiere vitesse essais sont repertories dans le Tableau 1.

Table 1. La Wild Card de la Bibliotheque de Reference - Temps en secondes
Delphi 5 sur un Pentium II 400Mhz avec 128 mo de RAM
L'indice de reference des programmes sont tres simples. Chaque programme cree tous les possibles mains de cinq cartes dans un jeu de cartes. Il appelle ensuite la SetHighValues methode de la main de l'objet, qui evalue la main et retourne une cote elevee et un haut de nom. La cote elevee est un entier long utilise comme un champ de bits. La faible vingt bits contiennent les rangs des cartes de poker standard de la commande. L'ordre onze bits contiennent le type de main. (Pour une explication plus detaillee, voir la source de bibliotheque, qui est disponible pour le telechargement.) Cela permet a un programme de poker pour comparer les valeurs des deux mains en comparant leurs notes elevees. Par exemple:
& nbsp & nbsp si la Main[1].HiRating > Main[2].HiRating puis
Le programme de test utilise la haute notation pour determiner le type de la main et conserve un nombre sur tous les types et le nombre total de mains. Cela sert comme une validation plus poussee de la bibliotheque de routines. Dans un de 52 cartes standard de pont, il y a 2,598,960 possible mains de cinq cartes, quatre chasses royales, 5,108 standard bouffees de chaleur etc. Si l'indice de reference des rapports differents numeros, nous savons qu'il existe un probleme avec les procedures d'evaluation.
Comme vous pouvez le voir, chaque joker utilise conduit a environ 80% de la baisse de la vitesse. Je n'ai pas pris la peine de l'execution de l'deuces wild de reference. Les deux jokers de reference a pris environ une heure et quart pour terminer. Le deuces wild de reference aurait pris un estimee a vingt-cinq heures.
le Rendant plus Rapide
La premiere etape est de trouver quels sont les domaines qui posent probleme. Les criteres de reference eux-memes point a une zone qui a besoin de travail. La methode utilisee pour les taux de wild card mains montants a la conversion des sauvages de la carte dans tous les possible des cartes de remplacement, et puis l'appel de l'evaluation reelle de routines. Il est clair que ce pourrait utiliser un peu de travail.
Pour trouver d'autres pistes d'amelioration, j'ai sorti mon fidele profileur de code. Je utiliser un Chronometre, une partie de Sleuth QA de TurboPower. Il y a d'autres, et chaque programmeur devrait en avoir un. J'ai couru le pas de cartes sauvages de reference en vertu de la profiler et attendu pour le rapport. En fait, je suis alle au lit. Puisque la bibliotheque est un petit peu lent, j'ai couru le profil de la nuit. Le lendemain matin, 273 millions d'appels de fonction plus tard, les resultats ont ete dans. Voir Le Tableau 2.

Table 2. Dix plus appele routines dans le poker bibliotheque.
Chronometre revient beaucoup d'informations. Il y a des timings sur chaque routine appelee et le pourcentage du total des montants. Dans ce cas, une partie de l'information la plus importante est dans le tableau ci-dessus.
La premiere chose a noter, c'est qu'il y a pres de 195 millions d'appels a la GetCard methode. Ce qui est attendu. Chaque main evaluees par le SetHighValues methode genere 25 appels a GetCard. Chaque appel a CopyCardFromDeck genere plus de dix. Le total est correct. Si le total pour CopyCardFromDeck. De plus, un rapide coup d'œil a la liste indique il n'y en a pas beaucoup qui peut etre change dans l'une de ces routines. Ils sont essentiellement juste les instructions d'affectation.
Il est temps de penser comme un joueur de poker a la place d'un programmeur. Il y a 2,598,960 possible de cinq cartes a la main dans un jeu de cartes. Quarante de ces droites bouffees de chaleur et les quatre de la droite les bouffees de chaleur sont un flush royal. Il y a 5,108 lignes droites et de 10 200 bouffees de chaleur dans un jeu standard. Le nombre d'appels a IsStraight, IsFlush et surtout a IsStraightFlush sont moyen de sortir de la ligne. Chaque main est teste a trois reprises pour voir si elle est droite. (en Fait 2.996336996336996336996336996337 fois, mais pourquoi chipoter?)
SetHiValNoWC est le cheval de bataille du poker de la bibliotheque pour l'evaluation des mains elevees. Il teste chaque main est passe et trouve de quel type il est. Puis il met la main, lui donne un numerique, de notation et d'un nom approprie. Pour ce faire, il appelle la IsStraight fonction, et plusieurs autres. Il le fait de belle façon securitaire, avec les comparaisons tries du plus haut au plus bas. C'est la l'un de nos problemes se trouve.
Chaque main est teste pour voir si cinq d'un genre. Si elle l'est, nous avons termine. Si non, il est teste pour voir si c'est une quinte flush royale. Cela signifie que les tests pour voir si elle est droite, un flush, quinte flush, et enfin, un royal. Si c'est une quinte flush royale, il verifie pour voir si c'est une royale naturelle ou si elle utilise des cartes sauvages. De toute façon, nous sommes fait. Si c'est pas royal, il est ensuite testee pour voir si c'est une quinte flush, donc le test pour les lignes droites est repete. Vous voyez le probleme? C'est un mauvais algorithme.
Optimisation 1
Notre premiere amelioration consiste a changer l'ordre des tests. Cette fois, au lieu de le faire de façon securitaire, je vais essayer de le faire de la maniere habile. Il y a probablement de nombreuses solutions. De combien de façons peut-dix tests? Ouch! Encore une fois, il est temps de mettre sur mon poker chapeau.
les mains de Poker peut etre decomposee en deux types distincts. Le premier type contient deux ou plus de deux cartes de meme rang. Toutes les paires, deux paires de mains, des voyages, un full, un carre, et cinq d'une sorte de mains entrent dans cette categorie. La deuxieme categorie comprend toutes les mains sans cartes de correspondance rang. Ces inclure des quintes flush royale, quinte flush, quinte, les bouffees de chaleur et haut de la carte des mains. A la haute main de la carte est defini comme cinq cartes sans.)
Cela divise le probleme en deux petits problemes. Dans chaque cas, nous voulons tester une main contre un type particulier qu'une seule fois et nous preferons tester pour les plus rares les mains apres le plus commun. Pseudo-code pour une solution partielle est dans le listing 1.
Cotation 1. Pseudo-code pour les nouvelles de la main de test de commande.
{test premier groupe - les mains avec des cartes de meme rang }
si isOnePair puis
& nbsp & nbsp si isThreeOfAKind puis
& ! & ! & ! & nbsp si isFourOfAKind puis
& ! & ! & ! & ! & ! & nbsp si IsFiveOfAKind puis
& ! & ! & ! & ! & ! & ! & ! & nbsp faire cinq d'une sorte de traitement de
& ! & ! & ! & ! & ! & nbsp else { pas cinq, mais quatre d'un genre }
& ! & ! & ! & ! & ! & ! & ! & nbsp quatre d'une sorte de traitement de
& ! & ! & ! & ! & ! & nbsp fin
& ! & ! & ! & nbsp fin
& nbsp & nbsp else
& nbsp & nbsp si isFullHouse puis
& ! & ! & ! & nbsp complete une maison de traitement de
& nbsp & nbsp else { non, seulement les deplacements }
& ! & ! & ! & nbsp trois d'une sorte de traitement de
& nbsp & nbsp end { si isThreeOfAKind }
{ aucun accord sur les adpic, comment environ deux paires }
else
& nbsp & nbsp si isTwoPairs puis
& ! & ! & ! & nbsp faire deux paires de traitement de
end { si isTwoPairs }
else
& nbsp & nbsp faire une paire de traitement de
end { si isOnePair }
on dirait qu'il doit faire mieux, mais c'est le probleme de beaucoup plus complique de travailler avec. Apres la mise en œuvre de cette, je l'ai teste et corrige les bugs qui ont ete introduites. N'utilisant pas de cartes sauvages, la bibliotheque pourrait maintenant le taux de 25 800 mains par seconde. C'est une bonne amelioration. Cependant, il n'est pas encore assez bon. L'analyse comparative de deux wild cards encore pres d'une heure a dix heures pour quatre.
Optimisation 2
en remontant vers le profil, je vois que SwapCards est appele beaucoup de choses. Donc, nous devrions verifier son code et trouver les endroits a partir de laquelle il est appele. Le code est simple a la vanille. Il n'existe aucun moyen court de langage d'assemblage pour le rendre plus rapide. Toutefois, le tri routine appelle SwapCards au lieu de faire son propre echange. La routine de tri sont enumeres ci-dessous:
procedure SortCardsLowToHigh(var Main: TcaaEvaluationHand)
var
& nbsp & nbsp leftCardPos, rightCardPos : integer
begin
& nbsp & nbsp pour leftCardPos := 2 a 5 ne
& ! & ! & ! & nbsp pour rightCardPos := 5 downto leftCardPos ne
& ! & ! & ! & ! & ! & nbsp si la Main[rightCardPos-1].Grade >
& ! & ! & ! & ! & ! & ! & ! & ! & nbsp Main[rightCardPos].Grade
& ! & ! & ! & ! & ! & ! & ! & ! & ! & ! & nbsp SwapCards(a la Main,rightCardPos-1,rightCardPos)
fin
Changer le code pour faire son propre permutation permettra d'economiser un appel de fonction, a chaque fois qu'un echange est fait. La routine de tri est lui-meme appele a plus de quatre millions de fois. Cela devrait nous donner un peu plus de vitesse. Il peut egalement etre possible d'ameliorer le tri lui-meme. J'ai passe un peu de temps a essayer d'autres algorithmes, mais theoriquement plus rapide sortes abouti a aucune amelioration et dans de nombreux cas, a ralenti les choses. La raison pour cela est la longueur du tableau combine avec le traitement de nombreuses autres methodes de tri.
Optimisation 3 - la Fixation d'une Erreur
Il est temps de regarder la IsFlush de la fonction et de l'ensemble de ses freres et sœurs. Le code est donne ci-dessous:
fonction de IsFlush(Main: TcaaEvaluationHand): Boolean
begin
& nbsp & nbsp Result := False
& nbsp & nbsp si (a la Main[1].Costume = Main[2].Costume) et (Main[1].Costume = Main[3].Costume
& ! & ! & ! & nbsp et (a la Main[1].Costume = Main[4].Costume)
& ! & ! & ! & nbsp et (a la Main[1].Costume = Main[5].Costume) then Result := True
fin
Rien a faire ici. Ou est-il? La Main parametre est un tableau d'enregistrements et il est passe comme un parametre standard - ce qui signifie sur la pile. Oups. Erreur stupide. C'est le code que j'ai copie la forme originale de Pascal bibliotheque. Les seuls changements que j'ai faits etaient d'assigner a la variable Resultat a la place du nom de la fonction. J'ai fait quelque chose qui n'etait pas necessaire, au lieu de quelque chose qui aurait aide. Faisant de la Main un parametre const permettra d'ameliorer la vitesse grandement.
ensuite, je suis alle a travers le reste du code pour trouver les tableaux, les dossiers ou les chaînes de caracteres passees a des fonctions comme des parametres standards. Oui, j'ai trouve beaucoup d'entre eux. Avec cette installation, la bibliotheque peut evaluer 38,900 mains par seconde a l'aide de pas de cartes sauvages. A l'aide d'un joker donne un respectable de 9 800 mains par seconde.
Optimisation 4
ensuite, j'ai regarde ce que les resultats de reference sont a la pointe. N'oubliez pas que chaque carte joker est l'ajout d'environ 80% de la vitesse de la peine. Les raisons ont ete expliquees precedemment. J'ai attendu de le corriger car je n'avais pas compris de quoi faire. Regardons une petite partie du code.
les caracteres generiques := NumWildCards(a la Main)
cas des caracteres generiques de
& nbsp & nbsp 0 : { pas etre interesse par ce }
& nbsp & nbsp 1 : begin { Une Wild Card }
& ! & ! & ! & ! & ! & ! & ! & nbsp pour wc5 := caaClubAce a caaSpadeKing ne
& ! & ! & ! & ! & ! & ! & ! & nbsp commencer
& ! & ! & ! & ! & ! & ! & ! & ! & ! & nbsp TempHand := la Main
& ! & ! & ! & ! & ! & ! & ! & ! & ! & nbsp TempHand[5].Rang := TcaaRank((wc5) mod 13)
& ! & ! & ! & ! & ! & ! & ! & ! & ! & nbsp TempHand[5].Costume := TcaaSuit((wc5) div 13)
ai-je vraiment besoin de tester tous les cinquante-deux cartes? C'est certainement la chose la plus sûre a faire, comme un premier essai. Elle fonctionne. Mais c'est sûr qu'il est lent. Le temps de mettre sur mon poker chapeau encore une fois. Tous les treize rangs doivent etre testes. Dois-je tester tous les quatre couleurs? Non, je n'ai pas. Voici pourquoi. La seule signification du costume est a determiner si la main est une forme de chasse d'eau. La seule maniere d'un costume peut faire une difference si elle correspond a la combinaison des autres cartes. Je peux juste cocher l'une des cases (non sauvage) cartes et les utiliser uniquement une couleur. Voici ce que le nouveau code ressemble.
les caracteres generiques := NumWildCards(a la Main)
cas des caracteres generiques de
& nbsp & nbsp 0 : { pas etre interesse par ce }
& nbsp & nbsp 1 : begin { Une Wild Card }
& ! & ! & ! & ! & ! & ! & ! & nbsp { set de demarrage pour demarrer la couleur de la premiere carte }
& ! & ! & ! & ! & ! & ! & ! & nbsp StartCardPos := Ord(a la Main[1].Costume) * 13
& ! & ! & ! & ! & ! & ! & ! & nbsp EndCardPos := StartCardPos 12

& ! & ! & ! & ! & ! & ! & ! & nbsp pour wc5 := StartCardPos a EndCardPos ne
& ! & ! & ! & ! & ! & ! & ! & nbsp commencer
& ! & ! & ! & ! & ! & ! & ! & ! & ! & nbsp TempHand := la Main
& ! & ! & ! & ! & ! & ! & ! & ! & ! & nbsp TempHand[5].Rang := TcaaRank((wc5) mod 13)
& ! & ! & ! & ! & ! & ! & ! & ! & ! & nbsp TempHand[5].Costume := TcaaSuit((wc5) div 13)
Maintenant, au lieu de tester de cinquante-deux variantes pour chaque wild-card, je ne fais que des tests de treize ans. Cette modification doit etre faite pour les deux wild card et trois wild-card mains. (Les routines de quatre et cinq wild card mains, ne fonctionnent pas de la meme façon et n'ont pas besoin d'etre change.) La vitesse de divergence entre le joker et non sauvage de carte de carte de carte d'evaluations a ete reduit environ de moitie. A l'aide d'un Joker, la bibliotheque de l'evalue a 22 000 mains par seconde et plus de 12 000 mains par seconde avec deux jokers.
Optimisation des 5
Le cinquieme optimisation vient de la 'je prefere etre chanceux que bon' l'ecole de la programmation. J'ai ete heureux avec la vitesse a ce point, j'ai donc decide de tester la bibliotheque dans les autres versions de Delphi. J'ai commence avec Delphi 1. Depuis la chaîne de type Delphi 1 est fixe et le defaut de declaration est equivalent a une declaration de la chaîne[255], j'ai cree deux nouveaux types de chaînes. L'un aurait le nom de la carte. L'autre tenait la main de nom.
Mon experience avec des chaînes courtes a ete qu'ils sont extremement rapides. Inprise aimerait sans doute la phase la courte chaîne. Plusieurs types de chaînes de compliquer la mise en œuvre de la langue. Neanmoins, j'ai souvent utiliser dans mon code et je ne voyais aucune raison de ne pas les utiliser dans toutes les versions de la bibliotheque. Cela permettrait de garder les choses simples. Mais, j'ai voulu tester. Il s'est avere pour etre le plus 'optimisation' j'ai pu faire. (Aussi deroutante! Un probleme avec un code d'emplacement de memoire?)

Code Source
code Source de la nature de la carte de bibliotheque, un compagnon de video poker bibliotheque, un exemple de jeu de video poker et tous les utilitaires decrits dans l'article peut etre telecharge a partir de http://charlesappel.home.mindspring.com/.