From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: =?UTF-8?Q?Cl=c3=a9ment_Pit-Claudel?= Newsgroups: gmane.emacs.devel Subject: Re: [PATCH]: Add new bytecode op `switch' for implementing branch tables. Date: Thu, 9 Feb 2017 14:15:35 -0500 Message-ID: <712df469-190d-aeab-e239-1f225be3333f@gmail.com> References: <1b07c68a-873e-83c8-246d-423bc83a3881@gmail.com> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=windows-1252 Content-Transfer-Encoding: 8bit X-Trace: blaine.gmane.org 1486667777 8575 195.159.176.226 (9 Feb 2017 19:16:17 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Thu, 9 Feb 2017 19:16:17 +0000 (UTC) User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.7.0 Cc: Stefan Monnier , "emacs-devel@gnu.org" To: Vibhav Pant Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Thu Feb 09 20:16:12 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 1cbuCP-0001tB-6b for ged-emacs-devel@m.gmane.org; Thu, 09 Feb 2017 20:16:09 +0100 Original-Received: from localhost ([::1]:39835 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cbuCU-0001Bw-NA for ged-emacs-devel@m.gmane.org; Thu, 09 Feb 2017 14:16:14 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:45469) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cbuBw-0001BZ-Pt for emacs-devel@gnu.org; Thu, 09 Feb 2017 14:15:41 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1cbuBt-00054k-Hq for emacs-devel@gnu.org; Thu, 09 Feb 2017 14:15:40 -0500 Original-Received: from mail-qk0-x242.google.com ([2607:f8b0:400d:c09::242]:34934) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1cbuBt-00054g-AU for emacs-devel@gnu.org; Thu, 09 Feb 2017 14:15:37 -0500 Original-Received: by mail-qk0-x242.google.com with SMTP id u25so2009755qki.2 for ; Thu, 09 Feb 2017 11:15:37 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=subject:to:references:cc:from:message-id:date:user-agent :mime-version:in-reply-to:content-transfer-encoding; bh=swabDOqVgxCRIoPpfGWunhgqoAfC1rFiEi62olsFH5E=; b=NGTrEoYM4v03emsc8rIzr5higHi5RtKG3lbDRdey2MKbejegN6nABYtP2hmSNEqRbi eZ+6HTAwlmO6jvxojJWKtTvnuHYSFlrbeAkLyESlp84SolJX5kpox30ysvmPWWt9Rz2G uzqgS7X9kCFzEjwKVWD/XRd0xQpjUm9dB/E8H9ClmU0vvRcByTS07CgDTzCfHKhn06qF uC+nwGiZjOQAS4jYrtXJE2p1yt2D2iOkCSzbmd72wnDM5xJubUlTBFQZxaMLLQe9c8Kz 8ry+ocDET9Q+7SQa5bx9ioZht0Y0ErU8rnvOUyIbUg0o28ui5pCDgT8CEwvuis6hfOaS 5WfQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:references:cc:from:message-id:date :user-agent:mime-version:in-reply-to:content-transfer-encoding; bh=swabDOqVgxCRIoPpfGWunhgqoAfC1rFiEi62olsFH5E=; b=qteX/cyCzefZhxbONoDRyZB27715LGR0NRuvop0ZNTqN/AmM+zWHNejSiO8cxh3G0p MZ7F5Qtxzj75UJgsFrgfxIOENU3NGoKMB36OrP0Q6wQLGzuBGAoAjid+hVB/Y+eBNfer bDi5s4sqzt0ikCNU2VjEmjVxJ/1GhAOSjPJLP8WIRC2JkR9CQKONC95YMgq/TelGjSTM TENnmdjEsotwjReLmQoZ8Qec+mY9udDDBx0u/8FpHmFHVgNdonJK/3AvqH9Cg5mXfq0n 3pEERiyB4xwwq2AqQPWMjczubIxxZyoPhLHrPyg8yiv0AQnRGYLOCXSrNCeldZsEvCd/ P6hg== X-Gm-Message-State: AMke39kS1oyiTHMAvMge2gV1foHeumID8Za2sJaSaUJ//CRRgy1QW9XUpEOvFZ7M+TXwSQ== X-Received: by 10.55.163.80 with SMTP id m77mr5141360qke.157.1486667736856; Thu, 09 Feb 2017 11:15:36 -0800 (PST) Original-Received: from [18.111.113.197] (dhcp-18-111-113-197.dyn.mit.edu. [18.111.113.197]) by smtp.gmail.com with ESMTPSA id a70sm9957146qkc.1.2017.02.09.11.15.35 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 09 Feb 2017 11:15:36 -0800 (PST) In-Reply-To: X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 2607:f8b0:400d:c09::242 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:212176 Archived-At: On 2017-02-08 08:38, Vibhav Pant wrote: > On Tue, Feb 7, 2017 at 9:26 PM, Clément 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 <= 5 (chosen arbitrarily). switch bytecode run 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) (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ément.