From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Dmitry Antipov Newsgroups: gmane.emacs.devel Subject: Re: Proposal: block-based vector allocator Date: Wed, 07 Dec 2011 20:08:46 +0400 Message-ID: <4EDF8F8E.8050401@yandex.ru> References: <4EDDA68B.5050601@yandex.ru> <4EDE315E.3030804@yandex.ru> <4EDEF421.6090800@yandex.ru> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Trace: dough.gmane.org 1323274141 8154 80.91.229.12 (7 Dec 2011 16:09:01 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Wed, 7 Dec 2011 16:09:01 +0000 (UTC) To: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Wed Dec 07 17:08:57 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 1RYK3E-00044W-FG for ged-emacs-devel@m.gmane.org; Wed, 07 Dec 2011 17:08:56 +0100 Original-Received: from localhost ([::1]:59181 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1RYK3D-0000Tp-9m for ged-emacs-devel@m.gmane.org; Wed, 07 Dec 2011 11:08:55 -0500 Original-Received: from eggs.gnu.org ([140.186.70.92]:38533) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1RYK37-0000TI-0Q for emacs-devel@gnu.org; Wed, 07 Dec 2011 11:08:53 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1RYK32-0003Lw-UP for emacs-devel@gnu.org; Wed, 07 Dec 2011 11:08:48 -0500 Original-Received: from mail.dev.rtsoft.ru ([213.79.90.226]:49268) by eggs.gnu.org with smtp (Exim 4.71) (envelope-from ) id 1RYK32-0003L1-Iq for emacs-devel@gnu.org; Wed, 07 Dec 2011 11:08:44 -0500 Original-Received: (qmail 19561 invoked from network); 7 Dec 2011 16:08:41 -0000 Original-Received: from unknown (HELO ?192.168.5.146?) (192.168.1.70) by 0 with SMTP; 7 Dec 2011 16:08:41 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:8.0) Gecko/20111115 Thunderbird/8.0 In-Reply-To: X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6, seldom 2.4 (older, 4) X-Received-From: 213.79.90.226 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:146553 Archived-At: On 12/07/2011 05:52 PM, Stefan Monnier wrote: > 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. > Yes. And the design I propose is one that has proved to be such a good > balance. The design itself can't prove anything. The devil is in the details, and implementation is the only thing that matters. My favorite GC textbook (http://www.amazon.com/gp/product/1420082795) describes a tens of very good designs, but doesn't provide any ready-to-use recipes to help us solve memory usage issues. > 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. > 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. Dmitry