From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= Newsgroups: gmane.emacs.bugs Subject: bug#68244: hash-table improvements Date: Fri, 5 Jan 2024 12:34:50 +0100 Message-ID: References: <83r0ixvys9.fsf@gnu.org> <4FC7642E-BAAF-40E3-AADC-0485AB085D6D@gmail.com> <83o7e1vvpp.fsf@gnu.org> Mime-Version: 1.0 (Mac OS X Mail 14.0 \(3654.120.0.1.15\)) Content-Type: multipart/mixed; boundary="Apple-Mail=_FED6533D-D349-44F8-BB29-7F1FA5CBD54D" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="16747"; mail-complaints-to="usenet@ciao.gmane.io" Cc: Dmitry Gutov , 68244@debbugs.gnu.org, Stefan Monnier To: Eli Zaretskii Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Fri Jan 05 12:36:18 2024 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1rLiUr-00045c-Hf for geb-bug-gnu-emacs@m.gmane-mx.org; Fri, 05 Jan 2024 12:36:17 +0100 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1rLiUZ-0005KZ-GF; Fri, 05 Jan 2024 06:35:59 -0500 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1rLiUY-0005KR-IP for bug-gnu-emacs@gnu.org; Fri, 05 Jan 2024 06:35:58 -0500 Original-Received: from debbugs.gnu.org ([2001:470:142:5::43]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1rLiUY-0005r6-9n for bug-gnu-emacs@gnu.org; Fri, 05 Jan 2024 06:35:58 -0500 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1rLiUc-0002iU-HI for bug-gnu-emacs@gnu.org; Fri, 05 Jan 2024 06:36:02 -0500 X-Loop: help-debbugs@gnu.org Resent-From: Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Fri, 05 Jan 2024 11:36:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 68244 X-GNU-PR-Package: emacs Original-Received: via spool by 68244-submit@debbugs.gnu.org id=B68244.170445450710365 (code B ref 68244); Fri, 05 Jan 2024 11:36:02 +0000 Original-Received: (at 68244) by debbugs.gnu.org; 5 Jan 2024 11:35:07 +0000 Original-Received: from localhost ([127.0.0.1]:56545 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1rLiTi-0002h7-QQ for submit@debbugs.gnu.org; Fri, 05 Jan 2024 06:35:07 -0500 Original-Received: from mail-lf1-x12a.google.com ([2a00:1450:4864:20::12a]:53759) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1rLiTg-0002g2-2t for 68244@debbugs.gnu.org; Fri, 05 Jan 2024 06:35:04 -0500 Original-Received: by mail-lf1-x12a.google.com with SMTP id 2adb3069b0e04-50e5a9bcec9so1869398e87.3 for <68244@debbugs.gnu.org>; Fri, 05 Jan 2024 03:34:59 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1704454494; x=1705059294; darn=debbugs.gnu.org; h=references:to:cc:in-reply-to:date:subject:mime-version:message-id :from:sender:from:to:cc:subject:date:message-id:reply-to; bh=VVId328r3mExrCAp5YMvE4xTLC0UXflO6ZN+zx/sbuA=; b=MWrXDJj3/8V2jMqtw2nfS3SEXggXum3OvP4tPF+s5mLAxY7nSSuCtcMqymOtBMyCS8 EhST9QwY7DhaRpaFqQz7HbLjcSJ1TShDhsX1i1WZlI9KLGUmsFjkSQ8wpaHwS9PPSOwq +wThw+eUCkxdkzCnqEFQfBFXKrjMrA56gdruoIn5qDXYRmZeC5V8xh+dDFy78pv4qASi b36lrwYFJvXHc22/xZQc3F3GDLAzreZcUgazt8j+nBCDz/1Zzy6FwnaqxzmTUq9FMWUF cPYvDyN56bD5wyUpgKiJ2atBvQ5xnfbNMZvvFxW9VitTYqizQDnQJg4JQVg/lP7WoabA uChw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1704454494; x=1705059294; h=references:to:cc:in-reply-to:date:subject:mime-version:message-id :from:sender:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=VVId328r3mExrCAp5YMvE4xTLC0UXflO6ZN+zx/sbuA=; b=SXQtgggwbfYWCjWbwr3AihpVQFj+ytevvH2hZvrWcxVaL13Yj9FfWN0qo8kmwppBDK 9eBG5ReoMbwhdfYWHcY5IWd2EZI0Ty4IJ4pgcY4usbF8O0BmyONfTCHDIbTbGXb22AA6 F45qllKH+xtp9ZnH6NWVZlc7RarvAZg6Df9lDQT2jFM8wCZ0Vik+2pWLxzLAsrYphkFT lnQobjmTBJMUQ5fDw705tIc1I6ghYY4ztCe6v/Yx0Y/oXuAA2dIxNyQHowJF6YR+oLzR 3Rtg4mTUgqxLMQ0qY3E4118qKusxmPhI/o0Bd62ZmGRopFXsTk/OG6FQTZCoGr7HOZ8D KWdA== X-Gm-Message-State: AOJu0YzihtVamscXkR5bOUYwWbvLjvcBmWsJhFANjOYG9vUAWTKIEj2b bGex7sy21LsdtjJUHMwjCHduwr0Hp9M= X-Google-Smtp-Source: AGHT+IHt7HmU7L9q/wfWkud0rQMdgB/qSl5Z7AFQgTGrB37T+cVLajgtZdoowim0rxpmEDIPHXgGPQ== X-Received: by 2002:a05:6512:31d4:b0:50e:75fc:35be with SMTP id j20-20020a05651231d400b0050e75fc35bemr1252786lfe.90.1704454493478; Fri, 05 Jan 2024 03:34:53 -0800 (PST) Original-Received: from smtpclient.apple (c80-217-1-132.bredband.tele2.se. [80.217.1.132]) by smtp.gmail.com with ESMTPSA id br9-20020a056512400900b0050eb25b5092sm211710lfb.229.2024.01.05.03.34.51 (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Fri, 05 Jan 2024 03:34:52 -0800 (PST) In-Reply-To: <83o7e1vvpp.fsf@gnu.org> X-Mailer: Apple Mail (2.3654.120.0.1.15) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Original-Sender: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.emacs.bugs:277381 Archived-At: --Apple-Mail=_FED6533D-D349-44F8-BB29-7F1FA5CBD54D Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=us-ascii 4 jan. 2024 kl. 18.45 skrev Eli Zaretskii : > It doesn't have to be a single number. Showing a series of separate > benchmarks is also fine. Unfortunately it's not quite that simple: those numbers have to be = interpreted and understood as well, which requires about as much work as = making the benchmarks in the first place. But let's try anyway: here is a run of one of the main suites I've been = using. The numbers indicate relative changes in percent of elapsed time = from the baseline to the tip of the scratch/hash-table-perf branch, = negative numbers being better. For example, -50 means that speed has = doubled, +100 that it has halved. --Apple-Mail=_FED6533D-D349-44F8-BB29-7F1FA5CBD54D Content-Disposition: attachment; filename=pct.org Content-Type: application/octet-stream; x-unix-mode=0644; name="pct.org" Content-Transfer-Encoding: 7bit | | 681a2877cc2 | |---------------------------+-------------| | make empty | -88.9 | | make 4, dead | -88.8 | | make 16, dead | -62.3 | | make 64, dead | +25.1 | | make 256, dead | -77.7 | | make 1024, dead | -76.7 | | make 4096, dead | -81.4 | | make 100000, dead | -73.2 | |---------------------------+-------------| | make 4, alive | -93.3 | | make 16, alive | -75.6 | | make 64, alive | +11.5 | | make 256, alive | -82.4 | | make 1024, alive | -79.7 | | make 2048, alive | -83.3 | | make 4096, alive | -84.4 | | make 100000, alive | -75.1 | |---------------------------+-------------| | gethash seq 4 | -4.7 | | gethash seq 16 | -5.7 | | gethash seq 64 | -4.9 | | gethash seq 256 | -4.7 | | gethash seq 1024 | -4.7 | | gethash seq 4096 | -4.5 | | gethash seq 100000 | -4.5 | |---------------------------+-------------| | gethash rnd 4 | -5.1 | | gethash rnd 16 | -4.5 | | gethash rnd 64 | -8.9 | | gethash rnd 256 | -3.0 | | gethash rnd 1024 | -4.8 | | gethash rnd 4096 | -1.9 | | gethash rnd 100000 | -6.5 | |---------------------------+-------------| | gethash sym 1059 | -15.2 | |---------------------------+-------------| | gethash 20000 tbls 5 elts | -76.8 | | gethash 5263 tbls 19 elts | -64.0 | | gethash 1538 tbls 65 elts | -21.8 | | gethash 571 tbls 175 elts | -34.6 | |---------------------------+-------------| | insert/remove all 10 | -5.4 | | insert/remove all 100 | -5.7 | | insert/remove all 1000 | -4.7 | | insert/remove all 10000 | -5.1 | | insert/remove all 100000 | -5.5 | |---------------------------+-------------| | insert/remove 10 | +10.2 | | insert/remove 100 | -7.7 | | insert/remove 1000 | -12.4 | | insert/remove 10000 | -5.1 | | insert/remove 100000 | -10.2 | |---------------------------+-------------| | maphash 10 | -6.0 | | maphash 100 | -0.4 | | maphash 1000 | -0.2 | | maphash 10000 | +0.8 | | maphash 100000 | -0.4 | |---------------------------+-------------| | print empty eql | -42.1 | | print empty eq | -39.0 | |---------------------------+-------------| | read empty eql | -96.5 | | read empty eq | -94.9 | | read 100 | -36.0 | | read 10000 | -6.7 | --Apple-Mail=_FED6533D-D349-44F8-BB29-7F1FA5CBD54D Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=us-ascii Again, these are micro-benchmarks designed to amplify the signal in = various respects, and the numbers don't tell everything -- far from it, = in fact. As mentioned before, one of the most important aspects of a data = structure is not just how well it performs itself but how good neighbour = it is: the less memory it uses and the better its locality of reference, = the less negative impact it has on other objects and data structures. = However, these effects can be difficult to measure correctly, so a lot = of the tuning and assessment have to be done by indirect means. --Apple-Mail=_FED6533D-D349-44F8-BB29-7F1FA5CBD54D--