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: Sun, 7 Jan 2024 19:36:17 +0100 Message-ID: References: <170438379722.3921.9312235725296561206@vcs2.savannah.gnu.org> <20240104155642.B4A99C00344@vcs2.savannah.gnu.org> <8d49ebdc-9da7-4e70-a080-d8e892b980b6@gutov.dev> <08314177-5AE9-4352-94A0-641830B4094D@gmail.com> Mime-Version: 1.0 (Mac OS X Mail 14.0 \(3654.120.0.1.15\)) Content-Type: multipart/mixed; boundary="Apple-Mail=_54817F36-7ABD-4580-AB5C-36D0B6990383" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="27980"; mail-complaints-to="usenet@ciao.gmane.io" Cc: Dmitry Gutov , Eli Zaretskii , 68244@debbugs.gnu.org To: Stefan Monnier Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Sun Jan 07 19:37:20 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 1rMY1P-00077g-Cz for geb-bug-gnu-emacs@m.gmane-mx.org; Sun, 07 Jan 2024 19:37:19 +0100 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1rMY14-0006wQ-7N; Sun, 07 Jan 2024 13:36:58 -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 1rMY13-0006w5-DZ for bug-gnu-emacs@gnu.org; Sun, 07 Jan 2024 13:36:57 -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 1rMY13-0003y5-5e for bug-gnu-emacs@gnu.org; Sun, 07 Jan 2024 13:36:57 -0500 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1rMY17-00051n-R6 for bug-gnu-emacs@gnu.org; Sun, 07 Jan 2024 13:37: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: Sun, 07 Jan 2024 18:37:01 +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.170465260119300 (code B ref 68244); Sun, 07 Jan 2024 18:37:01 +0000 Original-Received: (at 68244) by debbugs.gnu.org; 7 Jan 2024 18:36:41 +0000 Original-Received: from localhost ([127.0.0.1]:33827 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1rMY0l-00051D-Cu for submit@debbugs.gnu.org; Sun, 07 Jan 2024 13:36:40 -0500 Original-Received: from mail-lj1-x230.google.com ([2a00:1450:4864:20::230]:58435) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1rMY0c-00050o-Bw for 68244@debbugs.gnu.org; Sun, 07 Jan 2024 13:36:31 -0500 Original-Received: by mail-lj1-x230.google.com with SMTP id 38308e7fff4ca-2cd17a979bcso10223221fa.0 for <68244@debbugs.gnu.org>; Sun, 07 Jan 2024 10:36:24 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1704652578; x=1705257378; 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=AGSyowT3MNQyukwTYTIATk3gfWzvv7fRWJ8qakswixY=; b=VFgSxYT73UJBXKWxtFRju3nZejGn8kEZxFQY0VNGD2PdTabFne07Zdcrz5MepkOAaF 09N2EfZdBXG545P4LGsQstXN/oP2PUA5NDvRilx3V+AKJhZGpZuosfo8CCGgFYD7OQCe 8AVa9uIY7pUPVcfI9qWBPhArODVuCG4g0t+Bs1eiJWl32F7ZKsbDzQ34wSjlC7xHYhcs ZbVaS+b5E2mAPISBlR/RxkFSKznQ82bxMXSHYNf08g7HW3NIKFEy0XxKKvyQyeFfqS/+ FL/VvEwA4ogxD9gLb/6vXs8b+DN7cIkYd+tHm0HP0gGia19V0szNTwLu9//Y8icAA0iK e3qw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1704652578; x=1705257378; 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=AGSyowT3MNQyukwTYTIATk3gfWzvv7fRWJ8qakswixY=; b=npBVPM+Z72XPD0DTaRk2Z1dfEDBXKGRGWj0KNJgnoIMEd97eWgwCmXiHGs+cgDOP5Z GsS/XStjvqPRCxCFGHDUa0sIyPLv+VtPHCmRFKuQT8EAOfaDizMEZQYWouOuHA0t8TmG QGGFlxQGUlpx0QNTugtOoianBcwZEvu1YMR7Q4dv9pfuhrBnC3+0lKneGQKNHaWIrtgh HlOKrAMu6jrojA4h1+QijmMJbW8/MUciEGfkzSsP12iI+67TbEbNijp7VeKhIml3BTXS XsnKQxIbzdnDntI13127C+GWuWyWKPG+JduVXIVWKKLZpi8R/SMJNJ+HfSbjYPMLCzi+ 5Byw== X-Gm-Message-State: AOJu0YwYvz4ohq97Vmjbgpff7x9RuYncbMPRWRdjP3jwrUUDhp0XQODI aFus9doC9bHp2elxmayZNhI= X-Google-Smtp-Source: AGHT+IECbrkSZfJ/ZEdkaazejb4ERGq0af4feQApVwkKVes31NeT+TrYys95oY4yZF/uY+u20EvaVA== X-Received: by 2002:a2e:8397:0:b0:2cd:31b9:b1d4 with SMTP id x23-20020a2e8397000000b002cd31b9b1d4mr443412ljg.54.1704652578424; Sun, 07 Jan 2024 10:36:18 -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 k36-20020a05651c062400b002ccb984d5f8sm1236353lje.7.2024.01.07.10.36.17 (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Sun, 07 Jan 2024 10:36:17 -0800 (PST) In-Reply-To: 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:277521 Archived-At: --Apple-Mail=_54817F36-7ABD-4580-AB5C-36D0B6990383 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=us-ascii 7 jan. 2024 kl. 06.26 skrev Stefan Monnier : > The use of memory allocation as a way to decide when to do the next GC > is just a crude tool anyway, which can often result in bad GC = decisions, > anyway (e.g. typically during long periods of initialization where we > allocate many objects but don't generate almost any garbage). In any case the changes to GC heuristics and policy that have been = proposed aren't specific to hash-tables and while interesting are = outside the scope of my work at hand. This means that I'll keep using = the same kind of bookkeeping as before, so that the GC is reasonably = well informed if we want to change it in the future. I've pushed two new changes: a correction to the GC accounting for the = ancillary hash-table vectors, and a rather more interesting change to = the hash table range reduction. It now uses a Knuth multiplicative = method instead of the expensive remainder, so the index is now always a = power of 2 in size. Benchmark results attached: the first column is the same as before, the = middle after the accounting fix (which turned out not to be noticeable = at all), and the rightmost what we got from Knuth. I'll probably keep = both. --Apple-Mail=_54817F36-7ABD-4580-AB5C-36D0B6990383 Content-Disposition: attachment; filename=pct.org Content-Type: application/octet-stream; x-unix-mode=0644; name="pct.org" Content-Transfer-Encoding: 7bit | | 681a2877 | e366ae38 | b9c9539d | |---------------------------+----------+----------+----------| | make empty | -88.8 | -88.8 | -89.9 | | make 4, dead | -88.8 | -88.9 | -90.0 | | make 16, dead | -62.3 | -62.5 | -70.7 | | make 64, dead | +26.8 | +24.7 | -3.1 | | make 256, dead | -78.4 | -78.0 | -67.7 | | make 1024, dead | -76.7 | -76.7 | -67.0 | | make 4096, dead | -81.4 | -81.4 | -74.6 | | make 100000, dead | -73.2 | -73.3 | -59.0 | |---------------------------+----------+----------+----------| | make 4, alive | -93.3 | -93.3 | -95.4 | | make 16, alive | -75.6 | -75.6 | -82.8 | | make 64, alive | +11.4 | +12.6 | -22.6 | | make 256, alive | -82.4 | -82.4 | -72.5 | | make 1024, alive | -79.7 | -79.7 | -68.1 | | make 2048, alive | -83.3 | -83.7 | -73.3 | | make 4096, alive | -84.4 | -84.4 | -74.7 | | make 100000, alive | -75.3 | -75.3 | -61.2 | |---------------------------+----------+----------+----------| | gethash seq 4 | -4.7 | -4.7 | -11.2 | | gethash seq 16 | -5.7 | -5.7 | -7.6 | | gethash seq 64 | -5.5 | -4.9 | -6.8 | | gethash seq 256 | -5.3 | -4.7 | -6.4 | | gethash seq 1024 | -5.1 | -4.9 | -6.6 | | gethash seq 4096 | -5.1 | -4.5 | -6.6 | | gethash seq 100000 | -5.1 | -4.7 | +5.3 | |---------------------------+----------+----------+----------| | gethash rnd 4 | -5.0 | -5.0 | -8.7 | | gethash rnd 16 | -4.6 | -4.6 | -10.0 | | gethash rnd 64 | -8.9 | -8.9 | -13.6 | | gethash rnd 256 | -3.2 | -3.2 | -10.8 | | gethash rnd 1024 | -4.8 | -4.8 | -13.2 | | gethash rnd 4096 | -2.3 | -2.1 | -12.0 | | gethash rnd 100000 | -4.0 | -6.4 | -17.6 | |---------------------------+----------+----------+----------| | gethash sym 1059 | -15.4 | -15.4 | -18.0 | |---------------------------+----------+----------+----------| | gethash 20000 tbls 5 elts | -76.5 | -77.0 | -77.4 | | gethash 5263 tbls 19 elts | -63.5 | -63.8 | -67.4 | | gethash 1538 tbls 65 elts | -28.8 | -22.8 | -35.5 | | gethash 571 tbls 175 elts | -33.7 | -34.1 | -40.1 | |---------------------------+----------+----------+----------| | insert/remove all 10 | -5.4 | -5.0 | -10.8 | | insert/remove all 100 | -5.9 | -5.9 | -10.1 | | insert/remove all 1000 | -4.9 | -5.1 | -9.1 | | insert/remove all 10000 | -4.9 | -5.1 | -9.5 | | insert/remove all 100000 | -5.5 | -5.5 | +2.2 | |---------------------------+----------+----------+----------| | insert/remove 10 | +10.2 | +10.2 | -5.2 | | insert/remove 100 | -7.7 | -7.7 | -17.5 | | insert/remove 1000 | -12.4 | -12.4 | -16.1 | | insert/remove 10000 | -5.1 | -5.1 | -10.4 | | insert/remove 100000 | -9.9 | -9.9 | -6.9 | |---------------------------+----------+----------+----------| | maphash 10 | -6.1 | -6.0 | -7.1 | | maphash 100 | -0.4 | -0.4 | +0.8 | | maphash 1000 | -0.2 | -0.2 | +0.8 | | maphash 10000 | +0.8 | +0.8 | +0.0 | | maphash 100000 | -0.2 | -0.4 | +1.8 | |---------------------------+----------+----------+----------| | print empty eql | -43.2 | -41.8 | -42.6 | | print empty eq | -39.1 | -38.3 | -38.8 | |---------------------------+----------+----------+----------| | read empty eql | -96.5 | -96.5 | -96.5 | | read empty eq | -94.9 | -94.9 | -94.9 | | read 100 | -36.2 | -36.1 | -36.8 | | read 10000 | -6.8 | -7.0 | -7.8 | --Apple-Mail=_54817F36-7ABD-4580-AB5C-36D0B6990383--