> In my tests doing so reduced the unserialize time from 7 secs to ~0.3 sec on 1000000-size array and size dependency apparently changed to something more like O(n*log(n))

Could you submit a patch with that modification and a test script that exemplifies the speedup?

Added a patch against latest SVN version, did things in a way that required least code modification.

Here goes the test script:

<?php
ini_set('memory_limit', '512M');

$sizes = array(100000, 200000, 500000, 1000000);

foreach($sizes as $N) {

    $data = array();
    for($i=0; $i < $N; $i++) $data[] = mt_rand();

    $timeSerialize = 0;
    $timeUnserialize = 0;

    for($run=0; $run < 10; $run++) {

        $ts = microtime(1);
        $ser = serialize($data);
        $timeSerialize +=  microtime(1) - $ts;

        $ts =  microtime(1);
        $unser = unserialize($ser);
        $timeUnserialize +=  microtime(1) - $ts;

        if (count($data) != count($unser)) print "Error: array sizes mismatch\n";
        for($i=0; $i < $N; $i++)
            if (!isset($unser[$i]) || $data[$i] != $unser[$i])
                print "Error: array elements mismatch\n";

        unset($ser);
        unset($unser);
    }

    print "Size: $N\t\tSerialize: " . (floor(1000*$timeSerialize)) . "ms\t\tUnserialize: " . (floor(1000*$timeUnserialize)) . "ms\n\n";

}
?>


It's a bit memory consuming, so array sizes might need to be reduced depending on available hardware.

My test results:

Original PHP:
Size: 100000            Serialize: 483ms                Unserialize: 470ms

Size: 200000            Serialize: 1047ms               Unserialize: 1308ms

Size: 500000            Serialize: 2638ms               Unserialize: 14360ms

Size: 1000000           Serialize: 6319ms               Unserialize: 72744ms

Patched PHP:
Size: 100000            Serialize: 500ms                Unserialize: 357ms

Size: 200000            Serialize: 870ms                Unserialize: 703ms

Size: 500000            Serialize: 2212ms               Unserialize: 1315ms

Size: 1000000           Serialize: 4898ms               Unserialize: 2823ms

Hi we cannot merge this into 5.3, as it changes a structure (php_unserialize_data) thats exported to extensions in a type, breaking the ABI. But without a doubt it should go in trunk atleast.

Implemented in trunk, thanks for your work.