La optimización de object pascal

La optimizacion de object pascal

La optimizacion de object pascal : Multi-millones de consejos para hacer su vida mas facil.

Una historia de optimizacion.

Optimizacion de Object Pascal
en Este articulo se examina la optimizacion de codigo de Delphi basado en el estandar de las tecnicas, la plena comprension de la materia objeto del programa y un caso de pura chiripa. Una biblioteca de poquer se utiliza para ilustrar estos puntos.
Esta es una historia acerca de una simple biblioteca de poquer y optimizar el codigo en Delphi. La biblioteca de poquer que comenzo como un Turbo Pascal proyecto de hace años, que yo habia tenido la intencion de convertir a Delphi durante algun tiempo. Como sucedio, Delphi 5 golpear los estantes antes de encontrar el tiempo para hacer la conversion.
Mi primer paso fue el rediseño de la biblioteca como un objeto-orientado proyecto. El codigo original habia sido puramente de procedimiento. En su nuevo formato, la biblioteca ofrece tres clases de programacion de juegos de poker. Estos son, curiosamente - una tarjeta de clase, un mazo de clase y de la mano de la clase. La cubierta y de la mano son descendientes de una tarjeta de la lista de clase. La biblioteca es compatible con los juegos de poker, que el uso de las manos de cinco o mas cartas, tiene soporte para altas y bajas y variaciones de la admite comodines. Fue esta ultima caracteristica que resulto ser la mas dificil. Termine la construccion de una biblioteca completa con ningun comodin de apoyo y se utiliza como la base para el wild card de la version.
Para validar la biblioteca, he construido una serie de nueve aplicaciones de prueba. Estos incluyen programas para la prueba de la creacion y de barajar un mazo de cartas, que me permita elegir cinco tarjetas y evaluar como una mano de poker, un programa que recibe y evalua manos de cinco cartas de todo tipo estandar, un programa que hizo la misma para las siete de la tarjeta de las manos, un juego de poquer de video, y cuatro puntos de referencia para probar la velocidad de la biblioteca con naipes salvajes y sin.
Se tomo un par de semanas para construir la biblioteca y el proceso se desarrollo sin contratiempos. Yo era capaz de utilizar una buena parte del antiguo codigo Pascal. Esto resulto ser tanto bueno como malo. Bueno, porque acelero la conversion a lo largo. Malo, porque he cometido un pequeño error, que explicare mas adelante. En un par de semanas el proyecto fue probada y completa, excepto por un pequeño problema. Era demasiado lento para ser de cualquier uso. Asi comienza nuestra aventura. Los resultados de la primera velocidad de los ensayos se muestran en la Tabla 1.

Tabla 1. Wild Card de la Biblioteca de puntos de referencia - son Tiempos en segundos
Delphi 5 en un 400Mhz Pentium II con 128 megabytes de RAM
El punto de referencia de los programas son muy simples. Cada programa crea todas las posibles manos de cinco cartas de una baraja de cartas. A continuacion, llama a la SetHighValues metodo de la mano de objeto, que evalua la mano y devuelve una calificacion alta y un alto nombre. La alta calificacion es un entero largo usado como un campo de bits. El bajo para veinte bits contiene el ranking de las cartas en poker estandar de la orden. El alto fin de once bits contiene el tipo de mano. (Para una explicacion mas detallada, ver el codigo fuente de la biblioteca, que esta disponible para su descarga). Esto permite que un programa de poker para comparar los valores de dos manos mediante la comparacion de sus altas calificaciones. Por ejemplo:
& nbsp & nbsp si a la Mano[1].HiRating > Mano[2].HiRating, a continuacion,
El punto de referencia se utiliza el programa de la alta calificacion para determinar el tipo de mano y mantiene un recuento de todos los tipos estandar y el numero total de manos. Esto sirve como una validacion adicional de las rutinas de biblioteca. En una de 52 tarjetas estandar de la cubierta, hay 2,598,960 posible de cinco cartas de las manos, cuatro escaleras reales, 5,108 estandar vacia etc. Si los informes comparativos de diferentes numeros, sabemos que hay un problema con la evaluacion de las rutinas.
Como se puede ver, cada comodin utilizado conduce a aproximadamente un 80% de caida en la velocidad. No me molesta que ejecuta el deuces wild de referencia. Los dos comodines de referencia tomo aproximadamente una hora y cuarto para completar. El deuces wild de referencia habria tomado un estimado de veinte-cinco horas para completar.
lo que es mas Rapido
El primer paso es encontrar cual es el problema de las areas. Los puntos de referencia mismos apuntan a una area que necesita trabajo. El metodo utilizado para la tasa de wild card manos equivale a la conversion de la tarjeta salvaje en todos los posibles reemplazos de tarjetas y, a continuacion, llamar a la evaluacion real de las rutinas. Es claro que este podria utilizar un poco de trabajo.
Para encontrar otras areas de mejora, saque mi fiel del analizador de codigo. Yo la utilizacion del Cronometro, parte de Sleuth QA de TurboPower. Hay otros disponibles y cada programador debe tener uno. Me encontre con la ningunos naipes salvajes de referencia bajo el analizador y espero a que el informe. En realidad, me fui a la cama. Dado que la biblioteca es un poquito lento, me encontre con el perfil de la noche. A la mañana siguiente, 273 millones de llamadas de funcion mas tarde, se vieron los resultados. Ver Tabla 2.

