title: PHP array performance
body: <p>I'm testing an algorithm for 2d bin packing and I've chosen PHP to mock it up as it's my bread-and-butter language nowadays.</p>
  
  <p>As you can see on <a href="http://themworks.com/pack_v0.2/oopack.php?ol=1" rel="noreferrer">http://themworks.com/pack_v0.2/oopack.php?ol=1</a> it works pretty well, but you need to wait around 10-20 seconds for 100 rectangles to pack. For some hard to handle sets it would hit the php's 30s runtime limit.</p>
  
  <p>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's and 1's in it. It either checks if certain cell equals to 0/1 or sets it to 0/1. It can do such operations million times and each times it takes few microseconds.</p>
  
  <p>I guess I could use an array of booleans in a statically typed language and things would be faster. Or even make an array of 1 bit values. I'm thinking of converting the whole thing to some compiled language. Is PHP just not good for it?</p>
  
  <p>If I do need to convert it to let's say C++, how good are the automatic converters? My script is just a lot of for loops with basic arrays and objects manipulations.</p>
  
  <p>Edit. This function gets called more than any other. It reads few properties of a very simple object, and goes through a very small part of a smallish array to check if there's any element not equal to 0.</p>
  
  <pre><code>function fits($bin, $w, $h, $x, $y) {
  
      $w += $x;
      $h += $y;
  
      for ($i = $x; $i &lt; $w; $i++) {
  
          for ($j = $y; $j &lt; $h; $j++) {
  
              if ($bin[$i][$j] !== 0) {
                  return false;
              }
          }
      }
  
      return true;    
  }
  </code></pre>
  
  <p>Update: I've tried using 1d array instead of 2d as one of the answers suggested. Since I needed to always have current bin width accessible, I decided to wrap everything in the object. Also, now in every loop the index needs to be calculated. Now the script takes even more time to run. Other techniques didn't bring much performance boost, rather made code less readable. Time for HipHop I guess.</p>
  
  <p>Update: since hiphop php only runs on linux, and I don't have one, I've decided to rewrite the whole thing in C++. It's nice to freshen up the old skills. Also, if I do find a way to use hiphop, it'll be interesting to compare hand-written C++ code and the one hiphop would generate.</p>
  
  <p>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 make it even faster.</p>