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: Mon, 28 Aug 2023 12:32:01 -0400 Message-ID: References: <87y1i0iwvu.fsf@localhost> <87il8z323q.fsf@localhost> Reply-To: Stefan Monnier Mime-Version: 1.0 Content-Type: text/plain Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="34488"; 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 Mon Aug 28 18:33:12 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 1qafAu-0008mT-BR for geb-bug-gnu-emacs@m.gmane-mx.org; Mon, 28 Aug 2023 18:33:12 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1qafAf-00012S-PY; Mon, 28 Aug 2023 12:32:57 -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 1qafAd-00012H-PV for bug-gnu-emacs@gnu.org; Mon, 28 Aug 2023 12:32:55 -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 1qafAd-000518-IL for bug-gnu-emacs@gnu.org; Mon, 28 Aug 2023 12:32:55 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1qafAj-0002Oi-VV for bug-gnu-emacs@gnu.org; Mon, 28 Aug 2023 12:33:01 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Stefan Monnier Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Mon, 28 Aug 2023 16:33:01 +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.16932403439169 (code B ref 65491); Mon, 28 Aug 2023 16:33:01 +0000 Original-Received: (at 65491) by debbugs.gnu.org; 28 Aug 2023 16:32:23 +0000 Original-Received: from localhost ([127.0.0.1]:48894 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1qafA7-0002Np-Cc for submit@debbugs.gnu.org; Mon, 28 Aug 2023 12:32:23 -0400 Original-Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:1228) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1qafA4-0002Na-Aq for 65491@debbugs.gnu.org; Mon, 28 Aug 2023 12:32:21 -0400 Original-Received: from pmg3.iro.umontreal.ca (localhost [127.0.0.1]) by pmg3.iro.umontreal.ca (Proxmox) with ESMTP id E566E4414C7; Mon, 28 Aug 2023 12:32:07 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca; s=mail; t=1693240321; bh=r8YpZBXLcYz7h8DgLkIqBmFpzLpR4ou6ZXawvvFH2lo=; h=From:To:Cc:Subject:In-Reply-To:References:Date:From; b=bYdh+YryUjv7jesNdmmeN2VIdu8CkWgBspZx3qyFzFgow4nYwUhgOJ6dkljwPH2C/ 2qo1a3BuVxH/TmxfpxSMpdox2wPeGbdF0G3KS/EWRwskhr0g5ajOEvukihTjKdtKXS DjxVm7jJ9CHqaTCsEgOOikKDQyvtwhIczSEwk5Zx2fE+cGQNHVv1xUb4l9q5JTjSuv 5rBYy5rBlckRyyTk08ZZihUI/gIBMTSTG/FgSHyuQbvQrilSQ9imqHE6ZkATknVjWO mFPXIatiVw4UayoLUevZgzoUPqQw379+oJsQkgjbKhmNr7bMRJyiUmUNmmvmFryWm5 Dl+y3ksgDb8mA== Original-Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1]) by pmg3.iro.umontreal.ca (Proxmox) with ESMTP id CB3DC440BB5; Mon, 28 Aug 2023 12:32:01 -0400 (EDT) Original-Received: from pastel (unknown [108.175.234.188]) by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id AAAE21203CF; Mon, 28 Aug 2023 12:32:01 -0400 (EDT) In-Reply-To: <87il8z323q.fsf@localhost> (Ihor Radchenko's message of "Mon, 28 Aug 2023 10:14:49 +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:268636 Archived-At: > The reason might be that vector sizes are distributed non-uniformly and > some segments of vector_free_lists are filled more than others. Indeed, I'd expect that at any given time, many buckets of `vector_free_lists` are empty. Also, when ELisp code allocates many structs of the same size, the first few allocations may be satisfied by free elements in the appropriate bucket, but very quickly that bucket will become empty, so we'll look for the next non-empty bucket, and the remaining slightly-smaller free vector will then be put back into a lower bucket but the next allocation will go through the same loop to find that same "slightly-smaller free vector", to make it yet a bit smaller, ... until it's all consumed after which we'll look for the next bigger free vector etc... So your code makes a lot of sense from that point of view. Many mallocs approach the problem by creating whole pages dedicated to a given object size, so when the bucket is empty, N new free vectors of that exact size are created (in a new vector-block) and put into the appropriate bucket so the next N allocations of that same size will quickly find a free vector. Since all those vector-blocks are made of vectors of the same size, the size info can be shared between them instead of each one of them carrying its own size. [ In our case, vectors need to carry their size for other purposes than memory management, so it's not clear we'd gain much there. But it could help make `live_small_vector_holding` faster. ] Stefan