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

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 https://github.com/php/php-src/pull/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.

Bắt đầu bằng cách đọc triển khai zend_hash hiện có và helper zend_rotr3 trong opcache, sau đó xem lại pull request #7690 được tham chiếu để nắm bối cảnh về xung đột và hiệu năng. Công việc được xem là hoàn tất khi thống nhất và triển khai các API băm cho khóa con trỏ, hoặc một cách tiếp cận zend_hash trực tiếp tương đương, bảo toàn các bit của con trỏ đồng thời giảm xung đột.