From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Stefan Monnier via "Bug reports for GNU Emacs, the Swiss army knife of text editors" Newsgroups: gmane.emacs.bugs Subject: bug#65491: [PATCH] Improve performance allocating vectors Date: Sun, 27 Aug 2023 12:21:30 -0400 Message-ID: References: <87y1i0iwvu.fsf@localhost> Reply-To: Stefan Monnier Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="19560"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Cc: 65491@debbugs.gnu.org To: Ihor Radchenko Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Sun Aug 27 18:22:27 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 1qaIWw-0004tl-QW for geb-bug-gnu-emacs@m.gmane-mx.org; Sun, 27 Aug 2023 18:22:27 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1qaIWb-0002FS-JW; Sun, 27 Aug 2023 12:22:06 -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 1qaIWS-00028n-RA for bug-gnu-emacs@gnu.org; Sun, 27 Aug 2023 12:21: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 1qaIWS-00007a-Ip for bug-gnu-emacs@gnu.org; Sun, 27 Aug 2023 12:21:56 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1qaIWY-0007y5-Co for bug-gnu-emacs@gnu.org; Sun, 27 Aug 2023 12:22:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Stefan Monnier Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sun, 27 Aug 2023 16:22: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.169315331030597 (code B ref 65491); Sun, 27 Aug 2023 16:22:02 +0000 Original-Received: (at 65491) by debbugs.gnu.org; 27 Aug 2023 16:21:50 +0000 Original-Received: from localhost ([127.0.0.1]:46031 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1qaIWM-0007xR-0i for submit@debbugs.gnu.org; Sun, 27 Aug 2023 12:21:50 -0400 Original-Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:61525) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1qaIWG-0007wx-2j for 65491@debbugs.gnu.org; Sun, 27 Aug 2023 12:21:45 -0400 Original-Received: from pmg2.iro.umontreal.ca (localhost.localdomain [127.0.0.1]) by pmg2.iro.umontreal.ca (Proxmox) with ESMTP id 7B5C380793; Sun, 27 Aug 2023 12:21:32 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca; s=mail; t=1693153291; bh=pdtBJS3jKdo2xIh2v8soKcVJQQ/3lKXROYKDwSHgDJE=; h=From:To:Cc:Subject:In-Reply-To:References:Date:From; b=Kwdn/StgbZHSeu+K/qX2pA+b3Rzfdga7utMn/PyfR7c60vMVWFh2mQ6A+N0dGLXnV pfRJC3YvMV7aWDBaTy+zRuTpmqsafFGBOyO3d/pUsNh2PAkhIZJFPWr2LOCR+98BAX j+gYceFcdvs06Sa9F2arW2011t9dqO2Wqu0h3A6casmBvvrb2it8qMuUX6DXfac6Yn vQbnUgezw4/MDZNM756G3jhjWNN3DmHcH8ovdie1e3IvFwRdg7I0MAX3RXbsa9LLHK LNVO6INPB+cdUBawqiA9sEA0UP2uPopfZtJ8Kt3DLpX5Wi0/OI+lxLoNFYBWmv0gI9 QXrfU6Wm9nK9A== Original-Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1]) by pmg2.iro.umontreal.ca (Proxmox) with ESMTP id 17EE9805DE; Sun, 27 Aug 2023 12:21:31 -0400 (EDT) Original-Received: from pastel (unknown [108.175.234.188]) by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id E294A12024D; Sun, 27 Aug 2023 12:21:30 -0400 (EDT) In-Reply-To: <87y1i0iwvu.fsf@localhost> (Ihor Radchenko's message of "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:268564 Archived-At: > This patch adds a heuristic that reduces the time spent searching > `vector_free_lists' when trying to allocate a new vector. The microbenchmarks give surprisingly good performance improvements. > `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). Hmm... after GC we should usually have a non-zero number of free vectors available (the unused parts of vector blocks which could not be `free`d because they still contain a live vector), no? [ See comment below. ] > The described approach may sometimes miss free vectors in > `vector_free_lists', especially if the allocation happens from larger > vector to smaller. Right, it could lead to an increase in fragmentation, tho it might tend to allocate temporally related objects together, which might be beneficial. > - pack-unpack 0.40=B10.00 -> 0.35=B10.01 Interesting. I didn't expect such a large effect there. > @@ -3145,6 +3145,7 @@ large_vector_vec (struct large_vector *p) >=20=20 > static struct Lisp_Vector *vector_free_lists[VECTOR_MAX_FREE_LIST_INDEX]; >=20=20 > +static ptrdiff_t last_known_vector_free_idx =3D VECTOR_MAX_FREE_LIST_IND= EX; > /* Singly-linked list of large vectors. */ >=20=20 > static struct large_vector *large_vectors; There's clearly some spacing issue with the following comment but more importantly the new var would need a good comment explaining what the variable should hold and why it's useful, so we know when it's safe and desirable to set or use the var. > @@ -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] =3D v; > + last_known_vector_free_idx =3D vindex; > } >=20=20 > /* 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 =3D VINDEX (nbytes + VBLOCK_BYTES_MIN); > + for (index =3D max (VINDEX (nbytes + VBLOCK_BYTES_MIN), last_known_vec= tor_free_idx); > index < VECTOR_MAX_FREE_LIST_INDEX; index++) > if (vector_free_lists[index]) > { IIUC that's the core of your patch. Nice. > @@ -3426,6 +3428,7 @@ sweep_vectors (void) > gcstat.total_vectors =3D 0; > gcstat.total_vector_slots =3D gcstat.total_free_vector_slots =3D 0; > memset (vector_free_lists, 0, sizeof (vector_free_lists)); > + last_known_vector_free_idx =3D VECTOR_MAX_FREE_LIST_INDEX; >=20=20 > /* Looking through vector blocks. */ Hmm... so I was wrong and after GC there are aren't any free vectors? I need to go re-read that code, then, because it doesn't match my mental model of how it work(s|ed). Stefan