com php-src: Increase array_rand() rehashing treshold : ext/standard/array.c

Commit: d91e2e47d4cd68b2d9978181a36d5c304f61eb51 Author: Nikita Popov <nikic@php.net> Mon, 18 Jul 2016 23:40:07 +0200 Parents: 7f3375d5f28b1447ccc659e9867d67cf3bb86ba7 Branches: master Link: http://git.php.net/?p=php-src.git;a=commitdiff;h=d91e2e47d4cd68b2d9978181a36d5c304f61eb51 Log: Increase array_rand() rehashing treshold From 3/8 to 3/4. I was thinking in terms of nTableSize, where a requirement > 1/2 is not tenable. However, we're actually working with nNumUsed, in which case more than 1/4 tombstones should be quite unusual. Changed paths: M ext/standard/array.c Diff: diff --git a/ext/standard/array.c b/ext/standard/array.c index 3ffced1..359bd97 100644 --- a/ext/standard/array.c +++ b/ext/standard/array.c @@ -5056,8 +5056,8 @@ PHP_FUNCTION(array_rand) if (num_req == 1) { HashTable *ht = Z_ARRVAL_P(input); - /* Compact the hashtable if less than 3/8 of elements are used */ - if (num_avail < ht->nNumUsed - (ht->nNumUsed>>1) - (ht->nNumUsed>>2)) { + /* Compact the hashtable if less than 3/4 of elements are used */ + if (num_avail < ht->nNumUsed - (ht->nNumUsed>>2)) { if (ht->u.flags & HASH_FLAG_PACKED) { zend_hash_packed_to_hash(ht); } else { @@ -5066,9 +5066,9 @@ PHP_FUNCTION(array_rand) } /* Sample random buckets until we hit one that is not empty. - * The worst case probability of hitting an empty element is 1-3/8. The worst case - * probability of hitting N empty elements in a row is (1-3/8)**N. - * For N=10 this becomes smaller than 1%. */ + * The worst case probability of hitting an empty element is 1-3/4. The worst case + * probability of hitting N empty elements in a row is (1-3/4)**N. + * For N=5 this becomes smaller than 0.1%. */ do { zend_long randval = php_mt_rand_range(0, ht->nNumUsed - 1); Bucket *bucket = &ht->arData[randval];