From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Ihor Radchenko Newsgroups: gmane.emacs.bugs Subject: bug#65491: [PATCH] Improve performance allocating vectors Date: Thu, 24 Aug 2023 09:59:33 +0000 Message-ID: <87y1i0iwvu.fsf@localhost> Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="26686"; mail-complaints-to="usenet@ciao.gmane.io" To: 65491@debbugs.gnu.org Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Thu Aug 24 12:00:34 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 1qZ78j-0006jw-6Q for geb-bug-gnu-emacs@m.gmane-mx.org; Thu, 24 Aug 2023 12:00:33 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1qZ78D-0005cR-4z; Thu, 24 Aug 2023 06:00:01 -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 1qZ78B-0005Zx-De for bug-gnu-emacs@gnu.org; Thu, 24 Aug 2023 05:59:59 -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 1qZ78B-0002Uy-5B for bug-gnu-emacs@gnu.org; Thu, 24 Aug 2023 05:59:59 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1qZ78E-0005u0-VB for bug-gnu-emacs@gnu.org; Thu, 24 Aug 2023 06:00:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Ihor Radchenko Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Thu, 24 Aug 2023 10:00:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: report 65491 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch X-Debbugs-Original-To: bug-gnu-emacs@gnu.org Original-Received: via spool by submit@debbugs.gnu.org id=B.169287116722592 (code B ref -1); Thu, 24 Aug 2023 10:00:02 +0000 Original-Received: (at submit) by debbugs.gnu.org; 24 Aug 2023 09:59:27 +0000 Original-Received: from localhost ([127.0.0.1]:36159 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1qZ77e-0005sH-Df for submit@debbugs.gnu.org; Thu, 24 Aug 2023 05:59:27 -0400 Original-Received: from lists.gnu.org ([2001:470:142::17]:45210) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1qZ77Z-0005s0-FR for submit@debbugs.gnu.org; Thu, 24 Aug 2023 05:59:24 -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 1qZ77P-0005Fk-GL for bug-gnu-emacs@gnu.org; Thu, 24 Aug 2023 05:59:12 -0400 Original-Received: from mout01.posteo.de ([185.67.36.65]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1qZ77L-0002RH-CG for bug-gnu-emacs@gnu.org; Thu, 24 Aug 2023 05:59:11 -0400 Original-Received: from submission (posteo.de [185.67.36.169]) by mout01.posteo.de (Postfix) with ESMTPS id 0613E240028 for ; Thu, 24 Aug 2023 11:59:04 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=posteo.net; s=2017; t=1692871145; bh=CP5Sp1pfQxVr0rDgniFPDcYdXbp1yRqpqEhKtF4Duts=; h=From:To:Subject:Date:Message-ID:MIME-Version:From; b=sPLggslNPrkF1x0pYCc5x6zHcNzuTOVtpGXCisMHOENMVmfoaHS4jBsoMRdfYOy9S B44ymXJddBPJ+yOHsW5CwC8l430B1gUyXQP0tZzVtSUxKpkmbeeDfSxUt2niM/rJE+ 8qWHYhEkm05BLApsGWYudsvZWdl3DkimzV0Of4zV+aa5WwGidLkgZQD+XPSXDAJ1IE QFVkuvsEdrXFMVsotdm4RB2dfeH29glpw5WUOwiQYDWlM3ciIjGv+ZsIDuP8/Y5BLR 3mZF0iM2HvuBjIirx5IMIBsl9eN3pY9+pV4oZqKe1CchtQKPEW+cdhJbK6ZvUQZG5F 6JuCKqKDRypdQ== Original-Received: from customer (localhost [127.0.0.1]) by submission (posteo.de) with ESMTPSA id 4RWdpJ1XqLz6tyc for ; Thu, 24 Aug 2023 11:59:04 +0200 (CEST) Received-SPF: pass client-ip=185.67.36.65; envelope-from=yantar92@posteo.net; helo=mout01.posteo.de X-Spam_score_int: -43 X-Spam_score: -4.4 X-Spam_bar: ---- X-Spam_report: (-4.4 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_MED=-2.3, RCVD_IN_MSPIKE_H5=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action 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:268321 Archived-At: --=-=-= Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Tags: patch Hi, 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=C2=B10.04 -> 1.04=C2=B10.03 - pack-unpack 0.40=C2=B10.00 -> 0.35=C2=B10.01 - pidigits 6.00=C2=B10.06 -> 4.08=C2=B10.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.7= 3 | 0.05 | | bubble-no-cons | 1.17 | 0.00 | 0 | 1.1= 7 | 0.07 | | bytecomp | 1.64 | 0.32 | 13 | 1.9= 5 | 0.03 | | dhrystone | 2.13 | 0.00 | 0 | 2.1= 3 | 0.02 | | eieio | 1.19 | 0.13 | 7 | 1.3= 2 | 0.04 | | fibn | 0.00 | 0.00 | 0 | 0.0= 0 | 0.00 | | fibn-named-let | 1.47 | 0.00 | 0 | 1.4= 7 | 0.04 | | fibn-rec | 0.00 | 0.00 | 0 | 0.0= 0 | 0.00 | | fibn-tc | 0.00 | 0.00 | 0 | 0.0= 0 | 0.00 | | flet | 1.41 | 0.00 | 0 | 1.4= 1 | 0.03 | | inclist | 0.84 | 0.00 | 0 | 0.8= 4 | 0.03 | | inclist-type-hints | 0.76 | 0.00 | 0 | 0.7= 6 | 0.00 | | listlen-tc | 0.12 | 0.00 | 0 | 0.1= 2 | 0.01 | | map-closure | 5.25 | 0.00 | 0 | 5.2= 5 | 0.02 | | nbody | 1.47 | 0.15 | 1 | 1.6= 2 | 0.07 | | pack-unpack | 0.38 | 0.02 | 1 | 0.4= 0 | 0.00 | | pack-unpack-old | 1.13 | 0.05 | 3 | 1.1= 9 | 0.03 | | pcase | 1.77 | 0.00 | 0 | 1.7= 7 | 0.01 | | pidigits | 5.04 | 0.97 | 17 | 6.0= 0 | 0.06 | | scroll | 0.58 | 0.00 | 0 | 0.5= 8 | 0.02 | | smie | 1.47 | 0.05 | 2 | 1.5= 2 | 0.02 | |--------------------+----------------+------------+---------+-----------= --+-----------------| | total | 28.49 | 1.74 | 45 | 30.2= 3 | 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.7= 4 | 0.07 | | bubble-no-cons | 1.03 | 0.00 | 0 | 1.0= 3 | 0.02 | | bytecomp | 1.45 | 0.25 | 13 | 1.7= 0 | 0.10 | | dhrystone | 1.98 | 0.00 | 0 | 1.9= 8 | 0.05 | | eieio | 0.92 | 0.12 | 7 | 1.0= 4 | 0.03 | | fibn | 0.00 | 0.00 | 0 | 0.0= 0 | 0.00 | | fibn-named-let | 1.45 | 0.00 | 0 | 1.4= 5 | 0.12 | | fibn-rec | 0.00 | 0.00 | 0 | 0.0= 0 | 0.00 | | fibn-tc | 0.00 | 0.00 | 0 | 0.0= 0 | 0.00 | | flet | 1.39 | 0.00 | 0 | 1.3= 9 | 0.07 | | inclist | 0.83 | 0.00 | 0 | 0.8= 3 | 0.03 | | inclist-type-hints | 0.77 | 0.00 | 0 | 0.7= 7 | 0.03 | | listlen-tc | 0.10 | 0.00 | 0 | 0.1= 0 | 0.00 | | map-closure | 5.25 | 0.00 | 0 | 5.2= 5 | 0.37 | | nbody | 1.45 | 0.16 | 1 | 1.6= 0 | 0.05 | | pack-unpack | 0.33 | 0.02 | 1 | 0.3= 5 | 0.01 | | pack-unpack-old | 1.07 | 0.06 | 3 | 1.1= 3 | 0.08 | | pcase | 1.78 | 0.00 | 0 | 1.7= 8 | 0.05 | | pidigits | 3.15 | 0.92 | 17 | 4.0= 8 | 0.12 | | scroll | 0.55 | 0.00 | 0 | 0.5= 5 | 0.01 | | smie | 1.45 | 0.04 | 2 | 1.4= 9 | 0.06 | |--------------------+----------------+------------+---------+-----------= --+-----------------| | total | 25.63 | 1.62 | 45 | 27.2= 5 | 0.45 | In GNU Emacs 30.0.50 (build 54, x86_64-pc-linux-gnu, GTK+ Version 3.24.38, cairo version 1.17.8) of 2023-08-22 built on localhost Repository revision: c09d78f3c0818d7391760e84f94a442e8beb22dd Repository branch: master Windowing system distributor 'The X.Org Foundation', version 11.0.12101008 System Description: Gentoo Linux Configured using: 'configure --with-native-compilation JAVAC=3D/etc/java-config-2/current-system-vm/bin/javac' --=-=-= Content-Type: text/patch Content-Disposition: attachment; filename=0001-Improve-performance-allocating-vectors.patch >From 476db65dc780d8c501d73dfaaf92c53eb9c73b2f Mon Sep 17 00:00:00 2001 Message-ID: <476db65dc780d8c501d73dfaaf92c53eb9c73b2f.1692869114.git.yantar92@posteo.net> From: Ihor Radchenko Date: Thu, 24 Aug 2023 11:05:18 +0300 Subject: [PATCH] Improve performance allocating vectors * src/alloc.c (last_known_vector_free_idx): New global variable holding the last known free allocated vector index in `vector_free_lists'. (setup_on_free_list): Record the vector index when adding a new allocated vector to `vector_free_lists'. (allocate_vector_from_block): Add heuristics searching for an existing allocated vector no earlier than `last_known_vector_free_idx'. This heuristics may sometimes skip available allocated vectors, but reduces the number of the `for' loop iterations significantly. (sweep_vectors): Set `last_known_vector_free_idx' to large value - no free allocated vectors remain available after sweep operation. Link: https://yhetil.org/emacs-devel/87bkfdsmde.fsf@localhost --- src/alloc.c | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) diff --git a/src/alloc.c b/src/alloc.c index c77bdc6372d..4293de2bdf3 100644 --- a/src/alloc.c +++ b/src/alloc.c @@ -3145,6 +3145,7 @@ large_vector_vec (struct large_vector *p) static struct Lisp_Vector *vector_free_lists[VECTOR_MAX_FREE_LIST_INDEX]; +static ptrdiff_t last_known_vector_free_idx = VECTOR_MAX_FREE_LIST_INDEX; /* Singly-linked list of large vectors. */ static struct large_vector *large_vectors; @@ -3180,6 +3181,7 @@ setup_on_free_list (struct Lisp_Vector *v, ptrdiff_t nbytes) set_next_vector (v, vector_free_lists[vindex]); ASAN_POISON_VECTOR_CONTENTS (v, nbytes - header_size); vector_free_lists[vindex] = v; + last_known_vector_free_idx = vindex; } /* Get a new vector block. */ @@ -3234,7 +3236,7 @@ allocate_vector_from_block (ptrdiff_t nbytes) /* Next, check free lists containing larger vectors. Since we will split the result, we should have remaining space large enough to use for one-slot vector at least. */ - for (index = VINDEX (nbytes + VBLOCK_BYTES_MIN); + for (index = max (VINDEX (nbytes + VBLOCK_BYTES_MIN), last_known_vector_free_idx); index < VECTOR_MAX_FREE_LIST_INDEX; index++) if (vector_free_lists[index]) { @@ -3426,6 +3428,7 @@ sweep_vectors (void) gcstat.total_vectors = 0; gcstat.total_vector_slots = gcstat.total_free_vector_slots = 0; memset (vector_free_lists, 0, sizeof (vector_free_lists)); + last_known_vector_free_idx = VECTOR_MAX_FREE_LIST_INDEX; /* Looking through vector blocks. */ -- 2.41.0 --=-=-= Content-Type: text/plain -- Ihor Radchenko // yantar92, Org mode contributor, Learn more about Org mode at . Support Org development at , or support my work at --=-=-=--