From d91e2e47d4cd68b2d9978181a36d5c304f61eb51 Mon Sep 17 00:00:00 2001 From: Nikita Popov Date: Mon, 18 Jul 2016 23:40:07 +0200 Subject: [PATCH] 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. --- ext/standard/array.c | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) diff --git a/ext/standard/array.c b/ext/standard/array.c index 3ffced130c..359bd978d4 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]; -- 2.50.1