Hashtable collision resolution in PHP 7

8 years ago by Pawel Por — view source — reply

unread

I'm trying to understand why PHP 7 hashtables are more efficient than
PHP 5 hashtables.
I'm confused about hashes that are in collision.
In PHP 5 there were a linked lists to resolve collisions.
What about PHP 7 ? Are there still linked lists ?
I read somewhere that the solution taken in PHP 7 is L1 cache friendly
so I conclude PHP 7 cannot resolve collisions using linked lists but
rather arrays.
If so please write me where the buckets that are in collision are
stored in memory I mean by what field the array is pointed to by (e.g.
zval.u2.next) and a few words of high level design of how it is
implemented.

thanks for help

8 years ago by Sara Golemon — view source — reply

unread

https://nikic.github.io/2014/12/22/PHPs-new-hashtable-implementation.html

Hi

I'm trying to understand why PHP 7 hashtables are more efficient than
PHP 5 hashtables.
I'm confused about hashes that are in collision.
In PHP 5 there were a linked lists to resolve collisions.
What about PHP 7 ? Are there still linked lists ?
I read somewhere that the solution taken in PHP 7 is L1 cache friendly
so I conclude PHP 7 cannot resolve collisions using linked lists but
rather arrays.
If so please write me where the buckets that are in collision are
stored in memory I mean by what field the array is pointed to by (e.g.
zval.u2.next) and a few words of high level design of how it is
implemented.

thanks for help

8 years ago by Julien Pauli — view source — reply

unread

https://nikic.github.io/2014/12/22/PHPs-new-hashtable-implementation.html

Hi

I'm trying to understand why PHP 7 hashtables are more efficient than
PHP 5 hashtables.
I'm confused about hashes that are in collision.
In PHP 5 there were a linked lists to resolve collisions.
What about PHP 7 ? Are there still linked lists ?
I read somewhere that the solution taken in PHP 7 is L1 cache friendly
so I conclude PHP 7 cannot resolve collisions using linked lists but
rather arrays.
If so please write me where the buckets that are in collision are
stored in memory I mean by what field the array is pointed to by (e.g.
zval.u2.next) and a few words of high level design of how it is
implemented.

thanks for help

I also blogged about that,

http://jpauli.github.io/2016/04/08/hashtables.html

Short answer : yes, there is a single-linked-list to solve collisions in
PHP 7 hashtables.

Julien.

8 years ago by Dmitry Stogov — view source — reply

unread

PHP 7 still uses a kind of linked list for collision resolution (trough zval.u2.next) and this is still an expensive operation.