While working on PureTextRender package, I realized some serious limits in PHP arrays. The mentioned package renders text into BMP images using pure PHP (no GD), and for that it requires a lot of arrays to be filled and traversed. The original package only supported small images due to typical PHP memory limit (128MB) though images were monochrome BMP! Before going any further, let’s see some PHP benchmark code:

<?php //array_fill() Memory Usage	 	 
$startMemory=(memory_get_usage()/1024);	 	 
$a=array_fill(0, 1000, 0);	 	 
echo PHP_EOL.((memory_get_usage()/1024)-$startMemory)." KB".PHP_EOL;	 	 
//Result: 94.3828125 KB

As you see, a thousand array elements take 94 Kilobytes of memory, resulting in 94 bytes per element on average. Lets do more experiments. I will omit the $startMemory and the line that echo’s the memory difference in the rest of the examples in this article, and I’m running all this on a 64bit OS X:

//PHP Native Array Memory Usage	 	 
$a=array();	 	 
for ($i=0;$i<1000;++$i)	 	 
 $a[$i]=$i;	 	 

Output: 141.375 KB

As you can see, this example takes almost 50% more memory, though it is also populating a 1000 element array. It doesn’t matter what the value is in the code, I can replace =$i with =0 and it would consume the same amount of memory. A simple explanation would be that the hash table used for storing array keys needs expansion over and over, and garbage collector doesn’t get a chance to clean up before the end of the script, keeping the previous versions in place. An expansion policy of over 50% would result in about 50% overhead in memory usage.

Now the following code will only consume 20KB in spite of an expected 988 KB:

//2D array_fill() Memory Usage	 	 
$a=array_fill(0,100,array_fill(0,100,0));

The reason for this behavior is that a single array of 100 elements is created in the internal expression, and assigned by reference to all outer 100 arrays, so the resulting memory consumption is (100+1)X instead of (100*100)X. Lets repeat all the experiments using SplFixedArray:

$a=new SplFixedArray(1000); //8.5703125 KB	 	 

The above line only defines the fixed array, and the below code populated it as well:

//SplFixedArray MemoryUsage	 	 
$a=new SplFixedArray(1000);	 	 
for ($i=0;$i<1000;++$i)	 	 
 $a[$i]=$i;	 	 

Now this sample uses 55.6015625 KB of memory, making an average of 55 bytes per element. The ideal situation would be 8 bytes per element (as happens in the definition), since 64bit systems have 8 byte int elements, but the extra space is consumed by the hash table and its indices. As you can see, a 3-dimensional array of size 100 would quickly chomp up PHP memory and leave nothing to work with. Before going further with memory footprints, lets compare performance of SplFixedArray with native arrays:

//SplFixedArray Performance	 	 
$t=microtime(1);	 	 
$a=new SplFixedArray(1024*1024);	 	 
echo ((microtime(1)-$t)*1000)." ms".PHP_EOL;$t=microtime(1); //3.4949779510498 ms	 	 
for ($i=0;$i<1024*1024;++$i)	 	 
 $a[$i]=$i;	 	 
echo ((microtime(1)-$t)*1000)." ms".PHP_EOL;$t=microtime(1); //228.07097434998 ms

Creation of the array is pretty fast, but population takes a good chunk of time. Lets see how much of that time is wasted in the loop:

//PHP Loop Performance	 	 
$t=microtime(1);	 	 
for ($i=0;$i<1024*1024;++$i);	 	 
echo ((microtime(1)-$t)*1000)." ms".PHP_EOL;$t=microtime(1); //138.4379863739 ms

Well, it’s mostly PHP’s fault then. It takes almost 100 miliseconds to fill one million elements of SplFixedArray. Lets see how native PHP arrays do:

