En historie om optimization.This artikkelen opprinnelig dukket opp i Delphi DeveloperCopyright Pinnacle Publishing, Inc. Alle rettigheter reservert.
Optimalisere Object Pascal Denne artikkelen undersøker optimalisere Delphi kode basert på standard teknikker, helt å forstå innholdet i programmet og et tilfelle av ren flaks. En poker biblioteket brukes til å illustrere disse punktene.
Dette er en historie om en enkel poker bibliotek og optimalisere koden i Delphi. Poker bibliotek begynte som en Turbo Pascal prosjekt år siden, en som jeg hadde vært meningen å konvertere til Delphi i noen tid. Som det skjedde, Delphi 5 treffer hyllene før jeg fant tid til å gjøre det conversion.My første skritt var å redesigne biblioteket som et objekt-orientert prosjekt. Den opprinnelige koden hadde blitt rent prosessuelle. I sin nye formatet, gir biblioteket tre klasser for programmering pokerspill. Disse er, merkelig nok - et kort klasse, en kortstokk klasse og en hånd klasse. Dekket og hånden er etterkommere av en kort liste klasse. Biblioteket støtter pokerspill, som bruker hendene på fem eller flere kort, har støtte for høy og lav variasjoner og støtter jokere. Det var denne siste funksjonen som viste den vanskeligste. Jeg endte opp med å bygge et komplett bibliotek med noen wild card support og brukt dette som grunnlag for wild card version.To validere biblioteket, jeg bygget en serie på ni testapplikasjoner. Disse inkluderte programmer for å teste etablering og stokking av en kortstokk, for å tillate meg å plukke fem kort og vurdere dem som en pokerhånd, et program som deles ut og evaluert fem-korts hånd til alle standard type, et program som gjorde det samme for syv korts hender, en video pokerspill, og fire milepæler for å teste hastigheten på biblioteket med wild cards og without.It tok et par uker å bygge biblioteket og prosessen gikk greit. Jeg var i stand til å bruke en god del av den gamle Pascal kode. Dette viste seg å være både gode og dårlige. Bra, fordi det føk konverteringen sammen. Bad, fordi jeg gjorde en liten feil som jeg vil forklare senere. I et par uker til prosjektet ble testet og komplett med unntak av ett lite problem. Det var for treg til å være til nytte. Dermed begynner våre eventyr. Resultatene av de første farts forsøkene er oppført i Tabell 1.
Benchmark
Hands per sekund
Total tid

Ingen Wild Cards

16490
157,6
En Joker

3453
830,9
To jokere
703
4,496.7
Deuces Wild
N /A
N /A

Tabell 1. Wild Card Library Benchmarks - Tidene er i secondsDelphi 5 på en 400Mhz Pentium II med 128 megabyte RAM
referanse~~POS=TRUNC programmer er svært enkel. Hvert program skaper alle mulige fem-korts hender i en kortstokk. Den vil deretter anrope SetHighValues ​​fremgangsmåte for hånden gjenstand, som evaluerer hånd og returnerer en høy vurdering og en høy navn. Høy rangering er en lang heltall brukt som en bit felt. De lave for tjue biter inneholde rekkene av kortene i standard poker rekkefølge. Den høye ordre elleve biter inneholde hånden type. (For en mer detaljert forklaring, se biblioteket kilden, som er tilgjengelig for nedlasting.) Dette gjør at en pokerprogram for å sammenligne verdiene av to hender ved å sammenligne sine høye seertall. For eksempel: hvis Hånd [1] .HiRating > Hånd [2] .HiRating thenthe benchmark program bruker høy vurdering for å avgjøre hvilken type hånd og holder en telling på alle tradisjonelle typer, og det totale antall hender. Dette fungerer som ytterligere validering av bibliotekets rutiner. I en 52-kort standard dekk, er det 2,598,960 mulige fem-korts hånd, fire royal flush, 5,108 standard flush etc. Dersom referanse rapporterer forskjellige tall så vet vi at det er et problem med evaluerings routines.As du kan se, hver wild card brukes fører til omtrent en 80% nedgang i hastighet. Jeg gjorde ikke bry kjører Deuces Wild benchmark. De to jokere referanse tok omtrent en time og et kvarter å fullføre. Deuces Wild referanse ville ha tatt anslagsvis fem og tyve timer å complete.Making det FasterThe første trinnet er å finne hva de problemområder er. Benchmarks selv peke på ett område som trenger arbeid. Metoden som brukes for å rangere joker hender utgjør konvertere wild card inn i alle mulige erstatningskort og deretter ringe selve evalueringsrutiner. Det er klart at dette kunne bruke noen work.To finne andre områder for forbedring, jeg fikk ut min trofaste kode profiler. Jeg bruker stoppeklokke, en del av Sleuth QA fra TurboPower. Det finnes andre tilgjengelige og hver programmerer bør ha en. Jeg kjørte noen jokere referanse under profiler og ventet på rapporten. Egentlig gikk jeg til sengs. Siden biblioteket er en tiss litt treg, jeg kjørte profil på natten. Neste morgen, kaller 273 millioner funksjon senere, var resultatene i. Se tabell 2.
Antall Calls


