Newsgroups: php.internals Path: news.php.net Xref: news.php.net php.internals:99060 Return-Path: Mailing-List: contact internals-help@lists.php.net; run by ezmlm Delivered-To: mailing list internals@lists.php.net Received: (qmail 46773 invoked from network); 16 May 2017 11:50:41 -0000 Received: from unknown (HELO lists.php.net) (127.0.0.1) by localhost with SMTP; 16 May 2017 11:50:41 -0000 Authentication-Results: pb1.pair.com smtp.mail=julienpauli@gmail.com; spf=pass; sender-id=pass Authentication-Results: pb1.pair.com header.from=julienpauli@gmail.com; sender-id=pass Received-SPF: pass (pb1.pair.com: domain gmail.com designates 209.85.213.68 as permitted sender) X-PHP-List-Original-Sender: julienpauli@gmail.com X-Host-Fingerprint: 209.85.213.68 mail-vk0-f68.google.com Received: from [209.85.213.68] ([209.85.213.68:36794] helo=mail-vk0-f68.google.com) by pb1.pair.com (ecelerity 2.1.1.9-wez r(12769M)) with ESMTP id 5F/43-15531-F87EA195 for ; Tue, 16 May 2017 07:50:40 -0400 Received: by mail-vk0-f68.google.com with SMTP id p85so5625502vkd.3 for ; Tue, 16 May 2017 04:50:39 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:sender:in-reply-to:references:from:date:message-id :subject:to:cc; bh=7rZbjcMP/G/K0zoUUoGGyFTea9vodQEmxM441n9GWjE=; b=ujig35ENWuGDJ3n5p68bJ8J0B4SbKrX5ovEGwAok1FdfWeEDVc/7tpwdHdzB4txVjF iEBZCrFrXQqmnw+1h+G3KtKgk9C3EPSlPd0e1LrQA0K7h3F4fsJN8JaER+S93iZyQ+Ul vKFy8RbYoXrSVKikhUc2V5nMompek7GammbMP+gbHMhziz6s2RPLW9RDJSbU98Pp6eAf r5mG9qegVPpYcmuPeqtyRN3dhgs3dRc1+GdAHsS6TydUb+Z3HsFNDV8ceFSi/OhL4zNN bFvnDl01OIIKuadVqtX/Uv6GQXQYtOYvzeX5uC0D9pmrIw128i7KBBvWKiWQI5eRt5lY Cf6Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:sender:in-reply-to:references:from :date:message-id:subject:to:cc; bh=7rZbjcMP/G/K0zoUUoGGyFTea9vodQEmxM441n9GWjE=; b=kjQ7ECl86NCAnytO2KvZJ/QeA629CMNAB9WmvzS6XJsNs+hkVuziKYC85UPrzYgMnY fVlpBVLb+Go45yaXExqBooSL8faPxoq47EjQ1ooAzwq81A2lJ6av/mcXvCe8qhhM7nyw 677o2D8cSubxY95u1iIcqeiI9qJyrs5eyXgQ8YSEu8PqxpQuTTx90W5weOH1/OronZd1 TV4uyDuscPlvCfZjJG7PxgMDiLqmvOQKxXzJrxkrJJF0n7Fpo1BV8wQNgHQ8YDEZlfpl ioQsgb96/D7eZ4Us8mE5BT1U2kcg6BLUegogRFHbwfuveUJYLSzfnBzLNDsQjOyKVKAe d6rw== X-Gm-Message-State: AODbwcAevf5hTNO6U+wtpHY9uR+w0sjHwKb+eS5ewSQ1i25Y6LMbjxJK ktv44l1Ud25sVTMFhA9lJI7bEcXVMA== X-Received: by 10.31.92.148 with SMTP id q142mr4286855vkb.99.1494935436925; Tue, 16 May 2017 04:50:36 -0700 (PDT) MIME-Version: 1.0 Sender: julienpauli@gmail.com Received: by 10.159.58.77 with HTTP; Tue, 16 May 2017 04:49:56 -0700 (PDT) In-Reply-To: References: Date: Tue, 16 May 2017 13:49:56 +0200 X-Google-Sender-Auth: RbQBeEcaYEVnYmmSVieRgHhl-b4 Message-ID: To: Sara Golemon Cc: Pawel Por , PHP internals Content-Type: multipart/alternative; boundary="001a114e25a2ae1ff7054fa2c739" Subject: Re: [PHP-DEV] Hashtable collision resolution in PHP 7 From: jpauli@php.net (Julien Pauli) --001a114e25a2ae1ff7054fa2c739 Content-Type: text/plain; charset="UTF-8" On Tue, May 16, 2017 at 12:00 PM, Sara Golemon wrote: > https://nikic.github.io/2014/12/22/PHPs-new-hashtable-implementation.html > > On Tue, May 16, 2017 at 4:28 AM, Pawel Por 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. --001a114e25a2ae1ff7054fa2c739--