From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Eli Zaretskii Newsgroups: gmane.emacs.bugs Subject: bug#65491: [PATCH] Improve performance allocating vectors Date: Sat, 26 Aug 2023 10:14:28 +0300 Message-ID: <83bkeumg17.fsf@gnu.org> References: <87y1i0iwvu.fsf@localhost> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="32024"; mail-complaints-to="usenet@ciao.gmane.io" Cc: 65491@debbugs.gnu.org To: Ihor Radchenko , Stefan Monnier Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Sat Aug 26 09:15:11 2023 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 1qZnVl-00084p-NZ for geb-bug-gnu-emacs@m.gmane-mx.org; Sat, 26 Aug 2023 09:15:09 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1qZnVb-0002hC-Id; Sat, 26 Aug 2023 03:14:59 -0400 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 1qZnVZ-0002gy-Jt for bug-gnu-emacs@gnu.org; Sat, 26 Aug 2023 03:14:57 -0400 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 1qZnVZ-00059y-8I for bug-gnu-emacs@gnu.org; Sat, 26 Aug 2023 03:14:57 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1qZnVe-0002lp-1n for bug-gnu-emacs@gnu.org; Sat, 26 Aug 2023 03:15:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Eli Zaretskii Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sat, 26 Aug 2023 07:15:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 65491 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch Original-Received: via spool by 65491-submit@debbugs.gnu.org id=B65491.169303405510576 (code B ref 65491); Sat, 26 Aug 2023 07:15:02 +0000 Original-Received: (at 65491) by debbugs.gnu.org; 26 Aug 2023 07:14:15 +0000 Original-Received: from localhost ([127.0.0.1]:41622 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1qZnUt-0002kV-4c for submit@debbugs.gnu.org; Sat, 26 Aug 2023 03:14:15 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:40374) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1qZnUp-0002kG-Az for 65491@debbugs.gnu.org; Sat, 26 Aug 2023 03:14:13 -0400 Original-Received: from fencepost.gnu.org ([2001:470:142:3::e]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1qZnUe-000564-0y; Sat, 26 Aug 2023 03:14:00 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org; s=fencepost-gnu-org; h=MIME-version:References:Subject:In-Reply-To:To:From: Date; bh=aSPkoQSdPSeLxS2o9w5A3ewQn7Er8B2/f6z/fqtFf9w=; b=U/JfocdYoPtbX+op+T0I r6j1ntueQFV2MGT9cWWKgJmfdQCEPCyrz1L/WNjDPYK5QSWGsyfD9aj63+f4iYUg9UMjhEvbmmR89 wbCF3LdKuXIrXn0qwrbnfp3XabZZdIsqiDDkVGnGFMhsF2wShD6dAjS2cTGW9tHHxlpm3iOz8FOBg 2H1Wt78KdLTSX7KJ+QAHHzZs4DO82UJy4jeU+wlPQv6BUCeumfzRm+8ATmLjecbpT+R5xMKsdD+C9 486zWYxH0posXjZazO8hbMH3mENCnX0szj8thzoyHEb6bHq/5A7Hy/7lLDTQQX3vQWHSwXcWdXQFR QNw90HP1jKA4vw==; In-Reply-To: <87y1i0iwvu.fsf@localhost> (message from Ihor Radchenko on Thu, 24 Aug 2023 09:59:33 +0000) 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:268473 Archived-At: > From: Ihor Radchenko > Date: Thu, 24 Aug 2023 09:59:33 +0000 > > Following up the bignum performance discussion in > https://yhetil.org/emacs-devel/87bkfdsmde.fsf@localhost > > This patch adds a heuristic that reduces the time spent searching > `vector_free_lists' when trying to allocate a new vector. > > `vector_free_lists' is a rather long array with few hundreds of > elements. And it does not make sense to check the whole array in > `allocate_vector_from_block' if we can get information about free vector > that was recently made available of if we know for sure that no free > vectors are available (after GC). > > In the patch, we start searching `vector_free_lists' no earlier than the > last known index of the available free vector, or skip the search > entirely when there is known index (after sweep). > > The described approach may sometimes miss free vectors in > `vector_free_lists', especially if the allocation happens from larger > vector to smaller. The cost will be slightly higher memory consumption - > no larger than VECTOR_MAX_FREE_LIST_INDEX extra free vectors. > > With the patch, CPU time spent allocating new vectors in the fib.eln > test from https://yhetil.org/emacs-devel/87bkfdsmde.fsf@localhost drops 10x. > > Also, the patch gives a noticeable improvement when running > elisp-benchmarks (ELPA package). The overall speedup is around 10% > (including unaffected tests). > > No single test gets worse within error margins and the following tests > get a significant speedup: > > - eieio 1.32±0.04 -> 1.04±0.03 > - pack-unpack 0.40±0.00 -> 0.35±0.01 > - pidigits 6.00±0.06 -> 4.08±0.12 > > pidigits is no surprise as it likely uses bignums. > > * Results without the patch > > | test | non-gc avg (s) | gc avg (s) | gcs avg | tot avg (s) | tot avg err (s) | > |--------------------+----------------+------------+---------+-------------+-----------------| > | bubble | 0.68 | 0.06 | 1 | 0.73 | 0.05 | > | bubble-no-cons | 1.17 | 0.00 | 0 | 1.17 | 0.07 | > | bytecomp | 1.64 | 0.32 | 13 | 1.95 | 0.03 | > | dhrystone | 2.13 | 0.00 | 0 | 2.13 | 0.02 | > | eieio | 1.19 | 0.13 | 7 | 1.32 | 0.04 | > | fibn | 0.00 | 0.00 | 0 | 0.00 | 0.00 | > | fibn-named-let | 1.47 | 0.00 | 0 | 1.47 | 0.04 | > | fibn-rec | 0.00 | 0.00 | 0 | 0.00 | 0.00 | > | fibn-tc | 0.00 | 0.00 | 0 | 0.00 | 0.00 | > | flet | 1.41 | 0.00 | 0 | 1.41 | 0.03 | > | inclist | 0.84 | 0.00 | 0 | 0.84 | 0.03 | > | inclist-type-hints | 0.76 | 0.00 | 0 | 0.76 | 0.00 | > | listlen-tc | 0.12 | 0.00 | 0 | 0.12 | 0.01 | > | map-closure | 5.25 | 0.00 | 0 | 5.25 | 0.02 | > | nbody | 1.47 | 0.15 | 1 | 1.62 | 0.07 | > | pack-unpack | 0.38 | 0.02 | 1 | 0.40 | 0.00 | > | pack-unpack-old | 1.13 | 0.05 | 3 | 1.19 | 0.03 | > | pcase | 1.77 | 0.00 | 0 | 1.77 | 0.01 | > | pidigits | 5.04 | 0.97 | 17 | 6.00 | 0.06 | > | scroll | 0.58 | 0.00 | 0 | 0.58 | 0.02 | > | smie | 1.47 | 0.05 | 2 | 1.52 | 0.02 | > |--------------------+----------------+------------+---------+-------------+-----------------| > | total | 28.49 | 1.74 | 45 | 30.23 | 0.16 | > > * Results with the patch > > | test | non-gc avg (s) | gc avg (s) | gcs avg | tot avg (s) | tot avg err (s) | > |--------------------+----------------+------------+---------+-------------+-----------------| > | bubble | 0.69 | 0.05 | 1 | 0.74 | 0.07 | > | bubble-no-cons | 1.03 | 0.00 | 0 | 1.03 | 0.02 | > | bytecomp | 1.45 | 0.25 | 13 | 1.70 | 0.10 | > | dhrystone | 1.98 | 0.00 | 0 | 1.98 | 0.05 | > | eieio | 0.92 | 0.12 | 7 | 1.04 | 0.03 | > | fibn | 0.00 | 0.00 | 0 | 0.00 | 0.00 | > | fibn-named-let | 1.45 | 0.00 | 0 | 1.45 | 0.12 | > | fibn-rec | 0.00 | 0.00 | 0 | 0.00 | 0.00 | > | fibn-tc | 0.00 | 0.00 | 0 | 0.00 | 0.00 | > | flet | 1.39 | 0.00 | 0 | 1.39 | 0.07 | > | inclist | 0.83 | 0.00 | 0 | 0.83 | 0.03 | > | inclist-type-hints | 0.77 | 0.00 | 0 | 0.77 | 0.03 | > | listlen-tc | 0.10 | 0.00 | 0 | 0.10 | 0.00 | > | map-closure | 5.25 | 0.00 | 0 | 5.25 | 0.37 | > | nbody | 1.45 | 0.16 | 1 | 1.60 | 0.05 | > | pack-unpack | 0.33 | 0.02 | 1 | 0.35 | 0.01 | > | pack-unpack-old | 1.07 | 0.06 | 3 | 1.13 | 0.08 | > | pcase | 1.78 | 0.00 | 0 | 1.78 | 0.05 | > | pidigits | 3.15 | 0.92 | 17 | 4.08 | 0.12 | > | scroll | 0.55 | 0.00 | 0 | 0.55 | 0.01 | > | smie | 1.45 | 0.04 | 2 | 1.49 | 0.06 | > |--------------------+----------------+------------+---------+-------------+-----------------| > | total | 25.63 | 1.62 | 45 | 27.25 | 0.45 | > Stefan, any comments? my comment is that the savings are quite small, so it seems, so I'm not sure we should install this.