Exploit fully packed array/hash property

Hi Dmitry,

On second thought, I might have dismissed your HASH_FLAG_*_KEYS idea prematurely.

Of course we will have to set/unset the flag in parts of the code that are very hot and naturally that will lead to a regression in terms of CPU instructions. But in regards to your idea of possibly eliminating redundant checks on every loop iteration, I think it could be interesting. It's a tradeoff between maintaining the necessary flags and avoiding repeatedly iterating over branches. Given that bitwise operations on these flags are just about the cheapest operations the CPU can perform (no pipeline stalls and flags usually already in L1 cache at that point), and branching inside a loop being extremely costly (with the risk of pipeline stalls caused by branch miss prediction, which might even happen repeatedly, and EXPECTED/UNEXPECTED macros undesirable in most of these cases), choosing to maintain those flags on write operations in order to speed up read operations suddenly looks much more appealing. In many operations that deal with the hash table in bulk we might even be able to set the flag just once upfront. So maybe we should investigate further. Your quick test is not conclusive because you have effectively only benchmarked the negatives without settling it with the positives.

I don't know wether the additional code complexity is worth the effort though. Personally I'd like to focus on getting more out of the packed hash table case, meaning trying to preserve the packed characteristics and utilizing dedicated code paths as much as possible throughout the entire code base while using the existing infrastructure to do so without additional overhead. Packed arrays are very ubiquitous after all, and as HT_IS_PACKED always implicates HASH_FLAG_LONG_KEYS, there is not that great of a need for the latter if we can ensure to use packed arrays wherever possible.

On another note, and this comes without any caveats, we could at least use HT_IS_WITHOUT_HOLES to get rid of repeated checks for Z_TYPE(p->val) == IS_UNDEF inside loops. This would not entail any overhead on write. What do you think?

Cheers,

Benjamin

========== Original ==========
From: Dmitry Stogov dmitry@zend.com
To: Benjamin Coutu ben.coutu@zeyos.com, Xinchen Hui xinchen.h@zend.com, Nikita Popov nikita.ppv@gmail.com, Joe Watkins pthreads@pthreads.org, "Bob Weinand" bobwei9@hotmail.com, Andrea Faulds ajf@php.net
Date: Wed, 19 Oct 2016 18:02:53 +0200
Subject: Re: [PHP-DEV] Exploit fully packed array/hash property

This is an option.

If nobody propose a better solution, I'll prepare the patch tomorrow (this solution won't make BC breaks at all).

BTW: I think, HASH_FLAG_*_KEYS may be used to eliminate redundant checks on every loop iteration in some functions.

Thanks. Dmitry.