Understanding PHP 7 Internals: HashTable中文EN

In my two earlier articles Deep dive into the PHP7 kernel: zval and Deep dive into the PHP7 kernel: Reference, I introduced some of the redesign thinking and results around zval and reference at the time we were developing PHP7. After that, because I really had limited energy, I didn't continue writing. Now, more than a year later, because of this sudden epidemic, I've been working from home a lot, and I've finally had time to continue introducing the changes to the Hashtable in PHP7, and the considerations behind the changes we made at the time.

PHP5

For folks who've been following the PHP kernel, you're probably fairly familiar with the PHP5 Hashtable, but let's still briefly review the PHP5 Hashtable first:

In the PHP5 implementation, the core of the Hashtable is that it stores a series of pointers to zval pointers, i.e. zval** (I've met quite a few folks who ask why it's zval** rather than zval*. The reason is actually quite simple: because multiple positions in the Hashtable can point to the same zval. The most common possibility is during COW — when we need to point a variable to a new zval, if the symbol table stores zval*, then we can't achieve "modify one place and have all holders be aware of it." So it must be zval**). The original point of this design was to let the Hashtable store information of any size, not just pointers, but also a block of memory value (though in practice, in most cases, e.g. the symbol table, it still stores pointers to zval).
The PHP5 code also used a fairly Hacky way to determine what's being stored:

#define UPDATE_DATA(ht, p, pData, nDataSize)
    if (nDataSize == sizeof(void*)) {
        if ((p)->pData != &(p)->pDataPtr) {
            pefree_rel((p)->pData, (ht)->persistent);
        }
        memcpy(&(p)->pDataPtr, pData, sizeof(void *));
        (p)->pData = &(p)->pDataPtr;
    } else {
        if ((p)->pData == &(p)->pDataPtr) {
            (p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent);
            (p)->pDataPtr=NULL;
        } else {
            (p)->pData = (void *) perealloc_rel((p)->pData, nDataSize, (ht)->persistent);   
            /* (p)->pDataPtr is already NULL so no need to initialize it */             
        }
        memcpy((p)->pData, pData, nDataSize);
    }

It checks whether the stored size is the size of a pointer, and thereby updates the stored content in different ways. A very Hacky approach.

In the PHP5 Hashtable, every Bucket is allocated and freed separately.

And the data stored in the Hashtable is also linked into a list via the pListNext pointer, so it can be traversed directly. For this part, see my very early article Deep dive into PHP: Arrays.

Problems

When writing PHP7, we thought through in detail several possible optimization points, and also summarized from a performance standpoint the following problems with the current implementation:

• In PHP, the most common use of the Hashtable is to store various zvals. The PHP5 HashTable is designed to be too generic — it could be designed and optimized specifically for storing zvals, thereby reducing memory usage.
• 2. Cache locality. Because the PHP5 Hashtable's Buckets, including the zvals, are all allocated independently, and it uses a List to chain all elements in the Hashtable, this causes cache-unfriendly behavior when traversing or sequentially accessing an array.
  
  For example, as shown in the figure, a common foreach over an array in PHP code will incur multiple memory jumps.
• 3. Similar to point 1, in the PHP5 Hashtable, to access a zval, because it's zval**, you need to at least dereference the pointer twice. On one hand this is cache-unfriendly; on the other hand it's also inefficient.
  For example, in the figure above, in the part inside the blue box, after we find the bucket in the array, we still need to dereference the zval** before we can read the actual zval content. That is, two memory reads are needed. Inefficient.

Of course there are many other problems; I won't go into them here. To be honest, it's been more than two years, and some of what I was thinking back then I can't even remember now. Let's now look at PHP7's.

PHP7

First, in PHP7, our consideration at the time was that, worried the Hashtable was used so much that our newly designed struct might not cover all scenarios, we defined a new struct called zend_array. Of course, after a series of efforts, we found that zend_array could completely replace the Hashtable. In the end we kept both names, Hashtable and zend_array, but they're just aliases for each other.
In the articles below, I'll use HashTable to specifically refer to the Hashtable in PHP5, and zend_array to refer to the Hashtable in PHP7.

Let's first look at the definition of zend_array:

struct _zend_array {
    zend_refcounted_h gc;
    union {
        struct {
            ZEND_ENDIAN_LOHI_4(
                zend_uchar    flags,
                zend_uchar    _unused,
                zend_uchar    nIteratorsCount,
                zend_uchar    _unused2)
        } v;
        uint32_t flags;
    } u;
    uint32_t          nTableMask;
    Bucket           *arData;
    uint32_t          nNumUsed;
    uint32_t          nNumOfElements;
    uint32_t          nTableSize;
    uint32_t          nInternalPointer;
    zend_long         nNextFreeElement;
    dtor_func_t       pDestructor;
};

Compared with the Hashtable from the PHP5 era, zend_array's memory usage was reduced from 72 bytes in PHP5 to 56 bytes. Think of the tens of thousands of arrays in a single PHP lifecycle — the memory reduction is significant.

Let me specially clarify the role of ZEND_ENDIAN_LOHT_4 in the zend_array definition above. This is to solve the big/little-endian problem — it lets the elements inside maintain the same memory storage order on both big-endian and little-endian, so we can conveniently write generic bit operations. In PHP7, bit operations are used a lot, because this way a single byte can store 8 state bits, which saves a lot of memory. 🙂

#ifdef WORDS_BIGENDIAN
# define ZEND_ENDIAN_LOHI_4(a, b, c, d)    d; c; b; a;
#else
# define ZEND_ENDIAN_LOHI_4(a, b, c, d)    a; b; c; d;
#endif

And the data is core-stored in arData. arData is an array of Bucket, defined as:

typedef struct _Bucket {
    zval              val;
    zend_ulong        h;   /* hash value (or numeric index)   */
    zend_string      *key; /* string key or NULL for numerics */
} Bucket

Comparing with the PHP5 Bucket:

typedef struct bucket {
    ulong h;               /* Used for numeric indexing */
    uint nKeyLength;
    void *pData;
    void *pDataPtr;
    struct bucket *pListNext;
    struct bucket *pListLast;
    struct bucket *pNext;
    struct bucket *pLast;
    const char *arKey;
} Bucket;

Memory usage was reduced from 72 bytes to 32 bytes. Think of the hundreds of thousands of array elements in a single PHP process — this memory reduction is even more significant.

Comparing them:

• The current collision chain is replaced by bauck.zval->u2.next, so bucket->pNext and bucket->pLast can be removed.
• zend_array->arData is an array, so we no longer need pListNext and pListLast to maintain order; they can also be removed. Now the ordering of elements in the array is entirely determined by their index order in arData — elements added earlier are at lower indices.
• The Bucket in PHP7 now directly stores a zval, replacing the pData and pDataPtr in the PHP5-era bucket.
• Finally, PHP7 now uses zend_string as the array's string key, replacing the PHP5-era bucket's *key, nKeylength.

Now let's look at the overall organizational diagram of zend_array:

Recalling Deep dive into the PHP7 kernel: ZVAL, the current zend_array can handle the role of a HashTable in various scenarios.
Specially, there's one thing to note — the previously mentioned IS_INDIRECT. Do you all remember it? In the previous article I mentioned why the original HashTable was designed to store zval**. Now, because _Bucket directly stores a zval, how do we solve the need for "modify one place and have it visible in multiple places" during COW? IS_INDIRECT was born for this. The IS_INDIRECT type can essentially be understood as a zval* struct. It's widely applied in scenarios where two HashTables need to point to the same ZVAL, such as GLOBALS, Properties, and so on.

Additionally, for some extensions that used to use the HashTable to store their own memory, this can now be implemented via the IS_PTR zval type.

Now that arData is a contiguous array, when foreach-ing, we can sequentially access a block of contiguous memory. And now that the zval is directly stored in the bucket, in the vast majority of cases (content that doesn't need an external pointer, e.g. long, bool, etc.) we don't need any extra zval pointer dereferencing at all — cache-locality friendly, with a very significant performance improvement.

Also, in the PHP5 era, when looking up an array element, because what was passed in was char *key, we needed to compute the key's Hash value on every lookup. Now the key passed in at lookup time is a zend_string, so the Hash value doesn't need to be recomputed — there's also some performance improvement here.

ZEND_API zval* ZEND_FASTCALL zend_hash_find(const HashTable *ht, zend_string *key);
ZEND_API zval* ZEND_FASTCALL zend_hash_str_find(const HashTable *ht, const char *key, size_t len);
ZEND_API zval* ZEND_FASTCALL zend_hash_index_find(const HashTable *ht, zend_ulong h);
ZEND_API zval* ZEND_FASTCALL _zend_hash_index_find(const HashTable *ht, zend_ulong h);

Of course, PHP7 also kept the zend_hash_str_find API for looking up directly via char*. This is very useful for scenarios where only char* is available, as it can avoid the memory overhead of generating a zend_string.

Additionally, we also did a fair number of further optimizations:

Packed array

For arrays with string keys, zend_array stores the mapping from Hash value to arData in arHash. Some folks might wonder why arHash wasn't seen in zend_array? That's because arHash and arData are allocated together:

HashTable Data Layout
=====================

         +=============================+
pointer->| HT_HASH(ht, ht->nTableMask) |
         | ...                         |
         | HT_HASH(ht, -1)             |
         +-----------------------------+
arData ->| Bucket[0]                   |
         | ...                         |
         | Bucket[ht->nTableSize-1]    |
         +=============================+

As shown in the figure, in fact arData is the middle part of a single allocated block of memory; the real starting position of the allocated memory is actually pointer, and arData is a computed intermediate position. This way one pointer can express two positions, with each position obtained via forward/backward offset. For example, -1 corresponds to arHash[0]. This trick was also widely applied throughout the PHP7 process — for example, because zend_object is variable-length, there can't be other elements after it; to implement some custom objects, we'd allocate custom elements in front of zend_object, and so on.

For arrays that are all numeric keys, arHash becomes less necessary, so in this case we use a new kind of array, the packed array, to optimize this scenario.

For arrays with HASH_FLAG_PACKED (the flag is in zend_array->u.flags), they are arrays with only contiguous numeric keys. They don't need Hash value mapping, so reading such an array is like directly accessing a C array — you directly get the zval by offset.

<?php
echo "Packed array:n";
$begin = memory_get_usage();
$array = range(0, 10000);
echo "Memory: ", memory_get_usage() - $begin, " bytesn";
$begin = memory_get_usage();
$array[10001] = 1;
echo "Memory Increased: ", memory_get_usage() - $begin, " bytesn";

$start = microtime(true);
for ($i = 0; $i < 10000; $i++) {
    $array[$i];
}
echo "Time: ", (microtime(true) - $start) * 1000 , " msn";

unset($array);

echo "nMixed array:n";
$begin = memory_get_usage();
$array = range(0, 10000);
echo "Memory: ", memory_get_usage() - $begin, " bytesn";
$begin = memory_get_usage();
$array["foo"] = 1;
echo "Memory Increased: ", memory_get_usage() - $begin, " bytesn";

$start = microtime(true);
for ($i = 0; $i < 10000; $i++) {
    $array[$i];
}
echo "Time: ", (microtime(true) - $start) * 1000 ," msn";

The simple test shown in the figure outputs the following on my machine (note that some of this test's results may be affected by your machine, including what extensions are installed, so remember to use -n):

$ /home/huixinchen/local/php74/bin/php -n /tmp/1.php
Packed array:
Memory: 528480 bytes
Memory Increased: 0 bytes
Time: 0.49519538879395 ms

Mixed array:
Memory: 528480 bytes
Memory Increased: 131072 bytes
Time: 0.63300132751465 ms

As you can see, when we use $array[“foo”]=1 to force an array from a PACKED ARRAY into a Mixed Array, the memory growth is obvious. This part is because memory needs to be allocated for 10000 arHash entries.
And the time to iterate via index: the Packed Array is only 78% of the Mixed Array.

But here I still want to specially clarify: a packed array is always an array whose numeric keys are added in natural increment order. For example, the following kind of array is NOT a packed array:

$arr[2] = 1;
$arr[1] = 2;
$arr[0] = 3;

Although this array's index values are in natural increment, the order of addition is not by the index value's increment. This is also to guarantee the property that PHP array foreach traversal order is by addition order.

For example, if you foreach the array above, you'll find you still get the values 1, 2, 3 in order.

For such arrays, we still record the addition order according to arHash.

In general, the values in arData are naturally incrementally used in addition order, while the index order is recorded in arHash.

Static key array

For string arrays, at destruction time the string keys need to be freed, and when copying the array the key's refcount needs to be incremented. But if all the keys are INTERNED strings, then in fact we don't need to worry about these at all. So this HASH_FLAG_STATIC_KEYS was born.

Empty array

We analyzed and found that in actual use there are a large number of empty arrays. For these, when initializing an array, if not specially declared, arData is not allocated by default. At this point the array is marked as HASH_FLAG_UNINITIALIZED, and only when an actual write occurs is arData allocated.

Immutable array

Similar to INTERNED STRING, in PHP7 we also introduced a kind of Immutable array, flagged by IS_ARRAY_IMMUTABLE in array->gc.flags. You can understand it as an unchangeable array. For such arrays, no COW occurs and no counting is needed. This also greatly improves the operation performance of such data. My Yaconf makes heavy use of this data characteristic.

SIMD

In later PHP7 versions, I implemented a framework of SIMD-instruction-set optimizations, e.g. SIMD's base64_encode. And in the HashTable's initialization, we also applied some of these instruction sets (the application here is very small, but it's worth mentioning):

ifdef __SSE2__
        do {
            __m128i xmm0 = _mm_setzero_si128();
            xmm0 = _mm_cmpeq_epi8(xmm0, xmm0);
            _mm_storeu_si128((__m128i*)&HT_HASH_EX(data,  0), xmm0);
            _mm_storeu_si128((__m128i*)&HT_HASH_EX(data,  4), xmm0);
            _mm_storeu_si128((__m128i*)&HT_HASH_EX(data,  8), xmm0);
            _mm_storeu_si128((__m128i*)&HT_HASH_EX(data, 12), xmm0);
        } while (0);
#else
        HT_HASH_EX(data,  0) = -1;
        HT_HASH_EX(data,  1) = -1;
        HT_HASH_EX(data,  2) = -1;
        HT_HASH_EX(data,  3) = -1;
        HT_HASH_EX(data,  4) = -1;
        HT_HASH_EX(data,  5) = -1;
        HT_HASH_EX(data,  6) = -1;
        HT_HASH_EX(data,  7) = -1;
        HT_HASH_EX(data,  8) = -1;
        HT_HASH_EX(data,  9) = -1;
        HT_HASH_EX(data, 10) = -1;
        HT_HASH_EX(data, 11) = -1;
        HT_HASH_EX(data, 12) = -1;
        HT_HASH_EX(data, 13) = -1;
        HT_HASH_EX(data, 14) = -1;
        HT_HASH_EX(data, 15) = -1;
#endif

Existing problems

In implementing zend_array to replace HashTable, we ran into a lot of problems. The vast majority of them were solved, but one problem was left over. Because now arData is allocated contiguously, when the array grows in size to the point where it needs to expand, we can only realloc the memory again. But the system doesn't guarantee that the address won't change after your realloc, so it's possible that:

<?php
$array = range(0, 7);

set_error_handler(function($err, $msg) {
    global $array;
    $array[] = 1; //force resize;
});

function crash() {
    global $array;
    $array[0] += $var; //undefined notice
}

crash();

For example, in the example above, first there's a global array, then in the function crash, in the += opcode handler, the zend vm first gets the content of array[0], then does +$var, but var is an undefined variable, so at this point an undefined-variable notice is triggered. And at the same time we set an error_handler, in which we add an element to this array. Because arrays in PHP pre-allocate space by 2^n, at this point the array is full and needs to resize, so a realloc occurs. After returning from the error_handler, the memory array[0] points to may have changed. At this point a memory read/write error, or even a segfault, can occur. Folks interested can try running this example with valgrind to see.

But this problem has quite a lot of trigger conditions, and fixing it requires extra work on the data structure, or requires splitting add_assign which would affect performance. Also, in the vast majority of cases, because the array's pre-allocation strategy exists, and other most multi-opcode handler read/write operations are basically very close together, this problem is actually quite hard to be triggered by real code, so this problem has been left hanging.

Finally, let's stop here for now, and I'll add more later when I think of something. Also, most of the content here can also be found in a presentation PPT I gave four years ago: The Secret of PHP7’s Performance.