C apis for efficiently adding/checking if a pointer is in a HashTable, reducing hash collisions?

[TysonAndre]

Description

Description

C pointers in php are aligned to at least ZEND_MM_ALIGNMENT_LOG2 (generally 3 on 64-bit systems, 2 on 32-bit systems), whether they're from malloc or emalloc. (the lowest bit of the pointer represents the address of the byte)

Often, PECLs or php has use cases for inserting, deleting, and iterating over pointers in a hash map, and this is much slower when they collide to the same 1 in 8 (or 1 in 16, for larger value types) hash buckets

• e.g. in Improve performance of WeakReference/WeakMap. Avoid hash collisions on pointers. #7690 saw a performance improvement from the reduction in hash collisions from shifting the pointers (and issues referencing that PR)

• For access patterns such as allocating alternating keys and values, or pointers to large objects, there may be even more collisions with emalloc

Adding a struct such as struct zend_ptr_hash { struct zend_hash inner; } and macros/functions for common use cases when pointers are used as keys may help (zend_ptr_hash*). It'd probably be better to use the zend_hash directly.

The helper function static zend_always_inline zend_ulong zend_rotr3(zend_ulong key) in opcache could be used for preserving all bits of the pointer while avoiding hash collisions

---

The x32 ABI (64 bit pointers and 32 bit zend_long) is not officially supported by PHP, so there's no need for that in this feature request.

[TysonAndre]

PHP's unserialize() is also noticeably slower due to an instance of this for ref_props. Shifting right by ZEND_MM_ALIGN_LOG2 mitigates this, though it may need to wait for the next minor version being an change to the unserialize data representation. See igbinary/igbinary#371 (comment) for the benchmark and link to the patch used in igbinary

# php 8.2.0, with unserialize()
avg unserialize with untyped attribute: 0.0019850340
avg unserialize with typed attribute:   0.0035299640

ext/standard/var_unserializer.re

616:                                            if ((*var_hash)->ref_props) {
617:                                                    /* Remove old entry from ref_props table, if it exists. */
618-                                                    zend_hash_index_del(
619:                                                            (*var_hash)->ref_props, (zend_uintptr_t) data);
620-                                            }

707-                            zend_hash_index_update_ptr(
708:                                    (*var_hash)->ref_props, (zend_uintptr_t) data, info);
_ptr((*var_hash)->ref_props, (zend_uintptr_t) rval_ref);
919-            }

[bwoebi]

I'd like to note that when using pointers as hash indices, shifting by 3 is not always the best hash collision resolution. E.g. given a structure of size 32, they will be allocated in bins of size 32 having 5 zero bits, making shift by 5 the best solution here. This obviously only applies for one-way operations, as getting a pointer back from iteration this way is not safe.

But given that different use cases here perform better with different shift amounts, I'm not sure whether having just "one API fits all pointers" is applicable here.

[TysonAndre]

E.g. given a structure of size 32, they will be allocated in bins of size 32 having 5 zero bits, making shift by 5 the best solution here. This obviously only applies for one-way operations, as getting a pointer back from iteration this way is not safe.

I'm not sure that's what will happen with malloc when USE_ZEND_ALLOC=0, because we also need to support that use case. Though helper functions along the lines of zend_rotr3 can still be used for size 5 if benchmarks show it does better and we don't want to lose this data and want to be able to restore it (rotate by 5 bits and shift lowest 5 bits to highest 5 bits)

For the case of ref_props specifically, they're slots of a variable-size zend_object, which is aligned to 8 bits and sometimes has an address that ends in 8

• Though there's probably better cache line locality for objects with multiple typed properties if we do shift or rotate 32-byte zvals by 5 (may not be noticeable), the ref_props case doesn't need to get the original pointer

https://www.npopov.com/2014/12/22/PHPs-new-hashtable-implementation.html#hashtable-lookup (Thankfully for reducing collisions, php isn't using linear chaining, but effectively has an inline singly linked list per hash bucket with Z_NEXT macros)

[dktapps]

This issue ultimately boils down to the usage of unhashed integers as keys, which is an issue that crops up everywhere. The only real solution is built-in integer HashTable key hashing like siphash or similar. Does it really make sense to add extra APIs for this case instead of addressing the underlying problem?

[TysonAndre]

This issue ultimately boils down to the usage of unhashed integers as keys, which is an issue that crops up everywhere. The only real solution is built-in integer HashTable key hashing like siphash or similar. Does it really make sense to add extra APIs for this case instead of addressing the underlying problem?

Changing the hashing everywhere would probably negatively affect benchmarks for common use cases (and worsen cache locality for cases such as associative arrays with a few gaps)

As an alternative, @iluuu1994 mentioned https://github.com/google/cwisstable existed in another PR https://github.com/google/cwisstable https://github.com/google/cwisstable#compatibility-warnings

• Maybe embed it in a C file and expose wrapper APIs for a fixed set of common cases such as unordered uintptr_t -> void* with no garbage collection?
• The memory savings (and better cache locality) would be convenient when we know the types (e.g. uintptr_t and int)
• I believe cswisstable has a final hash step that will evenly distribute the input keys
• https://github.com/google/cwisstable/blob/main/cwisstable/policy.h has CWISS_AllocPolicy allowing the use of emalloc/efree

There's use cases such as the destructor and ordering where HashTable would do better.

I haven't tried it yet, but meant to try that for igbinary to see the performance impact for data structures for serialization and unserialization

---

Getting agreement on what to add to the public API and whether it's necessary seems like it might be difficult when HashTable is good enough for use cases when used properly (for small amounts of data, cswisstable wasn't faster, but large amounts would be noticeable)

[dktapps]

and worsen cache locality for cases such as associative arrays with a few gaps

I feel like packed arrays should be able to be used for such cases (e.g. first key offset, IS_UNDEF offsets for holes).

---

I just feel like this kind of stuff is playing whack a mole with the actual problem. I've previously run into collision problems like this in user code in one of my applications (2D coordinate indexing) and ended up writing my own extension to workaround the problem, and I don't doubt it comes up elsewhere too.