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: Fri, 09 Dec 2011 09:05:17 -0500 Message-ID: References: <4EDDA68B.5050601@yandex.ru> <4EDE315E.3030804@yandex.ru> <4EDEF421.6090800@yandex.ru> <4EDF8F8E.8050401@yandex.ru> <87hb1b25i7.fsf@uwakimon.sk.tsukuba.ac.jp> <4EE03FFD.1090400@yandex.ru> <4EE0EA5C.1090505@yandex.ru> <4EE1CF09.70700@yandex.ru> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: dough.gmane.org 1323439536 2881 80.91.229.12 (9 Dec 2011 14:05:36 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Fri, 9 Dec 2011 14:05:36 +0000 (UTC) Cc: emacs-devel@gnu.org To: Dmitry Antipov Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri Dec 09 15:05:30 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 1RZ14s-0001gu-4W for ged-emacs-devel@m.gmane.org; Fri, 09 Dec 2011 15:05:30 +0100 Original-Received: from localhost ([::1]:37825 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1RZ14r-000692-9n for ged-emacs-devel@m.gmane.org; Fri, 09 Dec 2011 09:05:29 -0500 Original-Received: from eggs.gnu.org ([140.186.70.92]:48156) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1RZ14l-00068c-Aj for emacs-devel@gnu.org; Fri, 09 Dec 2011 09:05:27 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1RZ14h-0005mx-12 for emacs-devel@gnu.org; Fri, 09 Dec 2011 09:05:23 -0500 Original-Received: from ironport2-out.teksavvy.com ([206.248.154.181]:6897) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1RZ14g-0005mt-Tq for emacs-devel@gnu.org; Fri, 09 Dec 2011 09:05:18 -0500 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Av0EAJcU4k5FpY2M/2dsb2JhbABDqniBBoFyAQEEAVYjBQsLDiYSFBgNJIgatheLcgSIMJo0hFE X-IronPort-AV: E=Sophos;i="4.71,326,1320642000"; d="scan'208";a="151582671" Original-Received: from 69-165-141-140.dsl.teksavvy.com (HELO ceviche.home) ([69.165.141.140]) by ironport2-out.teksavvy.com with ESMTP/TLS/ADH-AES256-SHA; 09 Dec 2011 09:05:17 -0500 Original-Received: by ceviche.home (Postfix, from userid 20848) id 6FF24660E9; Fri, 9 Dec 2011 09:05:17 -0500 (EST) In-Reply-To: <4EE1CF09.70700@yandex.ru> (Dmitry Antipov's message of "Fri, 09 Dec 2011 13:04:09 +0400") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.0.92 (gnu/linux) X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 206.248.154.181 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:146600 Archived-At: >> How much did it help? > Not too much because it makes no sense without block-based vector Your test with the *compilation* seems to indicate otherwise, or am I missing something? >> And you said that using the non-conservative stack scanning resulted in >> similar results, so all that extra memory is occupied by mem_nodes (or >> fragments that used to hole mem_nodes ;-). > Yes, one mem_node per each vector results in substantial overhead and > fragmentation. _Any_ block-based vector allocator should reduce the number > of mem_nodes, so saving space - but rounding allocator will consume some Exactly: no need to work hard. > of this space back for it's own internal fragmentation. That's why > I proposed the scheme with tightest possible fit instead of 'standard > malloc algorithm'. The apparently tightest fit is not necessarily tighter: what happens if you use an "order624" to allocate a 600B object, then use the remaining 24B for another object, and then free the 600B object? I also really want to know the answer to this question (third try): Why have different classes for 632B and 600B sizes? You can't fit more than 6 vectors of either size in a 4KB block, so you might as well divide your "order600" block into 6 chunks of 680B (plus 16B of padding) rather than 6 chunks of 600B plus an unused 496B of padding. Stefan