From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Vibhav Pant Newsgroups: gmane.emacs.devel Subject: Re: [PATCH]: Add new bytecode op `switch' for implementing branch tables. Date: Fri, 10 Feb 2017 09:42:11 +0530 Message-ID: References: <1b07c68a-873e-83c8-246d-423bc83a3881@gmail.com> <712df469-190d-aeab-e239-1f225be3333f@gmail.com> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary=001a114e7e885e2d650548254d86 X-Trace: blaine.gmane.org 1486699941 18410 195.159.176.226 (10 Feb 2017 04:12:21 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Fri, 10 Feb 2017 04:12:21 +0000 (UTC) Cc: emacs-devel@gnu.org To: =?UTF-8?Q?Cl=C3=A9ment_Pit=2DClaudel?= Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri Feb 10 05:12:17 2017 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1cc2ZE-0004M9-V8 for ged-emacs-devel@m.gmane.org; Fri, 10 Feb 2017 05:12:17 +0100 Original-Received: from localhost ([::1]:41651 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cc2ZI-0003Ym-Ta for ged-emacs-devel@m.gmane.org; Thu, 09 Feb 2017 23:12:20 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:54198) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cc2ZC-0003YV-8L for emacs-devel@gnu.org; Thu, 09 Feb 2017 23:12:15 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1cc2ZB-0005ua-7a for emacs-devel@gnu.org; Thu, 09 Feb 2017 23:12:14 -0500 Original-Received: from mail-yw0-x244.google.com ([2607:f8b0:4002:c05::244]:34575) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1cc2ZB-0005uM-33 for emacs-devel@gnu.org; Thu, 09 Feb 2017 23:12:13 -0500 Original-Received: by mail-yw0-x244.google.com with SMTP id v73so1793105ywg.1 for ; Thu, 09 Feb 2017 20:12:13 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=zbg7qvolHJ9OySc6yCBdIN5yKwuWYU7CdL8V8xZZ9hk=; b=DWd4FoDLWH6SNg210T7IwodDvHNfQ7uOyS1jxBjiKzhrI8OtvsD8Y3+qPNEN9hh9oo hOJNcllz7BT0wAhwdG1x+8OOvvrdWTefLU98U087fb1dL2e/TaTw3f/6fOoOaefnyxTp /A1wqFm31HCF6QJAR2Gad3MAtn8B3nQWt9UuxtFHTVw86ws4ALSm7XWhYc/aprh2Wpkm g8PoMwwbsNNjYlxMtppZn+/swT6p2dUgLHcA1I5jVQuJLvUWCs9IsbYjdQkymfRK7yzn sFZqWX9z3leIkkObNuyMUODY4m4hW3k02PffAi4yFJD8tV5t/9M4FRnAci5ex1H3hKps D8JQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=zbg7qvolHJ9OySc6yCBdIN5yKwuWYU7CdL8V8xZZ9hk=; b=XBrTqjYuSf7SlbzJ++ITpTYkIVSbA2kFmI+hjRhBHFAf29cZ+SqrbEBNrU//c8Lqjw K39IpBrSHiIcD2iY8Qjg6IcZ461ObTNXkFh52AXr4JCg5ecXzYRRJENSK8cSEX9x3+Fo l70uTYjtTYPBK4W9bXxbtcphqlFzgfnEpnVZFK+aZy0900MJJT8t9JZCFkzDfw2/CJVO DnnSvzEDp31XPwtKFncRLVZq5oP5hQe91nyjDSblze8ydyh/yUhEm/GYUNi/WKwsi0l0 ugX8uvE8nw531Ydn9vNgLDHy+8rTUQZPaS8BdbNkAICfnMx+kkgtRhCXGPvR0hSqQ2Qc aTmQ== X-Gm-Message-State: AMke39moSuazQoy4NUVrRMHoN6lJLkwbr4HN1hMmoBlHYjgiLOm1Qbwu5VjyRfc5s3eqxKkze86XAaTrO8D/pg== X-Received: by 10.13.208.132 with SMTP id s126mr4927829ywd.137.1486699932558; Thu, 09 Feb 2017 20:12:12 -0800 (PST) Original-Received: by 10.129.153.77 with HTTP; Thu, 9 Feb 2017 20:12:11 -0800 (PST) Original-Received: by 10.129.153.77 with HTTP; Thu, 9 Feb 2017 20:12:11 -0800 (PST) In-Reply-To: <712df469-190d-aeab-e239-1f225be3333f@gmail.com> X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 2607:f8b0:4002:c05::244 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.org gmane.emacs.devel:212192 Archived-At: --001a114e7e885e2d650548254d86 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable The linear search code has been shifted to bytecode.c, since there are a couple of assumptions about the jump table that we can't make for a regular hash table, so regular gethash shouldn't be affected. Vibhav Pant vibhavp@gmail.com On 10-Feb-2017 12:45 AM, "Cl=C3=A9ment Pit-Claudel" wrote: > On 2017-02-08 08:38, Vibhav Pant wrote: > > On Tue, Feb 7, 2017 at 9:26 PM, Cl=C3=A9ment Pit-Claudel > > wrote: > >> The timings fluctuate quite a bit, but the byte-switch branch seems to > be about 5-7% slower. Hopefully linear-scan hash tables will make things > much faster :) > > > > The following patch makes hash_lookup use linear search when the number > of keys > > in the hash table is <=3D 5 (chosen arbitrarily). switch bytecode run w= ith > this > > patch takes 15.96 seconds to run the benchmark, while the goto-if-nil > code takes > > 17.15 seconds. > > Here's another test that your patch seems to improve a bit: > > (defvar ~/maps nil) > > (dotimes (n 50) > (let ((map (make-hash-table :test #'eq))) > (dotimes (k 2) > (puthash k n map)) > (push map ~/maps))) > > (benchmark-run-compiled 1000000 > (dolist (mp ~/maps) > (gethash 1 mp))) > > Are linear scans used on all small hash tables, then? > > Cl=C3=A9ment. > > --001a114e7e885e2d650548254d86 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
The linear search code has been shifted to bytecode.c, si= nce there are a couple of assumptions about the jump table that we can'= t make for a regular hash table, so regular gethash shouldn't be affect= ed.

=

On 10-Feb-2= 017 12:45 AM, "Cl=C3=A9ment Pit-Claudel" <cpitclaudel@gmail.com> wrote:=
On 2017-02-08 08:38= , Vibhav Pant wrote:
> On Tue, Feb 7, 2017 at 9:26 PM, Cl=C3=A9ment Pit-Claudel
> <cpitclaudel@gmail.com= > wrote:
>> The timings fluctuate quite a bit, but the byte-switch branch seem= s to be about 5-7% slower.=C2=A0 Hopefully linear-scan hash tables will mak= e things much faster :)
>
> The following patch makes hash_lookup use linear search when the numbe= r of keys
> in the hash table is <=3D 5 (chosen arbitrarily). switch bytecode r= un with this
> patch takes 15.96 seconds to run the benchmark, while the goto-if-nil = code takes
> 17.15 seconds.

Here's another test that your patch seems to improve a bit:

(defvar ~/maps nil)

(dotimes (n 50)
=C2=A0 (let ((map (make-hash-table :test #'eq)))
=C2=A0 =C2=A0 (dotimes (k 2)
=C2=A0 =C2=A0 =C2=A0 (puthash k n map))
=C2=A0 =C2=A0 (push map ~/maps)))

(benchmark-run-compiled 1000000
=C2=A0 (dolist (mp ~/maps)
=C2=A0 =C2=A0 (gethash 1 mp)))

Are linear scans used on all small hash tables, then?

Cl=C3=A9ment.

--001a114e7e885e2d650548254d86--