Tabla 2. Diez la mayoria de los llamados rutinas en la biblioteca de poquer.
Cronometro devuelve una gran cantidad de informacion. Hay tiempos en cada rutina de llamada y el porcentaje del total de esta cantidad. En este caso, algunos de los mas importantes es la informacion en la tabla de arriba.
La primera cosa de la nota, es que hay casi 195 millones de llamadas a la GetCard metodo. Este es el esperado. Cada mano evaluado por el SetHighValues metodo genera 25 llamadas a GetCard. Cada llamada a CopyCardFromDeck genera mas de diez. El total es correcto. Asi es el total de CopyCardFromDeck. Ademas, un rapido vistazo a los listados indica que no hay mucho que se puede cambiar en cualquiera de estas rutinas. Ellos son, basicamente, las sentencias de asignacion.
Es el momento de pensar como un jugador de poquer en lugar de un programador. Hay 2,598,960 posible de cinco cartas en una baraja de cartas. Cuarenta de ellos son de escalera de color y cuatro de la escalera de color son las escaleras reales. Hay 5,108 rectas y 10.200 vuelca en una baraja estandar. El numero de llamadas a IsStraight, IsFlush y especialmente a IsStraightFlush estan fuera de linea. Cada mano esta siendo probado tres veces para ver si es una recta. (en Realidad 2.996336996336996336996336996337 veces, pero ¿por que discutir?)
SetHiValNoWC es el caballo de batalla de la biblioteca de poquer para la evaluacion de las manos altas. Las pruebas de cada mano pasa y descubre de que tipo es. Entonces formatos de la mano, le da una calificacion numerica y un nombre apropiado. Para ello se llama a la IsStraight funcion, y varios otros. Esto se hace en una bonita manera segura, con las comparaciones ordenada de mayor a menor. Ahi es donde uno de nuestros problemas.
Cada mano es una prueba para ver si es de cinco de una especie. Si es asi, hemos terminado. Si no se prueba a ver si es una escalera real. Esta es una prueba para ver si es una escalera, una escalera, una escalera de color y, finalmente, un real. Si es una escalera real, comprueba para ver si es real natural o si se utiliza comodines. De cualquier manera, hemos terminado. Si no es real, es una prueba para ver si es una escalera de color, asi que la prueba de la escalera se repite. Ver el problema? Este es un mal algoritmo.
Optimizacion de 1
Nuestra primera mejora es cambiar el orden de las pruebas. Esta vez, en lugar de hacerlo de una manera segura, voy a tratar de hacerlo de la manera inteligente. Probablemente hay muchas soluciones. ¿De cuantas maneras distintas puede diez pruebas se organizan? Ouch! De nuevo, es el momento de poner en mi poker sombrero.
las manos de Poker puede dividirse en dos tipos distintos. El primer tipo contiene dos o mas cartas del mismo rango. Todos los pares, dos pares de manos, viajes, casas completas, cuatro de una clase, y a cinco de una especie manos entran en esta categoria. En la segunda categoria estan todas las manos sin cartas del mismo rango. Estos incluyen escaleras reales, escalera de color, escaleras, colores y alta de la tarjeta de las manos. (Un alto mano de la tarjeta se define como cinco cartas no relacionadas.)
Este divide el problema en dos problemas mas pequeños. En cada caso, queremos poner a prueba una mano en contra de un determinado tipo de una sola vez y que prefiere para la prueba de las mas raras de las manos despues de la mas comun. Pseudo-codigo para una solucion parcial es en el listado 1.
Listado 1. Pseudo-codigo para la nueva mano de la orden de pruebas.
{prueba del primer grupo - manos con cartas del mismo rango }
si isOnePair, a continuacion,
& nbsp & nbsp si isThreeOfAKind, a continuacion,
& nbsp & nbsp & nbsp & nbsp si isFourOfAKind, a continuacion,
& nbsp & nbsp & nbsp & nbsp & nbsp & nbsp si IsFiveOfAKind, a continuacion,
& nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp hacer cinco de un tipo de procesamiento
& nbsp & nbsp & nbsp & nbsp & nbsp & nbsp else { no cinco, pero cuatro de una clase }
& nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp hacer cuatro de un tipo de procesamiento
& nbsp & nbsp & nbsp & nbsp & nbsp & nbsp final
& nbsp & nbsp & nbsp & nbsp final
& nbsp & nbsp else
& nbsp & nbsp si isFullHouse, a continuacion,
& nbsp & nbsp & nbsp & nbsp hacer pleno de la camara de procesamiento
& nbsp & nbsp else { no, solo los viajes }
& nbsp & nbsp & nbsp & nbsp hacer tres de un tipo de procesamiento
& nbsp & nbsp end { si isThreeOfAKind }
{ no viajes, como sobre dos pares }
else
& nbsp & nbsp si isTwoPairs, a continuacion,
& nbsp & nbsp & nbsp & nbsp hacer dos pares de procesamiento
end { si isTwoPairs }
else
& nbsp & nbsp hacer un par de procesamiento
end { si isOnePair }
Esto parece que deberia funcionar mejor, pero tiene el problema de ser mucho mas complicado de trabajar. Despues de la aplicacion de este, lo he comprobado y se han corregido los bugs que se han introducido. El no uso de comodines, la biblioteca, que ahora podria tasa de 25,800 manos por segundo. Esa es una buena mejora. Sin embargo, aun no es lo suficientemente bueno. La evaluacion comparativa de dos comodines aun tardaria cerca de una hora - diez horas para cuatro.
Optimizacion 2
volviendo al perfil, veo que SwapCards se llama un monton. Asi que debe comprobar fuera de su codigo y encontrar los lugares de los cuales es que se llama. El codigo es sencillo. No hay ninguna forma corta de lenguaje ensamblador para hacerlo mas rapido. Sin embargo, la rutina de seleccion esta llamando SwapCards en lugar de hacer su propio intercambio. La rutina de ordenacion se enumeran a continuacion:
procedimiento SortCardsLowToHigh(var Mano: TcaaEvaluationHand)
var
& nbsp & nbsp leftCardPos, rightCardPos : integer
begin
& nbsp & nbsp para leftCardPos := 2 a 5 años
& nbsp & nbsp & nbsp & nbsp para rightCardPos := 5 downto leftCardPos hacer
& nbsp & nbsp & nbsp & nbsp & nbsp & nbsp si a la Mano[rightCardPos-1].Rango >
& nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp Mano[rightCardPos].Rango, a continuacion,
& nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp SwapCards(Mano,rightCardPos-1,rightCardPos)
fin
cambios en el codigo para hacer su propio intercambio va a guardar una llamada a una funcion, cada vez que un intercambio. El tipo de rutina es llamada mas de cuatro millones de veces. Que debe darnos un poco mas de velocidad. Tambien puede ser posible mejorar la especie en si. Pase un poco de tiempo tratando de otros algoritmos, pero la teoria mas rapido no arrojo ningun tipo de mejoras y, en muchos casos, desacelero la cosa. La razon de esto es la longitud de la matriz combinada con la sobrecarga de muchos de los otros los metodos de seleccion.
Optimizacion 3 - la Fijacion de un Error
Es el momento de mirar en la IsFlush funcion y todos sus hermanos. El codigo se muestra a continuacion:
funcion IsFlush(de la Mano: TcaaEvaluationHand): Boolean
begin
& nbsp & nbsp Resultado := False
& nbsp & nbsp si (Mano[1].Traje = Mano[2].Traje) y de la Mano ([1].Traje = Mano[3].Traje de
& nbsp & nbsp & nbsp & nbsp y de la Mano ([1].Traje = Mano[4].Traje)
& nbsp & nbsp & nbsp & nbsp y de la Mano ([1].Traje = Mano[5].Traje) then Resultado := True
fin
no hay mucho que hacer aqui. O es que hay? La Mano parametro es un array de registros y es que se pasa como un parametro estandar - lo que significa que en la pila. Oops. Error absurdo. Este es el codigo que he copiado la forma original de Pascal de la biblioteca. Los unicos cambios que hice fueron asignando a la variable de Resultado en lugar del nombre de la funcion. Hice algo que no era necesario en lugar de algo que podria haber ayudado. Haciendo de la Mano de un parametro const mejoraran la velocidad considerablemente.
luego fui por el resto del codigo para encontrar cualquier matrices, registros o cadenas que se pasan a las funciones como parametros estandar. Si, he encontrado un monton de ellos. Con esta fija, la biblioteca puede evaluar 38,900 manos por segundo y con ningunos naipes salvajes. El uso de un comodin (joker le da un respetable 9,800 manos por segundo.
Optimizacion 4
lo siguiente mirado lo que los resultados de referencia se señala. Recuerda que cada comodin es la adicion de aproximadamente un 80% de la velocidad de la pena. Las razones para esto se explico anteriormente. Espere a solucionarlo, porque yo no habia descubierto que hacer. Echemos un vistazo a una pequeña parte del codigo.
Comodines := NumWildCards(Mano)
en el caso de los Comodines de la
& nbsp & nbsp 0 : { no interesado en este }
& nbsp & nbsp 1 : begin { Una Wild Card }
& nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp para wc5 := caaClubAce a caaSpadeKing hacer
& nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp empezar
& nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp TempHand := a Mano
& nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp TempHand[5].Rango := TcaaRank((wc5) mod 13)
& nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp TempHand[5].Traje := TcaaSuit((wc5) div 13)
¿de verdad tengo que probar todas las cincuenta y dos cartas posibles? Es sin duda lo mas seguro, como un primer intento. Funciona. Pero seguro que es lento. Tiempo para poner en mi poker sombrero de nuevo. Todos los trece rangos deben ser probados. ¿Tengo que probar todos los cuatro palos? No, No lo creo. He aqui por que. El unico significado que el traje tiene es en la determinacion de si la mano es una forma de rubor. La unica manera de que un traje puede hacer una diferencia es que si coincide con el traje de las otras tarjetas. Solo puedo comprobar uno de los (no natural) de las tarjetas y el uso solo de dicha demanda. Aqui es lo que el nuevo codigo como se muestra.
Comodines := NumWildCards(Mano)
en el caso de los Comodines de la
& nbsp & nbsp 0 : { no interesado en este }
& nbsp & nbsp 1 : begin { Una Wild Card }
& nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp { set de inicio para iniciar el palo en la primera carta }
& nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp StartCardPos := Ord(a Mano[1].Traje) * 13
& nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp EndCardPos := StartCardPos 12

& nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp para wc5 := StartCardPos a EndCardPos hacer
& nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp empezar
& nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp TempHand := a Mano
& nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp TempHand[5].Rango := TcaaRank((wc5) mod 13)
& nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp TempHand[5].Traje := TcaaSuit((wc5) div 13)
Ahora, en lugar de pruebas de cincuenta y dos variantes para cada uno de los wild card estoy probando solo trece años. Esta misma modificacion debe hacerse por dos wild card y tres wild card manos asi. (Las rutinas de cuatro y cinco salvaje de la tarjeta de las manos, no funcionan de la misma manera y no necesita ser cambiado.) La velocidad de la discrepancia entre la naturaleza de la tarjeta y no salvaje de la tarjeta tarjeta tarjeta de evaluaciones ha sido reducido aproximadamente a la mitad. El uso de un Comodin, ahora, la biblioteca evalua 22,000 manos por segundo y 12.000 manos por segundo con dos comodines.
Optimizacion 5
El quinto optimizacion proviene de la 'prefiero tener suerte que ser bueno' de la escuela de la programacion. Yo estaba feliz con la velocidad en este punto, asi que me decidi a probar la biblioteca en otras versiones de Delphi. Empece con Delphi 1. Desde el tipo de cadena en Delphi 1 es fijo y la declaracion predeterminada es equivalente a una declaracion de cadena[255], he creado dos nuevos tipos de cadena. Que uno tenga el nombre de la tarjeta. El otro se mantenga el nombre de la mano.
Mi experiencia con cadenas cortas ha sido que ellos son muy rapidos. Inprise probablemente como las etapas de la cadena corta. Varios tipos de cadena complicar la implementacion de la lengua. No obstante, a menudo el uso de ellos en mi codigo y no vi ninguna razon para no usarlos en todas las versiones de la biblioteca. Este seria mantener las cosas simples. Pero, yo queria probar con ellos. Resulto para ser el mas grande 'optimizacion' yo podria hacer. (Tambien desconcertante! Un problema con el codigo de ubicacion en la memoria?)

Codigo Fuente
codigo Fuente para el wild card de la biblioteca, un compañero de poker de video de la biblioteca, un ejemplo de juego de video poker y todas las utilidades descritas en el articulo puede ser descargado desde http://charlesappel.home.mindspring.com/.