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 19:21:52 +0530 Message-ID: References: <1b07c68a-873e-83c8-246d-423bc83a3881@gmail.com> <712df469-190d-aeab-e239-1f225be3333f@gmail.com> <25a6003d-1d9b-381f-29b0-aece30af1def@gmail.com> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 X-Trace: blaine.gmane.org 1486734773 5494 195.159.176.226 (10 Feb 2017 13:52:53 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Fri, 10 Feb 2017 13:52:53 +0000 (UTC) Cc: "emacs-devel@gnu.org" To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri Feb 10 14:52:47 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 1ccBd0-00018X-W0 for ged-emacs-devel@m.gmane.org; Fri, 10 Feb 2017 14:52:47 +0100 Original-Received: from localhost ([::1]:43966 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ccBd6-0003gN-NQ for ged-emacs-devel@m.gmane.org; Fri, 10 Feb 2017 08:52:52 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:55873) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ccBcU-0003g6-Ri for emacs-devel@gnu.org; Fri, 10 Feb 2017 08:52:15 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ccBcT-0004OV-Vz for emacs-devel@gnu.org; Fri, 10 Feb 2017 08:52:14 -0500 Original-Received: from mail-yb0-x243.google.com ([2607:f8b0:4002:c09::243]:34097) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1ccBcT-0004OL-Q5 for emacs-devel@gnu.org; Fri, 10 Feb 2017 08:52:13 -0500 Original-Received: by mail-yb0-x243.google.com with SMTP id w194so1383313ybe.1 for ; Fri, 10 Feb 2017 05:52: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=YhDapAeFoyVMkqe+9H5fBxAm6tQhb7+eWDv3JCud5zU=; b=iXKELnEIIPLLUlylhHz94oOLOkfEe7Wzg/L62IuMMrjLVi99lP3TZu70ZH9pPdRkhf xGaP2SBg4l1WcEmcwldSsEkd6VDJjSFrd3PNt5j0O9tvL1Yxb28/bx1DmC2X8w/yiBxe olr//G6FNUc6V6wPIdFVAdLehk0SzpSNThUQ1Uh7BkcA+R7ooFHbzQ003022D+nekGO6 b/Q2/VfdQxAXqFs1oh/vQJpwFc4Kgp6GObgFAQvkBTJCKO9suF3fd8x9OXjO0WDlQRbG K7HG9vkZlR6fli92TeHTADwK2UfiSWjDEozwV79u97PsziXxwdE0A1BA/QBKUzR4NNPg Pemw== 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=YhDapAeFoyVMkqe+9H5fBxAm6tQhb7+eWDv3JCud5zU=; b=SBfEHz8Boe4G6ZxI60v43aT7YFuUOGOs1BezWQz72oPA+i8P0wZz6lkSxRZ/CRO4Y7 Rh3biMP5e/ja95YM2qa3E/cM7cwZPySQwyrjR78UTb+6jaLbEVFJfcqwhCKsurFNJlX+ sX49x2XU7ltnX8HqnNd9v2pm1y6t16EFrm/weYX21vjX0st95R8lXc++eRJHLMA7TkAq 0hcXMP2UkpN3rXFBEqiCfY4zytEssULHxch/FQlEJXq/9lcFIuj4UoKF/i1JlPF9qpPQ X3mIuhBKGF18jIqNS/GVtANPd9c9weZRf1Z42fGqxnKZoARLVoT0aQBpwDEbft9Mq0LU I5gQ== X-Gm-Message-State: AMke39k4kYsEhciAcHOA7y6ZeDs1YulEUcnbtEWNTnXBUPEdY/toJP9njC5M7Go7LKLnxk5EyW04fy34F1d8pg== X-Received: by 10.37.50.73 with SMTP id y70mr6464376yby.63.1486734732964; Fri, 10 Feb 2017 05:52:12 -0800 (PST) Original-Received: by 10.129.153.77 with HTTP; Fri, 10 Feb 2017 05:51:52 -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:4002:c09::243 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:212206 Archived-At: On Fri, Feb 10, 2017 at 11:37 AM, Stefan Monnier wrote: >> 1. For jump tables, HASH_TABLE_SIZE (h) == h->count, so using h->count >> directly saves the cost of an array lookup. > > That doesn't invalidate the usefulness of a linear search. Sure, but that makes it better (IMO) to have separate code for linear searching the jump table. > >> 2. Since the size equals the count, we don't need to check whether >> HASH_HASH (h, i) (the hash code) is non nil in every pass of the >> linear search loop (maphash needs to do this, before calling the >> providing function). > > The linear search should compare HASH_HASH(h, i) to the search key's > hash anyway, so this comparison against nil is not needed. Is that strictly needed, though? In the case of jump tables, there is no extra space reserved in h->key_and_value for more keys to be stored, so the vector looks like `[:group 14 :version 20 :package-version 25 :link 30 :load 35 :tag 40 :set-after 46]` (the jump table for (custom-handle-keyword)). IIUC, this negates the need for comparing HASH_HASH (h, i), as our linear search code is effectively for i from 0 to h->count if h->key_and_value [2*i] == key_needed // HASH_KEY, the value we're comparing against return h->key_and_value[2*i + 1]; // HASH_VALUE, the address switch is to jump to Having said that, I think `gethash` should have it's own linear search code, with all the checks you mentioned. -- Vibhav Pant vibhavp@gmail.com