Need an array-like structure in PHP with minimal m

Question

In my PHP script I need to create an array of >600k integers. Unfortunately my webservers memory_limit is set to 32M so when initializing the array the script aborts with message

Fatal error: Allowed memory size of 33554432 bytes exhausted (tried to allocate 71 bytes) in /home/www/myaccount/html/mem_test.php on line 8

I am aware of the fact, that PHP does not store the array values as plain integers, but rather as zvalues which are much bigger than the plain integer value (8 bytes on my 64-bit system). I wrote a small script to estimate how much memory each array entry uses and it turns out, that it's pretty exactly 128 bytes. 128!!! I'd need >73M just to store the array. Unfortunately the webserver is not under my control so I cannot increase the memory_limit.

My question is, is there any possibility in PHP to create an array-like structure that uses less memory. I don't need this structure to be associative (plain index-access is sufficient). It also does not need to have dynamic resizing - I know exactly how big the array will be. Also, all elements would be of the same type. Just like a good old C-array.

---

Edit: So deceze's solution works out-of-the-box with 32-bit integers. But even if you're on a 64-bit system, pack() does not seem to support 64-bit integers. In order to use 64-bit integers in my array I applied some bit-manipulation. Perhaps the below snippets will be of help for someone:

function push_back(&$storage, $value)
{
    // split the 64-bit value into two 32-bit chunks, then pass these to pack().
    $storage .= pack('ll', ($value>>32), $value);
}

function get(&$storage, $idx)
{
    // read two 32-bit chunks from $storage and glue them back together.
    return (current(unpack('l', substr($storage, $idx * 8, 4)))<<32 |
            current(unpack('l', substr($storage, $idx * 8+4, 4))));
}

Answer 1

Depending on how you are generate the integers, you could potentially use PHP's generators, assuming you are traversing the array and doing something with individual values.

Answer 2

You can try to use a SplFixedArray, it's faster and take less memory (the doc comment say ~30% less). Test here and here.

Answer 3

600K is a lot of elements. If you are open to alternative methods, I personally would use a database for that. Then use standard sql/nosql select syntax to pull things out. Perhaps memcache or redis if you have an easy host for that, such as garantiadata.com. Maybe APC.

Answer 4

Use a string - that's what I'd do. Store it in a string on fixed offsets (16 or 20 digits should do it I guess?) and use substr to get the one needed. Blazing fast write / read, super easy, and 600.000 integers will only take ~12M to store.

base_convert() - if you need something more compact but with minimum effort, convert your integers to base-36 instead of base-10; in this case, a 14-digit number would be stored in 9 alphanumeric characters. You'll need to make 2 pieces of 64-bit ints, but I'm sure that's not a problem. (I'd split them to 9-digit chunks where conversion gives you a 6-char version.)

pack()/unpack() - binary packing is the same thing with a bit more efficiency. Use it if nothing else works; split your numbers to make them fit to two 32-bit pieces.

Answer 5

I took the answer by @deceze and wrapped it in a class that can handle 32-bit integers. It is append-only, but you can still use it as a simple, memory-optimized PHP Array, Queue, or Heap. AppendItem and ItemAt are both O(1), and it has no memory overhead. I added currentPosition/currentSize to avoid unnecessary fseek function calls. If you need to cap memory usage and switch to a temporary file automatically, use php://temp instead.

class MemoryOptimizedArray
{
    private $_storage;
    private $_currentPosition;
    private $_currentSize;
    const BYTES_PER_ENTRY = 4;
    function __construct()
    {
        $this->_storage = fopen('php://memory', 'rw+');
        $this->_currentPosition = 0;
        $this->_currentSize = 0;
    }
    function __destruct()
    {
        fclose($this->_storage);
    }
    function AppendItem($value)
    {
        if($this->_currentPosition != $this->_currentSize)
        {
            fseek($this->_storage, SEEK_END);
        }
        fwrite($this->_storage, pack('l', $value));
        $this->_currentSize += self::BYTES_PER_ENTRY;
        $this->_currentPosition = $this->_currentSize;
    }
    function ItemAt($index)
    {
        $itemPosition = $index * self::BYTES_PER_ENTRY;
        if($this->_currentPosition != $itemPosition)
        {
            fseek($this->_storage, $itemPosition);
        }
        $binaryData = fread($this->_storage, self::BYTES_PER_ENTRY);
        $this->_currentPosition = $itemPosition + self::BYTES_PER_ENTRY;
        $unpackedElements = unpack('l', $binaryData);
        return $unpackedElements[1];
    }
}

$arr = new MemoryOptimizedArray();
for($i = 0; $i < 3; $i++)
{
    $v = rand(-2000000000,2000000000);
    $arr->AddToEnd($v);
    print("added $v\n");
}
for($i = 0; $i < 3; $i++)
{
    print($arr->ItemAt($i)."\n");
}
for($i = 2; $i >=0; $i--)
{
    print($arr->ItemAt($i)."\n");
}

Answer 6

A PHP Judy Array will use significantly less memory than a standard PHP array, and an SplFixedArray.

I quote "An array with 1 million entries using regular PHP array data structure takes 200MB. SplFixedArray uses around 90 megabytes. Judy uses 8 megs. Tradeoff is in performance, Judy takes about double the time of regular php array implementation."