Changed HashTable layout:

Removed HashTable->arHash (reduced memory consumption). Now hash slots may be accessed using HT_HASH() macro.
Hash slotas are allocated together with Buckets (before them) and lay in reverse order from HashTable->arData base address (see comments in Zend/zend_types.h)
Indexes in hash table and conflict resolution chains (Z_NEXT) may be stored as indeces or offsets in bytes, depending on system (32 or 64-bit).
HashTable data filelds are reordered to keep the most useful for zend_hash_find() data in the same CPU cache line.

1 files changed, 34 insertions, 28 deletions

diff --git a/Zend/zend_string.c b/Zend/zend_string.c
index 634e2c8104..f20304570a 100644
--- a/Zend/zend_string.c
+++ b/Zend/zend_string.c
@@ -50,10 +50,9 @@ void zend_interned_strings_init(void)
 
 	zend_hash_init(&CG(interned_strings), 1024, NULL, _str_dtor, 1);
 
-	CG(interned_strings).nTableMask = CG(interned_strings).nTableSize - 1;
-	CG(interned_strings).arData = (Bucket*) pecalloc(CG(interned_strings).nTableSize, sizeof(Bucket), 1);
-	CG(interned_strings).arHash = (uint32_t*) pecalloc(CG(interned_strings).nTableSize, sizeof(uint32_t), 1);
-	memset(CG(interned_strings).arHash, INVALID_IDX, CG(interned_strings).nTableSize * sizeof(uint32_t));
+	CG(interned_strings).nTableMask = -CG(interned_strings).nTableSize;
+	HT_SET_DATA_ADDR(&CG(interned_strings), pemalloc(HT_SIZE(&CG(interned_strings)), 1));
+	HT_HASH_RESET(&CG(interned_strings));
 
 	/* interned empty string */
 	str = zend_string_alloc(sizeof("")-1, 1);
@@ -89,10 +88,10 @@ static zend_string *zend_new_interned_string_int(zend_string *str)
 	}
 
 	h = zend_string_hash_val(str);
-	nIndex = h & CG(interned_strings).nTableMask;
-	idx = CG(interned_strings).arHash[nIndex];
-	while (idx != INVALID_IDX) {
-		p = CG(interned_strings).arData + idx;
+	nIndex = h | CG(interned_strings).nTableMask;
+	idx = HT_HASH(&CG(interned_strings), nIndex);
+	while (idx != HT_INVALID_IDX) {
+		p = HT_HASH_TO_BUCKET(&CG(interned_strings), idx);
 		if ((p->h == h) && (p->key->len == str->len)) {
 			if (!memcmp(p->key->val, str->val, str->len)) {
 				zend_string_release(str);
@@ -107,18 +106,25 @@ static zend_string *zend_new_interned_string_int(zend_string *str)
 
 	if (CG(interned_strings).nNumUsed >= CG(interned_strings).nTableSize) {
 		if (CG(interned_strings).nTableSize < HT_MAX_SIZE) {	/* Let's double the table size */
-			Bucket *d = (Bucket *) perealloc_recoverable(CG(interned_strings).arData, (CG(interned_strings).nTableSize << 1) * sizeof(Bucket), 1);
-			uint32_t *h = (uint32_t *) perealloc_recoverable(CG(interned_strings).arHash, (CG(interned_strings).nTableSize << 1) * sizeof(uint32_t), 1);
-
-			if (d && h) {
-				HANDLE_BLOCK_INTERRUPTIONS();
-				CG(interned_strings).arData = d;
-				CG(interned_strings).arHash = h;
-				CG(interned_strings).nTableSize = (CG(interned_strings).nTableSize << 1);
-				CG(interned_strings).nTableMask = CG(interned_strings).nTableSize - 1;
+			void *new_data;
+			void *old_data = HT_GET_DATA_ADDR(&CG(interned_strings));
+			Bucket *old_buckets = CG(interned_strings).arData;
+
+			HANDLE_BLOCK_INTERRUPTIONS();
+			CG(interned_strings).nTableSize += CG(interned_strings).nTableSize;
+			CG(interned_strings).nTableMask = -CG(interned_strings).nTableSize;
+			new_data = malloc(HT_SIZE(&CG(interned_strings)));
+
+			if (new_data) {
+				HT_SET_DATA_ADDR(&CG(interned_strings), new_data);
+				memcpy(CG(interned_strings).arData, old_buckets, sizeof(Bucket) * CG(interned_strings).nNumUsed);
+				free(old_data);
 				zend_hash_rehash(&CG(interned_strings));
-				HANDLE_UNBLOCK_INTERRUPTIONS();
+			} else {
+				CG(interned_strings).nTableSize = CG(interned_strings).nTableSize >> 1;
+				CG(interned_strings).nTableMask = -CG(interned_strings).nTableSize;
 			}
+			HANDLE_UNBLOCK_INTERRUPTIONS();
 		}
 	}
 
@@ -131,9 +137,9 @@ static zend_string *zend_new_interned_string_int(zend_string *str)
 	p->key = str;
 	Z_STR(p->val) = str;
 	Z_TYPE_INFO(p->val) = IS_INTERNED_STRING_EX;
-	nIndex = h & CG(interned_strings).nTableMask;
-	Z_NEXT(p->val) = CG(interned_strings).arHash[nIndex];
-	CG(interned_strings).arHash[nIndex] = idx;
+	nIndex = h | CG(interned_strings).nTableMask;
+	Z_NEXT(p->val) = HT_HASH(&CG(interned_strings), nIndex);
+	HT_HASH(&CG(interned_strings), nIndex) = HT_IDX_TO_HASH(idx);
 
 	HANDLE_UNBLOCK_INTERRUPTIONS();
 
@@ -178,15 +184,15 @@ static void zend_interned_strings_restore_int(void)
 		GC_REFCOUNT(p->key) = 1;
 		zend_string_free(p->key);
 
-		nIndex = p->h & CG(interned_strings).nTableMask;
-		if (CG(interned_strings).arHash[nIndex] == idx) {
-			CG(interned_strings).arHash[nIndex] = Z_NEXT(p->val);
+		nIndex = p->h | CG(interned_strings).nTableMask;
+		if (HT_HASH(&CG(interned_strings), nIndex) == HT_IDX_TO_HASH(idx)) {
+			HT_HASH(&CG(interned_strings), nIndex) = Z_NEXT(p->val);
 		} else {
-			uint prev = CG(interned_strings).arHash[nIndex];
-			while (Z_NEXT(CG(interned_strings).arData[prev].val) != idx) {
-				prev = Z_NEXT(CG(interned_strings).arData[prev].val);
+			uint32_t prev = HT_HASH(&CG(interned_strings), nIndex);
+			while (Z_NEXT(HT_HASH_TO_BUCKET(&CG(interned_strings), prev)->val) != idx) {
+				prev = Z_NEXT(HT_HASH_TO_BUCKET(&CG(interned_strings), prev)->val);
  			}
-			Z_NEXT(CG(interned_strings).arData[prev].val) = Z_NEXT(p->val);
+			Z_NEXT(HT_HASH_TO_BUCKET(&CG(interned_strings), prev)->val) = Z_NEXT(p->val);
  		}
  	}
 #endif