PHP array performance

Question

I am testing an algorithm for packing 2d bin, and I have chosen PHP in order to mock it, as this is my language of bread and butter at present.

As you can see at http://themworks.com/pack_v0.2/oopack.php?ol=1 , it works very well, but you need to wait about 10-20 seconds for 100 rectangles of the pack. For some hard-to-handle sets, it would reach the php 30 runtime limit.

I did some profiling, and it shows that most of the time my script goes through different parts of a small 2d array with 0 and 1 in it. It either checks if the specific cell is 0/1, or sets the value to 0/1. It can perform such operations a million times and each time it takes several microseconds.

I think I could use an array of logical elements in a statically typed language, and everything will be faster. Or even make an array of 1 bit values. I am going to convert all this into a compiled language. PHP just not suitable for this?

If I need to convert it to say C ++, how good are automatic converters? My script is just a lot for loops with basic arrays and object manipulations.

Change This function is called more than any other. It reads several properties of a very simple object and goes through a very small part of a small array to check if there is any element other than 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; } 

Update: I tried using a 1d array instead of 2d as one of the suggested answers. Since I always need to have an available bin width, I decided to wrap everything in an object. In addition, now in each cycle, the index must be calculated. Now the script needs even more time to run. Other methods did not bring a big increase in productivity, but made the code less readable. I think it's time for hip hop.

Update: since hiphop php only works on linux, and I don’t have it, I decided to rewrite all this in C ++. Nice to brush up on old skills. Also, if I find a way to use hip-hop, it will be interesting to compare the C ++ code written by hand and create one hip-hop.

Update: I rewrote this thing in C ++, on average it works 20 times faster and uses much less memory. Let me see if I can do this even faster.

Answer 1

Accessing an array in PHP can be slow. PHP uses hash tables to implement arrays, i.e. To access an element in an array, it must compute a hash and traverse the linked list. Using a compiled language with real arrays will certainly improve performance because there is direct access to memory. For those interested: Code for hash access with a string and with an integer .

As for your code, there are a few points that I would optimize:

• return , not twice break .
• put $file->get_width() and $file->get_height in simple variables. I assume that the height or width does not change throughout the process. Remember: functions in PHP are slow.
• Use a one-dimensional array instead of nested arrays. You save one hash search per iteration this way. In fact, a one-dimensional array is only slightly faster or even slightly slower. Comparison of several ways to store performance and memory usage data .

.

 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; } 

Although I'm not sure why you are adding $x to $width / $y in $height . You do not want to iterate over the current coordinates to the borders of the image?

Answer 2

The solution to your problem could be https://github.com/facebook/hiphop-php/wiki/

As everyone has said, PHP is not the optimal language for intensively calculated tasks. It also does not have an array type. What is described as array() in PHP really is a dictionary / hash map. It has several optimizations for the double list, but, as you have already discovered, it does not provide the same runtime behavior as C pointers and arrays.

HipHop can convert PHP code to optimized C ++. It was also aimed at string manipulation, but it could very well offer the correct array / list conversion.

Disclaimer: I have never tried. Just wanted to make a useful sound answer here.

Answer 3

To suggest another alternative to PHP:

Have you viewed SplFixedArray ?

Depending on how the arrays are structured (linear from 0 to x), this can work pretty quickly

For comparison: http://www.slideshare.net/tobias382/new-spl-features-in-php-53 Slide 15 and 16 (sorry, I did not find the best)

Answer 4

A later alternative is the QB extension for PHP, specifically designed to solve this problem.

Although PHP is an excellent language for creating a complex web application, it imposes certain limitations. Writing code that performs low-level, computationally intensive tasks in PHP. usually impractical - it's just too slow. The QB extension addresses this weakness of PHP. By translating Zend code codes and executing them through a statically typed virtual machine, QB provides performance gains in order of magnitude. The added power allows PHP programmers to do what they could not do before, the integrated processing of images at the pixel level.

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

Answer 5

Arrays in PHP really seem pretty slow, especially looping around multidimensional arrays. Another option is to try Quercus . This is a PHP implementation in Java. I suppose it uses Java arrays. I didn’t even make a comparison.

Answer 6

The question is almost identifiable as "mostly opinion-based." With that in mind:

"Is PHP just not good?"

PHP was originally just a web template language, and simplicity was more dangerous than performance when it was developed. It evolved over time, and many optimizations were added, but nonetheless, PHP performance is relatively poor for other platforms. Therefore, if your criteria is performance, then PHP is not suitable for this.

"I'm going to convert all this into a compiled language."

Technically, you can also compile PHP. There is a PHP compiler from C ++ from Facebook. Zend has a fair kind of compiler. There used to be PHP on the Java interpreter (although not active, if I remember correctly).

I would recommend you try Java, since the syntax is similar, after all, it was one of the inspirations of PHP 5. Java bytecode compiled into native code with JDK 1.5. Performance should occur about 4 times for the same code structure (if you are using the PHP community distribution kit).