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: Tue, 7 Feb 2017 10:56:49 -0500 Message-ID: <1b07c68a-873e-83c8-246d-423bc83a3881@gmail.com> References: NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="------------143A7F3D7ADE1B39DFD9B286" X-Trace: blaine.gmane.org 1486484508 31665 195.159.176.226 (7 Feb 2017 16:21:48 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Tue, 7 Feb 2017 16:21:48 +0000 (UTC) User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.7.0 Cc: "emacs-devel@gnu.org" To: Vibhav Pant , Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Tue Feb 07 17:21:42 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 1cb8WT-0007sP-UK for ged-emacs-devel@m.gmane.org; Tue, 07 Feb 2017 17:21:42 +0100 Original-Received: from localhost ([::1]:55170 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cb8WV-0004iO-PJ for ged-emacs-devel@m.gmane.org; Tue, 07 Feb 2017 11:21:43 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:45122) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cb88V-0000qn-SO for emacs-devel@gnu.org; Tue, 07 Feb 2017 10:56:57 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1cb88R-0004zH-Qd for emacs-devel@gnu.org; Tue, 07 Feb 2017 10:56:56 -0500 Original-Received: from mail-qk0-x244.google.com ([2607:f8b0:400d:c09::244]:33460) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1cb88R-0004yo-ME for emacs-devel@gnu.org; Tue, 07 Feb 2017 10:56:51 -0500 Original-Received: by mail-qk0-x244.google.com with SMTP id 11so13755788qkl.0 for ; Tue, 07 Feb 2017 07:56:51 -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; bh=zrvhwdTqH+tpN99k3dmt06fQSEtae6P86p1dD9BUfpc=; b=vJKZOeOfOsuVJl1Ksk2K6gcxt2muzIOYFCXUlz+djgKyHgvILltvPwJ/Z/cDWldvOx k8sjrJ5chVEMsusP7mDTi9MI6jLBElsdGabO2o1DXMe5VQjPjV8TH5tqLwf74fB6ebrm hq8Mk4blvoXptcJwD2nPftOyflSis1AqyMfslI7baRRBs/FSujn0R3dW3fgP3k+U6fFJ /9VyPx4j1UlQyO7LqwnlMPn+UaEPVHZ9uXgcgRP+xNsciPdZhCdIflo2gA6ZJ8G/zDHh j0HSHxKGmOEL+Foc+mhoiG+jCLp8uK+GQt3ap+bskZeN0Q7Rf/GK4TMlmqj+oajZCPL2 wMdQ== 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; bh=zrvhwdTqH+tpN99k3dmt06fQSEtae6P86p1dD9BUfpc=; b=UxPq1XZEyzPB88gOApq0i9ncvkPOf8tB496kVUt4WaZ7oGCTq2GZ4Jt1PX/D9i2NWM jUTU8n1y2Oy6IZq1cZjGrwH1jn83yny/rVf5poAc7KfGo/IkxrTOIqxdfPPU6xbez010 /vwAI3bVn0UbNjV841mOjZOLRfAzHuB4SFYdqlxE7/swh55CQZ60PaddEbwczURIuNvx +iHswZE+QJXbk6U+/l6oC/3m7cA2aUMbs0NVLueRczWajVpJ+aeprbonrvbmgRBa4bOu 427KGQu7XJMmTEQ++YD0VWzkD7Qyt6H4JjUfQMiFZkkE1/KVDV+5RDCYfYc/U3OdjYJT i3ew== X-Gm-Message-State: AMke39m8S/S6QTq/OAMh31F2poEVR+0M1knu5Da1kOw3nY/xcv/TRDa1nAQH7Id7l1Hg8w== X-Received: by 10.55.15.28 with SMTP id z28mr16423789qkg.105.1486483011041; Tue, 07 Feb 2017 07:56:51 -0800 (PST) Original-Received: from [18.189.127.106] (dhcp-18-189-127-106.dyn.MIT.EDU. [18.189.127.106]) by smtp.gmail.com with ESMTPSA id t2sm3672386qte.14.2017.02.07.07.56.50 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 07 Feb 2017 07:56:50 -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::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:212103 Archived-At: This is a multi-part message in MIME format. --------------143A7F3D7ADE1B39DFD9B286 Content-Type: text/plain; charset=windows-1252 Content-Transfer-Encoding: 8bit On 2017-02-07 08:50, Vibhav Pant wrote: > On Tue, Feb 7, 2017 at 12:00 AM, Stefan Monnier > wrote: >>> The following patch adds support for a new op `switch` to the Emacs >>> bytecode VM and compiler. >> >> I guess the motivation is to speed up some code. >> Did you make any measurements to see what kind of effect it has? > > The attached benchmark code took 9.409541956 seconds when compiled > without switch, > and 0.20807168799999998 seconds (97% speedup) when compiled with switch. It > generates a cond clause with a thousand clauses comparing a variable > with random integer values, with the last clause containing the actual > value. However, > since it's a synthetic benchmark, real world code should be better indicator of > performance improvement. I've attached another benchmark, which evaluates arithmetic expressions. On this, byte-switch seems to be a bit slower: $ rm -f *.elc; emacs-byte-switch -Q --batch --eval '(byte-compile-file "eval-expr.el")'; time emacs-byte-switch -Q --batch -L . -l benchmark-expr.el real 0m4.193s user 0m4.188s sys 0m0.000s $ rm -f *.elc; emacs-master -Q --batch --eval '(byte-compile-file "eval-expr.el")'; time emacs-master -Q --batch -L . -l benchmark-expr.el real 0m3.956s user 0m3.944s sys 0m0.008s 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 :) Thanks for your work on this! Cheers, Clément. --------------143A7F3D7ADE1B39DFD9B286 Content-Type: text/x-emacs-lisp; name="benchmark-expr.el" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="benchmark-expr.el" (require 'eval-expr) (~/init-exprs) (dotimes (_ 20) (~/benchmark)) --------------143A7F3D7ADE1B39DFD9B286 Content-Type: text/x-emacs-lisp; name="eval-expr.el" Content-Transfer-Encoding: 8bit Content-Disposition: attachment; filename="eval-expr.el" ;;; eval-expr.el --- Simple eval-expruation benchmark for byte-switch -*- lexical-binding: t; -*- ;; Copyright (C) 2017 Clément Pit-Claudel ;; Author: Clément Pit-Claudel ;; This program is free software; you can redistribute it and/or modify ;; it under the terms of the GNU General Public License as published by ;; the Free Software Foundation, either version 3 of the License, or ;; (at your option) any later version. ;; This program is distributed in the hope that it will be useful, ;; but WITHOUT ANY WARRANTY; without even the implied warranty of ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ;; GNU General Public License for more details. ;; You should have received a copy of the GNU General Public License ;; along with this program. If not, see . ;;; Commentary: ;;; Code: (require 'cl-lib) (defun ~/eval-expr (expr context) "Eval EXPR in CONTEXT." (pcase expr (`(const ,c) c) (`(var ,x) (alist-get x context)) (`(unop ,op ,expr) (let ((res (~/eval-expr expr context))) (pcase op (`+ res) (`- (- res)) (`! (lognot res))))) (`(binop ,op ,l ,r) (let ((lres (~/eval-expr l context)) (rres (~/eval-expr r context))) (pcase op (`+ (+ lres rres)) (`- (- lres rres)) (`* (* lres rres))))))) (defun ~/size (expr) "Compute the size of EXPR." (pcase expr ((or `(const ,_) `(var ,_)) 1) (`(unop ,_ ,expr) (1+ (~/size expr))) (`(binop ,_ ,l ,r) (+ 1 (~/size l) (~/size r))))) (defun ~/mkexpr-1 (const-t var-t unop-t binop-t vars max-depth) (cl-decf max-depth) (let ((rnd (random binop-t))) (cond ((or (< rnd const-t) (= max-depth 0)) `(const ,(random 1000))) ((< rnd var-t) `(var ,(aref vars (random (length vars))))) ((< rnd unop-t) `(unop ,(aref [+ - !] (random 3)) ,(~/mkexpr-1 const-t var-t unop-t binop-t vars max-depth))) ((< rnd binop-t) `(binop ,(aref [+ - *] (random 3)) ,(~/mkexpr-1 const-t var-t unop-t binop-t vars max-depth) ,(~/mkexpr-1 const-t var-t unop-t binop-t vars max-depth)))))) (defun ~/mkexpr (const-p var-p unop-p binop-p vars max-depth) (let* ((const-t const-p) (var-t (+ const-t var-p)) (unop-t (+ var-t unop-p)) (binop-t (+ unop-t binop-p))) (~/mkexpr-1 const-t var-t unop-t binop-t vars max-depth))) (defvar ~/exprs nil) (defun ~/init-exprs () (setq ~/exprs nil) (dotimes (_ 5000) (push (~/mkexpr 1 1 2 4 [a b c] 15) ~/exprs))) (defun ~/benchmark () (apply #'+ (mapcar #'~/size ~/exprs)) (mapc (lambda (e) (~/eval-expr e '((a . 1) (b . 2) (c . 3)))) ~/exprs)) (provide 'eval-expr) ;;; eval-expr.el ends here --------------143A7F3D7ADE1B39DFD9B286--