//PHP Native Array Performance	 	 
$t=microtime(1);	 	 
$a=array();	 	 
echo ((microtime(1)-$t)*1000)." ms".PHP_EOL;$t=microtime(1); //0.003814697265625 ms	 	 
for ($i=0;$i<1024*1024;++$i);	 	 
echo ((microtime(1)-$t)*1000)." ms".PHP_EOL;$t=microtime(1); //141.56699180603 ms	 	 
for ($i=0;$i<1024*1024;++$i)	 	 
 $a[$i]=$i;	 	 
echo ((microtime(1)-$t)*1000)." ms".PHP_EOL;$t=microtime(1); //329.04195785522 ms

And when using arrray_fill:

//PHP array_fill() Performance	 	 
$t=microtime(1);	 	 
$a=array_fill(0,1024*1024,0);	 	 
echo ((microtime(1)-$t)*1000)." ms".PHP_EOL;$t=microtime(1); //78.655004501343 ms	 	 
for ($i=0;$i<1024*1024;++$i);	 	 
echo ((microtime(1)-$t)*1000)." ms".PHP_EOL;$t=microtime(1); //136.88087463379 ms	 	 
for ($i=0;$i<1024*1024;++$i)	 	 
 $a[$i]=$i;	 	 
echo ((microtime(1)-$t)*1000)." ms".PHP_EOL;$t=microtime(1); //232.02109336853 ms

Not bad at all! In fact array_fill is taking half the time of filling the array already. This means that assigning values to the array are much faster than expanding the hash table.
Overall, if it takes half a second to create, fill and traverse a one mega-entry array in PHP (~140MB). A typical web PHP setup has 128MB of memory limit (per instance) and 30 seconds of running time limit. They kinda match, because if you could come up with a faster storage that consumed more memory, you would be on a memory shortage, and if you came up with a denser storage, you would probably be too slow to fully utilize it. With all that being said, it appears that PHP focuses more on speed rather than memory, since most applications run more than one pass on pieces of their data.
Before going further, lets compare everything to an equivalent C code:

//C Array Performance
#include <sys/time.h>
#include <stdio.h>
struct timeval timevar;
int main()
{
	int i=0;

	gettimeofday(&timevar, NULL); 
	long microsec = ((unsigned long long)timevar.tv_sec * 1000000) + timevar.tv_usec,microsec2;

	int a[1024*1024]; //1 microseconds

	gettimeofday(&timevar, NULL); 
	microsec2 = ((unsigned long long)timevar.tv_sec * 1000000) + timevar.tv_usec;
	printf("%lu microseconds\n",microsec2-microsec);
	microsec=microsec2;

	for (i=0;i<1024*1024;++i) //2016 microseconds
		;

	gettimeofday(&timevar, NULL); 
	microsec2 = ((unsigned long long)timevar.tv_sec * 1000000) + timevar.tv_usec;
	printf("%lu microseconds\n",microsec2-microsec);
	microsec=microsec2;

	for (i=0;i<1024*1024;++i) //3813 microseconds
		a[i]=i;

	gettimeofday(&timevar, NULL); 
	microsec2 = ((unsigned long long)timevar.tv_sec * 1000000) + timevar.tv_usec;
	printf("%lu microseconds\n",microsec2-microsec);
	microsec=microsec2;
	return 0;
}

Memory Optimized Arrays

It doesn’t appear like one could improve performance of PHP arrays beyond what SplFixedArray already does, but there might be cases where a piece of code requires denser memory access to perform its task. The PureTextRender package mentioned above is one of those instances, where it needs a huge bitmap array, every element of which could be only a bit, fills it with generated content, passes it through distort, scale and rotate functions; each of which runs only one linear pass over the data, and dumps the output either into a file or onto the screen. Since passing through 128MB of data took half a second, and a typical image generating code would run up to 5 seconds, we could tolerate a denser structure that is up to 10 times slower than native PHP arrays.

Unfortunately, the only underlying data structure of PHP is native arrays, even SplFixedArray is not available unless one has PHP 5.3+. To do any sort of optimized (but not compressed) data storage, we would require a flat (preferably continues) storage system to use in PHP, similar to good ol’ C arrays.

