PHP array performance

Question

Estoy probando un algoritmo para bin 2d y he elegido PHP para simularlo, ya que es mi lenguaje pan y mantequilla en la actualidad.

Como puedes ver en http://themworks.com/pack_v0.2/oopack.php?ol=1 funciona bastante bien, pero necesitas esperar alrededor de 10-20 segundos para empacar 100 rectángulos. Para algunos conjuntos difíciles de manejar, alcanzaría el límite de tiempo de ejecución de 30 php.

Hice algunos perfiles y muestra que la mayoría de las veces mi script pasa por diferentes partes de una pequeña matriz 2d con 0 y 1 en ella. Comprueba si cierta celda es igual a 0/1 o la establece en 0/1. Puede hacer tales operaciones millones de veces y cada vez lleva pocos microsegundos.

Supongo que podría usar una matriz de booleanos en un lenguaje estáticamente tipado y las cosas serían más rápidas. O incluso hacer una matriz de valores de 1 bit. Estoy pensando en convertir todo en un lenguaje compilado. ¿PHP no es bueno para eso?

Si necesito convertirlo, digamos C++, ¿qué tan buenos son los convertidores automáticos? Mi script es solo un montón de bucles con matrices básicas y manipulaciones de objetos.

Editar. Esta función se llama más que cualquier otra. Se lee algunas propiedades de un objeto muy simple, y pasa a través de una muy pequeña parte de una matriz más bien pequeña para comprobar si hay algún elemento no es igual a 0.

function fits($bin, $w, $h, $x, $y) { 

    $w += $x; 
    $h += $y; 

    for ($i = $x; $i < $w; $i++) { 

     for ($j = $y; $j < $h; $j++) { 

      if ($bin[$i][$j] !== 0) { 
       return false; 
      } 
     } 
    } 

    return true;  
} 

Actualización: He intentado usar el conjunto en lugar de 1d 2d como una de las respuestas sugeridas. Como necesitaba tener siempre disponible el ancho actual de la papelera, decidí ajustar todo en el objeto. Además, ahora en cada bucle, el índice debe calcularse. Ahora el script tarda aún más tiempo en ejecutarse. Otras técnicas no aportaron mucho impulso al rendimiento, sino que hicieron que el código fuera menos legible. Es hora de HipHop, supongo.

Actualización: ya que hiphop php solo se ejecuta en Linux, y no tengo uno, he decidido volver a escribir todo en C++. Es bueno refrescar las viejas habilidades. Además, si encuentro una forma de usar hiphop, será interesante comparar el código de C++ escrito a mano y el que hiphop generaría.

Actualización: reescribí esta cosa en C++, en promedio funciona 20 veces más rápido y usa mucha menos memoria. Déjame ver si puedo hacerlo aún más rápido.

Answer 1

El acceso de matriz en PHP puede ser lento. PHP utiliza tablas hash para implementar matrices, es decir, para acceder a un elemento en una matriz, debe calcular un hash y atravesar una lista vinculada. El uso de un lenguaje compilado con matrices reales definitivamente mejorará el rendimiento, ya que se realiza un acceso directo a la memoria. Para el interesado: Código para hash access with string y with integer.

cuanto a su código, hay varios puntos que optimizaría:

• return directamente, no hace break dos veces.
• poner $file->get_width() y $file->get_height en variables simples. Supongo que la altura o el ancho no cambia a lo largo del proceso. Recuerde: las funciones en PHP son lentas.
• Utilice una matriz unidimensional, en lugar de matrices anidadas. Guarda una búsqueda de hash por iteración de esa manera. En realidad, una matriz unidimensional es solo marginalmente más rápida o incluso ligeramente más lenta. Comparison of several ways of saving the data concerning performance and memory usage.

.

function fits($bin, $x, $y, $w, $h) { 
    $w += $x; 
    $h += $y; 

    for ($i = $x; $i < $w; ++$i) { 
     for ($j = $y; $j < $h; ++$j) { 
      if ($bin[$i][$j] !== 0) { 
       return false; 
      } 
     } 
    } 

    return true; 
} 

