Everything

php

Hashtable collision resolution in PHP 7

php.internals

Pawel Por

9 years ago

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

Sara Golemon

9 years ago

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

On Tue, May 16, 2017 at 4:28 AM, Pawel Por <porparek@gmail.com> wrote:

Julien Pauli

9 years ago

On Tue, May 16, 2017 at 12:00 PM, Sara Golemon <pollita@php.net> wrote:

> https://nikic.github.io/2014/12/22/PHPs-new-hashtable-implementation.html
>
> On Tue, May 16, 2017 at 4:28 AM, Pawel Por <porparek@gmail.com> wrote:
> > 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.

Dmitry Stogov

9 years ago

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

________________________________
From: Pawel Por <porparek@gmail.com>
Sent: Tuesday, May 16, 2017 12:28:36 PM
To: internals@lists.php.net
Subject: [PHP-DEV] Hashtable collision resolution in PHP 7

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

--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: http://www.php.net/unsub.php