Before going crazy with ideas, I first created an array dampener for PHP, which implements multidimensional arrays using a flat linear storage of choice in PHP. This allows us to use different underlying storages on this multidimensional array implementation, and stopping PHP from doing weird reference stuff on array elements. The only downside to this multidimensional array, is that its a tad bit slow on index translations, which can be optimized for specific cases (later on this in this post).

//Multidimensional Generic Array PHP
class IndexCountMistmatch extends Exception {}
class MultidimensionalByteArray
{
	public $dimensions;
	protected $data;
	function __construct()
	{
		$args=func_get_args();
		if (count($args))
		{
			$this->dimensions=$args;
			$this->data=array(); //this is the generic part
		}

	}
	protected function calculateIndex($args)
	{
		$t=count($args);
		if ($t!=count($this->dimensions))
			throw new IndexCountMistmatch();
		$index = 0;
		$multiplier=1;
		for ($i = 0;$i < $t;$i++) 		
		{
 			$index += $args[$i] * $multiplier; 
			$multiplier *= $this->dimensions[$i];
		}

		return $index;
	}
	public function index()
	{
		$args=func_get_args();
		return $this->calculateIndex($args);
	}
	public function get()
	{
		$args=func_get_args();
		$index=$this->calculateIndex($args);
		return $this->data[$index];
	}
	public function set()
	{
		$args=func_get_args();
		$value=array_pop($args);
		$index=$this->calculateIndex($args);
		$this->data[$index]=$value;
	}
	public function size ()
	{
		$size=1;
		for ($i=0;$i<count($this->dimensions);++$i)
			$size*=$this->dimensions[$i];
		return $size;
	}
	public function count()
	{
		return strlen($this->data);
	}
}

Since PHP does not allow overriding of multidimensional array access operator [], we use the get method for that purpose; e.g $a->get(2,3,5). Now all we need, is an underlying flat storage. For the purpose of motivation stated in this document, we’d need a Bit storage, but since that’d be a little complicated, we’d first go with a Byte storage, then generalize it to a Dynamic storage, and then specialize it to a Bit storage.

//ByteArray 
class ByteArray implements arrayaccess , Countable 
{
	protected $data="";
	function __construct($size=1)
	{
		$this->data=str_repeat(chr(0), $size);
	}
	
	public function offsetExists ( $offset )
	{
		return $offset<strlen($this->data);
	}
	public function offsetGet ( $offset )
	{
		return ord($this->data[$offset]);
	}
	public function offsetSet ( $offset , $value )
	{
		return $this->data[$offset]=chr($value);
	}
	public function  offsetUnset ( $offset )
	{
		$this->offsetSet($offset,0);
	}
	public function count ()
	{
		return strlen($this->data);
	}
}

As you’ve observed, its pretty simple! The magic is in PHP strings. They are a flat, voodoo-free continues storage provided by PHP, just like good ol’ C arrays (or more like ASM arrays in this case). We initialize the string with enough number of nulls. This results in less memory thrashing (and fragmentation) when we already know the minimum size of the array we need. Our simple ByteArray does not support shrinking, but go ahead and add that if you’re eager about it. Now to have a multidimensional memory efficient array which only supports values 0 to 255, we can replace $this->data=array() with $this->data = new ByteArray() in our MultidimensionalArray class and name it MultidimensionalByteArray.

The problem with our byte arrays is that, they are byte arrays; i.e they only support one byte per element. The following DynamicArray class supports your desired number of byte per element, as long as they fit integers supported by your system:

//DynamicArray
class DynamicArray implements ArrayAccess , Countable 
{
	//big endian, no rotation needed
	static protected $wordSize=PHP_INT_SIZE; //can modify here
	protected $data="";
	function __construct($size=1)
	{
		$this->data=str_repeat(chr(0), $size*static::$wordSize);
	}
	
