From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Stefan Monnier Newsgroups: gmane.emacs.devel Subject: Re: Proposal: block-based vector allocator Date: Wed, 07 Dec 2011 11:30:23 -0500 Message-ID: References: <4EDDA68B.5050601@yandex.ru> <4EDE315E.3030804@yandex.ru> <4EDEF421.6090800@yandex.ru> <4EDF8F8E.8050401@yandex.ru> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: dough.gmane.org 1323275519 19349 80.91.229.12 (7 Dec 2011 16:31:59 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Wed, 7 Dec 2011 16:31:59 +0000 (UTC) Cc: emacs-devel@gnu.org To: Dmitry Antipov Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Wed Dec 07 17:31:55 2011 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([140.186.70.17]) by lo.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1RYKPT-00085a-LC for ged-emacs-devel@m.gmane.org; Wed, 07 Dec 2011 17:31:55 +0100 Original-Received: from localhost ([::1]:40614 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1RYKPS-0006uJ-Sq for ged-emacs-devel@m.gmane.org; Wed, 07 Dec 2011 11:31:54 -0500 Original-Received: from eggs.gnu.org ([140.186.70.92]:39319) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1RYKPQ-0006uE-Kb for emacs-devel@gnu.org; Wed, 07 Dec 2011 11:31:53 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1RYKPP-0000FY-Hg for emacs-devel@gnu.org; Wed, 07 Dec 2011 11:31:52 -0500 Original-Received: from pruche.dit.umontreal.ca ([132.204.246.22]:38461) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1RYKPP-0000CF-Dd for emacs-devel@gnu.org; Wed, 07 Dec 2011 11:31:51 -0500 Original-Received: from faina.iro.umontreal.ca (lechon.iro.umontreal.ca [132.204.27.242]) by pruche.dit.umontreal.ca (8.14.1/8.14.1) with ESMTP id pB7GUOnW029838; Wed, 7 Dec 2011 11:30:24 -0500 Original-Received: by faina.iro.umontreal.ca (Postfix, from userid 20848) id 0AF7CB42C1; Wed, 7 Dec 2011 11:30:23 -0500 (EST) In-Reply-To: <4EDF8F8E.8050401@yandex.ru> (Dmitry Antipov's message of "Wed, 07 Dec 2011 20:08:46 +0400") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.0.92 (gnu/linux) X-NAI-Spam-Flag: NO X-NAI-Spam-Threshold: 5 X-NAI-Spam-Score: 0 X-NAI-Spam-Rules: 1 Rules triggered RV4064=0 X-NAI-Spam-Version: 2.2.0.9309 : core <4064> : streams <708609> : uri <1023469> X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 132.204.246.22 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:146558 Archived-At: >> Then I suggest you leave the code alone: we have no evidence that the >> allocation pattern of vectors is any different than what malloc was >> designed for, and the malloc library has seen many years of engineering >> and tweaking, so you're very unlikely to do better than it does. > At least for the vector allocation, I did it in a few days, if you believe > in my numbers and byte-force-recompile as a representative benchmark. I'm not convinced your result is because your code does better than malloc. Instead I expect it's because it avoids the mem_node overhead. Recompiling and trying again without conservative stack scanning should factor out this effect. I'm still curious why you have a "order608" for 4KB blocks, since dividing the 4KB block into 608 would leave you with a lot of padding at the end and reducing the number of distinct "orders" should reduce fragmentation. >> Then you're doing it wrong: do it the way Lisp_Strings are handled >> (i.e. with compaction). > Although some designs makes it pretty hard, compaction is orthogonal to > an allocation, and allocator I'm proposing can be enhanced to support > compaction. You can't do compaction without changing the Lisp_Vector's layout (adding an indirection, as is done for Lisp_Strings). >> None of this is related to the GC speed anyway. > Wrong. Among others, good design might (and should) try to improve the > spatial locality of allocated objects, thus giving less data cache misses > and so better speed. It's very hard to predict how marking traversal > accesses the memory, and locality of this procedure is known to be very > poor. But, for example, sweeping of block-packed data is definitely > faster than sweeping the same amount of data randomly dispersed > among the heap. I thought we agreed that GC performance is not a concern here. Of course, every change to the layout can impact the performance of the GC. Have you measured the impact of your code on GC performance? Stefan