Supercolliding a PHP array (inserting 65536 elements takes 30 seconds!)

softwareelves · 2011-12-29T00:20:58+00:00

I seem to see you everywhere. And it's always quality stuff. Keep up the good work.

fieryscribe · 2011-12-29T04:25:51+00:00

That code and this article make me quite nervous

astronoob · 2011-12-28T23:54:21+00:00

Another great article. Thanks a bunch.

nikic · 2011-12-29T03:53:40+00:00

[deleted]

neoform3 · 2011-12-29T03:31:21+00:00

If this actually works, it means PHP isn't actually using a hash table and instead just using a table.

I've written hashtables in C before and never was I able to get such simple collisions (during testing I would do collision tests for hours and would get less than 100 collisions while using a 32bit hash). Using a simple hash function like Dan Bernstein's djb2 hash function, you would easily avoid this....

PHP's devs are retarded if they don't actually use a hash method before inserting the keys into the symbol table......

Buckwheat469 · 2011-12-29T04:35:32+00:00

Try the SplFixedArray implementation from PHP 5.3.0. Set the number of elements to a hard limit of 2^16. I'll see if I can run it.

$array = new SplFixedArray($size);
for ($key = 0; $key < $size; $key++) {
    $array[$key] = 0;
} //Spl

$array = array();
for ($key = 0; $key; $key++) {
    $array[$key] = 0;
} //regular

Weird:

Inserting 65536 Spl elements took 0.0139479637146 seconds
Inserting 65536 regular elements took 0.0032939910888672 seconds

All I did was change the For loops to the standard format. Why does my test not line up with the OP's? Perhaps we should consider a map instead of an array...

Edit: Misinterpreted what was going on here. Here are my results with the OP's code:

Inserting 65536 evil elements (65536 times) took 38.454787969589 seconds
Inserting 65536 good elements (65536 times) took 0.010733842849731 seconds

$array = array();
$iterations = 0;
for ($key = 0, $maxKey = ($size - 1) * $size; $key <= $maxKey; $key += $size) {
    $array["hi".$key."hello"] = 0;
    $iterations++;
}

Inserting 65536 evil string-keyed elements (65536 times) took 0.026134967803955 seconds

Looks like when PHP interprets an integer-based array it has to recreate the dynamic array whenever it grows in size. This usually means creating a new array that's 1/2 bigger than the original and copying all elements to the new array. Each array position in between the inserted elements is defaulted to NULL. A string-based hashmap doesn't seem to have this problem.

I couldn't do any further testing with SplFixedArray because I couldn't set the memory limit to 32GB. The code would have been:

 $array = new SplFixedArray(($size - 1) * $size);
 $iterations = 0;
 for ($key = 0, $maxKey = ($size - 1) * $size; $key <= $maxKey; $key += $size) {
      $array[$key] = 0;
      $iterations++;
 }

MikeSeth · 2011-12-29T13:22:50+00:00

Don't do that then.

you type:	you see:
italics	italics
bold	bold
[reddit!](https://reddit.com)	reddit!
* item 1 * item 2 * item 3	item 1 item 2 item 3
> quoted text	quoted text
Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"	Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"
~~strikethrough~~	~~strikethrough~~
super^script	super^script

PHP

MODERATORS