doctrine/mongodb-odm — pull request #368 by djlambert (2012-07-17 17:08:22+00:00)
Title: AlnumGenerator optimization

New algorithm to generate id which is 15% to 20% faster and supports very very large numbers. Benchmarked with the following:

```php
= 0; $t-- ) {
$a = floor( $id / pow( $base, $t ) );
$out = $out . substr( $index, $a, 1 );
$id = $id - ( $a * pow( $base, $t ) );
}

return $out;
}

// Works with large numbers over PHP_INT_MAX
function new1($id, $index)
{
$base = strlen($index);

$out = null;
do {
$out = $index[bcmod($id, $base)] . $out;
$id = bcdiv($id, $base);
} while (bccomp($id, 0) == 1);

return $out;
}

// Works with large numbers below PHP_INT_MAX
function new2($id, $index)
{
$base = strlen($index);

$out = null;
do {
$out = $index[$id % $base] . $out;
$id = bcdiv($id, $base);
} while ($id != 0);

return $out;
}

// Doesn't work with large numbers
function new3($id, $index)
{
$base = strlen($index);

$out = null;
do {
$out = $index[$id % $base] . $out;
$id = floor($id / $base);
} while ($id != 0);

return $out;
}

$chars = '0123456789ABCDEF';
$out=null;

$functions = array('orig', 'new1', 'new2', 'new3');
$times = array();

foreach ($functions as $function) {
$time_start = microtime(true);
$start = 0;
$iterations = 10000;

for ($t = $start; $t <= $start + $iterations; $t++) {
$num = bcsub(PHP_INT_MAX, $t);
//$num = $t;
$out = $function($num, $chars);
//echo "$num:$out\n";
}
$time_end = microtime(true);
$times[$function] = $time_end - $time_start;
echo "$out $function=$times[$function]\n";
}
```

I implemented this with the ORM to support unsigned bigint's on Mysql, but it should be just as applicable here.

If we were to assume id values smaller than PHP_INT_MAX new2 could be used for further performance increase. new3 is again faster than new2 and works with larger numbers than the original, but fails far short of PHP_INT_MAX. In the benchmarks above the id generated should be 7FFFFFFFFFFFD8EF (9223372036854775807 - 10000), which only new1 and new2 return. If the bcsub call is changed to bcadd only new1 continues to work, which is the one in this pull request.

Also modified the code formatting and added doc comments for setters.