Aunque no estoy seguro, ¿por qué se agrega a la $x$width/$y a la $height. ¿No quieres iterar desde las coordenadas actuales hasta los límites de la imagen?

Answer 2

La solución a su problema podría ser https://github.com/facebook/hiphop-php/wiki/

Según lo dicho por todos los demás, PHP no es el idioma óptima para las tareas intensivas de cálculo. Tampoco tiene realmente un tipo de matriz. Lo que se describe como array() en PHP es realmente un mapa de diccionario/hash. Tiene algunas optimizaciones para duplicar como lista, pero como ya has descubierto, no proporciona el mismo comportamiento en tiempo de ejecución que los punteros C y las matrices.

HipHop puede transformar el código PHP en C++ optimizado. También se dirigió a la manipulación de cadenas, pero podría ofrecer una transformación adecuada de matriz/lista.

Descargo de responsabilidad: Nunca lo he intentado. Solo quería contribuir con una respuesta de sonido inteligente aquí.

Answer 3

sugerir otra alternativa de PHP:

¿Ha mirado en SplFixedArray?

Dependiendo de cómo se estructuran las matrices (lineal a 0 x) matrices esto se puede llevar a cabo un poco más rápido

Para una sede de referencia: http://www.slideshare.net/tobias382/new-spl-features-in-php-53 Slide 15 & 16 (lo siento, no encontró uno mejor)

Answer 4

La pregunta es casi calificable como "principalmente basada en la opinión". Con eso en mente:

"¿PHP no es bueno para eso?"

PHP era originalmente solo un lenguaje de plantillas web, y la simplicidad era una preocupación mayor que el rendimiento cuando se diseñó. Ha evolucionado con el tiempo y se han agregado muchas optimizaciones, pero aún así, el rendimiento de PHP es relativamente pobre para las otras plataformas. Entonces, si su criterio es el rendimiento, PHP no es bueno para eso.

"Estoy pensando en convertir todo a un lenguaje compilado".

Técnicamente, también se puede compilar PHP. Existe un compilador PHP a C++ por Facebook. Hay un compilador de compilación justo a tiempo por Zend. Solía ​​haber un intérprete de PHP en Java (aunque ya no está activo si no recuerdo mal).

Te recomiendo que pruebes Java ya que su sintaxis es similar, después de todo, fue una de las inspiraciones de PHP 5. Java bytecode se compila en código nativo desde JDK 1.5. El rendimiento debería surgir cca 4x para la misma estructura de código (suponiendo que utilice la distribución PHP de la comunidad).

Answer 5

Una alternativa más reciente es la extensión de QB a PHP que está específicamente diseñada para ayudar con este tipo de problema.

Mientras que PHP es un lenguaje excelente para la construcción de aplicaciones web complejas , impone ciertas limitaciones. Escribir código que realiza tareas de bajo nivel, intensivas en computación en PHP es generalmente poco práctico - simplemente sería demasiado lento. La extensión QB aborda esta debilidad particular de PHP. Al traducir los códigos de operación Zend y ejecutarlos a través de una máquina virtual tipada estáticamente, QB ofrece una ganancia de orden de magnitud en el rendimiento. La potencia agregada permite a los programadores de PHP hacer cosas que antes no podían hacer, como la manipulación de imágenes a nivel de píxel .

Ver: http://php-qb.net/

Answer 6

matrices en PHP de hecho parecen ser bastante lento, especialmente bucle a través de matrices multidimensionales. Otra opción sería intentar Quercus. Es una implementación de PHP en Java. Supongo que usa matrices de Java. No he hecho una comparación sin embargo.

Answer 7

RESPUESTA DE ACTUALIZACIÓN necesite Según 2018.

Esta pregunta es antiguo y las respuestas dadas no son del todo cierto en PHP 7 si se utiliza matrices para llevar. Debido a que la pregunta aparece primer hit en google, agrego una nueva respuesta

Si usa enteros solo como claves de matriz en PHP 7 y se asegura de que los inserte en la matriz en orden ascendente, puede ver las mejoras de 10x operaciones de matriz más rápidas.

leer aquí: Blackfire Blog on PHP 7 Array Improvements