Procedure/Function




194,922,000TcaaPCardList.GetCard



14,593,208SwapCards



12,994,800TcaaPokerHand.CopyCardFromDeck



7,787,360IsStraight



5,197,916IsStraightFlush



4,203,056SortCardsLowToHigh



3,917,000RankString



2,615,028IsFlush



2,598,960TcaaPokerHand.SetHighValues



2,598,960SetHiValNoWC




Table 2. Ti mest kalt rutiner i poker biblioteket.
Stoppeklokke returnerer mye informasjon. Det er timings på hver rutine kalt og andelen av den totale dette utgjør. I dette tilfellet, noen av de viktigste informasjonen er i tabellen above.The første av notatet, er at det er nesten 195 millioner samtaler til GetCard metoden. Dette er forventet. Hver hånd evaluert av SetHighValues ​​metoden genererer 25 samtaler til GetCard. Hver samtale til CopyCardFromDeck genererer ti mer. Den totale er riktig. Så er totalen for CopyCardFromDeck. Videre et raskt blikk på oppføringene indikerer at det er ikke mye som kan endres i noen av disse rutinene. De er i hovedsak bare oppdrag statements.It tid til å tenke som en pokerspiller i stedet for en programmerer. Det er 2,598,960 mulige fem-korts hender i en standard kortstokk. Førti av disse er straight flush og fire av de straight flush er royal flush. Det er 5,108 straight og 10.200 flush i en standard kortstokk. Tallene for samtaler til IsStraight, IsFlush og spesielt til IsStraightFlush er langt over streken. Hver hånd blir testet tre ganger for å se om det er en rett. (faktisk 2.996336996336996336996336996337 ganger, men hvorfor krangle?)
SetHiValNoWC er arbeidshesten av poker biblioteket for å evaluere høye hender. Den tester hver hånd gikk til det og finner hvilken type det er. Deretter formaterer den hånden, det gir en numerisk rating og et passende navn. For å gjøre dette kaller det IsStraight funksjon, og flere andre. Det gjør dette på en fin trygg måte, med sammenligninger bestilt fra høyeste til laveste. Det er der en av våre problemer lies.Each hånd er testet for å se om er fem av et slag. Hvis det er, er vi ferdig. Hvis ikke det er testet for å se om det er en royal flush. Dette betyr testing for å se om det er en rett, en flush, straight flush og til slutt en kongelig. Hvis det er en royal flush, sjekker den for å se om det er en naturlig kongelig eller hvis det bruker wild cards. Uansett, vi er ferdig. Hvis det ikke er en kongelig, er det da testet for å se om det er en straight flush, så test for straight gjentas. Se problemet? Dette er en dårlig algorithm.Optimization 1Our første forbedring er å endre rekkefølgen på testene. Denne gangen, i stedet for å gjøre det på trygg måte, vil jeg prøve å gjøre det på den smarte måten. Det er sannsynlig å være mange løsninger. Hvor mange måter kan ti tester ordnes? Au! Igjen er det på tide å sette på min poker hat.Poker hender kan deles inn i to forskjellige typer. Den første typen inneholder to eller flere kort av samme rang. Alle parene, to par hender, turer, fullt hus, fire like og fem av et slag hender faller inn under denne kategorien. I den andre kategorien er alle hender med ingen kort av matchende rang. Disse inkluderer royal flush, straight flush, straight, flush og høyt kort hender. (En høy korts hånd er definert som fem urelaterte kort.) Dette deler problemet i to mindre problemer. I hvert fall ønsker vi å teste en hånd mot en bestemt type bare én gang, og vi ønsker å teste for de sjeldnere hendene etter mer vanlig. Psuedo-kode for en delvis løsning er i oppføring 1. Oppføring 1. Pseudo-kode for ny hånd testing for
. {Test første gruppen - hender med kort av samme rang} hvis isOnePair så hvis isThreeOfAKind så hvis isFourOfAKind så hvis IsFiveOfAKind deretter gjøre fem like behandling else {ikke fem, men fire like} gjøre fire like behandling end end else if isFullHouse så gjør fullt hus behandling else {nei, bare turer} gjøre tre like behandling end {if isThreeOfAKind} {ingen turer, hvor om lag to parene} else if isTwoPairs deretter gjøre to par processingend {if isTwoPairs} else gjøre ett par processingend {if isOnePair} Dette ser ut som det skal være bedre, men det har problemet med å være en mye vanskeligere å jobbe med. Etter gjennomføring av denne, jeg testet den og fikset de nye feilene som ble introdusert. Bruke ingen jokere, kan biblioteket nå vurderer 25,800 hender per sekund. Det er en god forbedring. Men det er fortsatt ikke godt nok. Benchmarking for to jokere fortsatt vil ta nesten en time - ti timer for four.Optimization 2Going tilbake til profilen, ser jeg at SwapCards blir kalt mye. Så vi bør sjekke ut sin kode og finne de stedene som det blir kalt. Koden er vanlig vanilje. Det er ingen måte kort av assembly for å gjøre det raskere. Imidlertid er sortering rutine å kalle SwapCards stedet for å gjøre sin egen swapping. Den slags rutine er listet opp nedenfor: prosedyre SortCardsLowToHigh (var Hånd: TcaaEvaluationHand); Var leftCardPos, rightCardPos: integer; begynne for leftCardPos: = 2-5 gjøre for rightCardPos: = 5 nedfor leftCardPos gjøre hvis Hånd [rightCardPos-1] .Rank > Hånd [rightCardPos] .Rank deretter SwapCards (Hånd, rightCardPos-en, rightCardPos), slutten, Endre koden for å gjøre sin egen swapping vil spare et funksjonskall, hver gang en swap er gjort. Den slags rutine er selv kalt over fire millioner ganger. Det burde gi oss litt mer fart. Det kan også være mulig å forbedre sorterings selv. Jeg brukte litt tid på å prøve andre algoritmer, men teoretisk raskere slags ga ingen forbedringer, og i mange tilfeller redusert ting ned. Grunnen til dette er lengden av matrisen, kombinert med den overliggende mange av de andre sorterings methods.Optimization 3 - feste en MistakeIt tid til å se på IsFlush funksjon og alle dens søsken. Koden er listet nedenfor: function IsFlush (Hånd: TcaaEvaluationHand): Boolean, begynner Resultat: = False; if (Hånd [1] .Suit = Hånd [2] .Suit) og (Hånd [1] .Suit = Hånd [3] .Suit og (Hånd [1] .Suit = Hånd [4] .Suit) og (Hånd .? [1] .Suit = Hånd [5] .Suit) så Resultat: = True; ende; ikke mye å gjøre her, eller er det The Hand parameteren er en rekke poster og det blir vedtatt som en standard parameter - som betyr på stakken. Oops. Dumb feil. Dette er koden jeg kopierte formen den opprinnelige Pascal bibliotek. de eneste endringene jeg har gjort var å tildele til Result variabel i stedet for funksjonsnavnet. jeg gjorde noe som ikke var nødvendig i stedet for noe som ville ha hjulpet. Making Hånd en const parameter vil forbedre hastigheten greatly.I deretter gikk gjennom resten av koden for å finne noen arrays, poster eller strenger som sendes til funksjoner som standard parametere. Ja, jeg fant en masse av dem. med denne fast, biblioteket kan vurdere 38,900 hender per sekund ved hjelp av ingen jokere. ved hjelp av en joker gir en respektabel 9800 hender per second.Optimization 4 jeg neste sett på hva benchmark resultater peker til. Husk at hvert wild card er å legge om en 80% hastighet straff. Årsakene til dette ble forklart tidligere. Jeg ventet med å fikse det fordi jeg ikke hadde funnet ut hva du skal gjøre. La oss se på en liten del av de code.WildCards: = NumWildCards (hånd), case jokertegn på 0: {ikke interessert i denne} 1: begin {One Wild Card} for wc5: = caaClubAce til caaSpadeKing gjør begynne TempHand: = Hånd; TempHand [5] .Rank: = TcaaRank ((wc5) mod 13); TempHand [5] .Suit: = TcaaSuit ((wc5) div 13); Må jeg virkelig trenger å teste alle femti-to mulige kort? Det er absolutt den sikreste tingen å gjøre, som et første forsøk. Det fungerer. Men at det er treg. Tid for å sette på min poker hatten igjen. Alle tretten gradene må testes. Må jeg til å teste alle fire dresser? Nei, jeg gjør ikke det. Her er grunnen. Den eneste betydning drakten har er å avgjøre om hånden er en form for flukt. Den eneste måten en dress kan gjøre en forskjell er om det samsvarer drakten av de andre kortene. Jeg kan bare sjekke en av de (ikke-wild) kort og bruke bare det passer. Her er hva den nye koden ser like.WildCards: = NumWildCards (hånd), case jokertegn fra 0: {ikke interessert i denne} 1: begin {One Wild Card} {sett begynne å starte på drakten i første kort} StartCardPos: = Ord (Hånd [1] .Suit) * 13; EndCardPos: = StartCardPos + 12; for wc5: = StartCardPos til EndCardPos ikke begynne TempHand: = hånd; TempHand [5] .Rank: = TcaaRank ((wc5) mod 13); TempHand [5] .Suit: = TcaaSuit ((wc5) div 13), nå i stedet for å teste femtito varianter for hvert wild card jeg bare teste tretten. Den samme endringen må gjøres for to wild card og tre wild card hender også. (Rutinene for fire og fem wild card hender, ikke fungerer på samme måte, og trenger ikke å endres.) Hastigheten avvik mellom wild card og ikke wild card-kort-kort evalueringer har blitt kuttet omtrent halvert. Ved hjelp av en Joker, biblioteket nå evaluerer 22.000 hender per sekund og 12.000 hender per sekund med to jokers.Optimization 5the femte optimalisering kommer fra "Jeg vil heller være heldig enn god" skole programmering. Jeg var fornøyd med hastigheten på dette punktet, så jeg bestemte meg for å teste biblioteket i andre versjoner av Delphi. Jeg startet med Delphi 1. Siden strengtype i Delphi en er fast og standard erklæring tilsvarer en erklæring om string [255], jeg opprettet to nye strengtypene. Man skulle holde kortet navn. Den andre ville holde hånden name.My erfaring med korte strenger har vært at de er ekstremt rask. Inprise vil nok gjerne å fase kort streng ut. Flere streng typer komplisere gjennomføringen av språket. Likevel, jeg bruker dem ofte i min kode, og jeg så ingen grunn til ikke å bruke dem i alle versjoner av biblioteket. Dette vil holde ting enkelt. Men, jeg ønsket å teste dem. Det viste seg å være den største "optimalisering" jeg kunne gjøre. Se tabell 3.
Compiler
Tid
(Lower = bedre)
bilder Hands /Second
(Høyere = bedre)
String Type

Delphi en
204,6 < .no> 12705
kort (hva ellers?)
Delphi to
22,2
117001
kort

Delphi to
32,3
80361
lang
Delphi 3

49.9
52112
kort
Delphi 3
70,1
37057

lang
Delphi 4
54,0
48111
kort
Delphi 4
78,5
33105
lang
Delphi 5
23,5
110759
shortM
Delphi 5
43,1
43094
lang


Tabell 3. Standard Poker Library Benchmark - Alle klokkeslett er på sekunder. Alle testene ble kjørt på en 400Mhz Pentium II med 128 megabyte RAM.
Testene ovenfor ble gjort mot den vanlige versjonen av poker biblioteket. Lignende hastighet forskjeller i begge. Korte strenger er raskere med hver versjon av Delphi. Den mest slående forskjellen er i Delphi 5. Er korte strenger alltid raskere? Jeg fortalte at Delphi 5 konverterer korte strenger til de nye dynamiske strenger før du utfører noen operasjoner. Dette bør gjøre korte strenger tregere i disse operasjonene. I dette tilfelle blir strenger bare brukes til å gi navn for kort og hender. Dette er til hjelp i feilsøking. Men de eneste manipulasjoner blir gjort er oppgaver og mangfoldige sammenhenger. Se tabell 4 for forbedringer ved hjelp av wild card biblioteket.
Benchmark
Hands per sekund
Total tid

Ingen Wild Cards

97161
26,7
En Joker
66424
43,2
To jokere Book 41719
75,8
Deuces Wild < .no> 14016
185,4

Tabell 4. Wild Card Library Benchmark - Tidene er i sekunder Delphi 5 på en 400Mhz Pentium II med 128 megabyte RAM
Hva blir det neste? Biblioteket kommer fort nok nå. 14,016 hender per sekund på den tregeste test bør absolutt være rask nok. Vi vet at det er raskt etter Delphi 5. La oss prøve det ut under alle versjoner og se hva som skjer. Tabell 5 inneholder resultatene.
Delphi en
Delphi to
Delphi 3

Delphi 4
Delphi 5

ingen jokere
12526
108920
44267
40274
97161
En Joker
10037
69963
36770
33808
66424
To jokere Book 7336 < .no> 43,095
27,846
25,995
41,719 i
Deuces Wild

2,976

13,590

11,766

11,440

14,016




Table 5. Wild Card Library Benchmark - Hands per sekund Delphi 5 på en 400Mhz Pentium II med 128 megabyte RAM, En Nye ProfileAs en siste sjekk, vil vi kjøre profiler igjen og se hva vi får. Se tabell 6.
Antall Calls


Procedure/Function




194,922,000

TcaaPCardList.GetCard



12,994,800

TcaaPokerHand.CopyCardFromDeck



4,203,056

SortCardsLowToHigh



3,917,000

RankString



2,598,960

MakeAcesLow



2,598,960

TcaaPokerHand.SetHighValues



2,598,960

SetHiValNoWC



1,876,344

SwapCards



1,125,312

MakeAcesHigh



1,098,240

SetCardOrderOnePair




Table 6. Ti mest kalt rutiner etter optimaliseringer
Dette har sikkert endret. Den gode nyheten er at ingen av de rutiner synes å bli kalt mer enn de burde. Jo bedre nyheten er at det er nok på tide å stoppe. Biblioteket er rask nok. Kan det være raskere? Ja visst. Det er flere ting som fortsatt kan gi litt ekstra fart. Men synes det ikke å være noe som vil få noen stor increase.From nå av blir små forbedringer være rekkefølgen av dagen. Jeg satt opp en ny mappe på harddisken min og kopiert det ferdige biblioteket der. Dette vil fungere som en eksperimentell versjon, der ideer kan testes uten å bryte arbeids kode. Her er noen av de tingene jeg prøvde med eksperimentell versjon som ikke har gjort det til produksjonskode.