	public function offsetExists ( $offset )
	{
		return $offset/static::$wordSize <strlen($this->data);
	}
	public function offsetGet ( $offset )
	{
		$res="";
		for ($i=0;$i<static::$wordSize;++$i)
		{
			$res<<=8; 			
			$res|=ord($this->data[$offset*static::$wordSize + $i]);
		}
		return $res;
	}
	public function offsetSet ( $offset , $value )
	{
		for ($i=0;$i<static::$wordSize;++$i) 		
		{ 			
			$this->data[$offset*static::$wordSize + (static::$wordSize-$i-1)]=chr($value);
			$value>>=8;
		}
	}
	public function  offsetUnset ( $offset )
	{
		$this->offsetSet($offset,0);
	}
	public function count ()
	{
		return strlen($this->data/static::$wordSize);
	}
}

On a very basic level, this is actually doing what hardware is supposed to do, but since PHP is hiding that simple hardware functionality from us, we have to compromise. You can modify line 4 of the above code and set wordSize to 4, 8, 2 or even 1 to get different length arrays. Keep in mind that the longer the word size, the slower storage and retrieval of values in the array. It is actually worthwhile to rewrite some of DynamicArray for 16 bit support, just to make it faster. A for loop introduces much extra overhead, compared to this:

//DynamicArray16
class DynamicArray16 extends DynamicArray
{
	static protected $wordSize=2;
	public function offsetGet ( $offset )
	{
		return ord($this->data[$offset<<1])<data[($offset<<1) +1]); 	
	} 	
	public function offsetSet ( $offset , $value ) 	
	{ 		
		$this->data[($offset<<1)+1]=chr($value); 		
		$this->data[$offset<<1]=chr($value>>8);
	}
}

By this point, you and I are both eager to know how these creative array implementations stand against native PHP arrays, both in terms of memory usage and speed; but before we delve deeper into that realm, lets introduce the nice little entity, the BitArray:

//BitArray
class BitArray implements arrayaccess , Countable
{
	protected $data;
	protected $count=0;
	function __construct($size=1)
	{
		$this->data=new ByteArray( ((int)($size/8))+1);
	}

	public function offsetExists($offset)
	{
		$arrayIndex=floor($index/8);
		return isset($this->data[$arrayIndex]);
	}
	public function offsetGet($offset)
	{
		$arrayIndex=($offset>>3);
		$bitIndex=7-($offset&7);
		return ($this->data[$arrayIndex]>>$bitIndex)&1;
	}
	public function offsetSet($offset, $value)
	{
		if ($offset>=$this->count)
			$this->count=$offset+1;
		$arrayIndex=($offset>>3);
		$bitIndex=7- ($offset&7);
		$bit=$value&1;
		if (!isset($this->data[$arrayIndex]))
			$this->data[$arrayIndex]= $bit<<$bitIndex; 		
		else 			
			$this->data[$arrayIndex]|=($bit << $bitIndex); 	
	} 	
	public function offsetUnset($offset) 	
	{ 		
		$this->offsetSet($offset,0);
	}
	public function count()
	{
		return $this->count;
	}
	public function realCount()
	{
		return count($this->data);
	}
	public function byte($offset)
	{
		return $this->data[$offset];
	}
}

This is actually pretty clever if you’re going to use it for a bitmap, as its pretty fast (well not that pretty) and very sleek on memory. Stick this in our MultidimensionalArray and we’d end up with MultidimensionalBitArray. Just use two dimensions to have a Bitmap. Better rewrite it as well, if we want it to be fast enough:

Even though our implementations are terribly slower than native implementations, they allow for bigger arrays to be used. In certain cases, like for my Pure PHP Captcha; when I want to store font information in a bitmap array (3 dimensional bit array) of size 256x13x6, and use many instances of that script on the server, the memory footprint is much more important than the speed impact. Same is true when I’m generating CAPTCHA images and showing them on the string. Hopefully I will dedicate another post to the CAPTCHA class and how useful it is.