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, 06 Jun 2012 18:58:36 +0400 Message-ID: <4FCF701C.6070106@yandex.ru> References: <4EDDA68B.5050601@yandex.ru> <4FB4AFA4.7020601@yandex.ru> <4FBA32D9.5090704@yandex.ru> <4FC775B5.30904@yandex.ru> <4FC8709C.6000903@yandex.ru> <4FCF007F.7080104@yandex.ru> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Trace: dough.gmane.org 1338994595 8559 80.91.229.3 (6 Jun 2012 14:56:35 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Wed, 6 Jun 2012 14:56:35 +0000 (UTC) Cc: emacs-devel@gnu.org To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Wed Jun 06 16:56:34 2012 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1ScHez-00023f-7f for ged-emacs-devel@m.gmane.org; Wed, 06 Jun 2012 16:56:33 +0200 Original-Received: from localhost ([::1]:46912 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ScHey-0000jK-W3 for ged-emacs-devel@m.gmane.org; Wed, 06 Jun 2012 10:56:32 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:52268) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ScHer-0000iQ-Fz for emacs-devel@gnu.org; Wed, 06 Jun 2012 10:56:31 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ScHep-0003I1-Io for emacs-devel@gnu.org; Wed, 06 Jun 2012 10:56:25 -0400 Original-Received: from forward20.mail.yandex.net ([95.108.253.145]:40116) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ScHep-0003HW-3q for emacs-devel@gnu.org; Wed, 06 Jun 2012 10:56:23 -0400 Original-Received: from smtp16.mail.yandex.net (smtp16.mail.yandex.net [95.108.252.16]) by forward20.mail.yandex.net (Yandex) with ESMTP id E11621041E91; Wed, 6 Jun 2012 18:56:20 +0400 (MSK) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yandex.ru; s=mail; t=1338994580; bh=DlL8iY3+Xp1SRHBC+GH7O17oC2C+WreQX79QEy40TaU=; h=Message-ID:Date:From:MIME-Version:To:CC:Subject:References: In-Reply-To:Content-Type:Content-Transfer-Encoding; b=ncbhnKTjfgCNFqKDEbM7q9llkFw7ghlHmUnY+U0OyNa6kQ9ARaZ6c5TxahsEN5/Eb vNt2GXowPnMdptznnekkCiyZxymW91GaI65+8ISgF4qlUqrKXSj0w6gdF6EWFnBGr5 lOEDBhEu/3u4HElLb/KUD+nFr45NTGb+JeKMLaWs= Original-Received: from smtp16.mail.yandex.net (localhost [127.0.0.1]) by smtp16.mail.yandex.net (Yandex) with ESMTP id BFF906A011F; Wed, 6 Jun 2012 18:56:20 +0400 (MSK) Original-Received: from antipov.client.gelicon.ru (antipov.client.gelicon.ru [78.153.153.8]) by smtp16.mail.yandex.net (nwsmtp/Yandex) with ESMTP id uIhCOY5t-uKhCqAfZ; Wed, 6 Jun 2012 18:56:20 +0400 X-Yandex-Rcpt-Suid: monnier@iro.umontreal.ca X-Yandex-Rcpt-Suid: emacs-devel@gnu.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yandex.ru; s=mail; t=1338994580; bh=DlL8iY3+Xp1SRHBC+GH7O17oC2C+WreQX79QEy40TaU=; h=Message-ID:Date:From:User-Agent:MIME-Version:To:CC:Subject: References:In-Reply-To:Content-Type:Content-Transfer-Encoding; b=MmGeo8deyPnUxF3dsHYkvq64j9/xonuNpAcQ42N7KBiA3SZzxwIVkTWTNIqTGxBuk dj9mKc1N82EHrl/xTkI/D5x0YaVEYAT3Y67b2LJw7TwsJL9+x36ieUUYIixW8LEEPH /iwjMqE6zcvbEdcrToRMDkMsdr+EgA/2GxTx2HEQ= User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:12.0) Gecko/20120428 Thunderbird/12.0.1 In-Reply-To: X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 95.108.253.145 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:150797 Archived-At: On 06/06/2012 05:13 PM, Stefan Monnier wrote: > I explained this earlier: using a vector-block for largish vectors is > not efficient (because the overhead of the vector-block is not shared > among enough vectors). > E.g. for a vector of size VECTOR_BLOCK_BYTES, using the vector-block > code is a complete waste ...of just one pointer, so 8/4088, or 0.2% in terms of space for this rare case; an overhead of having one more mem_node is 6x larger. As for the speed, the difference is harder to predict: for the same amount of vectors, more blocks adds more overhead of per-block allocation and sweeping; on the other side, less blocks adds more mem_nodes and thus more overhead of all mem_node tree operations. BTW, I suppose the whole thing should be under #if GC_MARK_STACK. > For the case of a vector of size VECTOR_BLOCK_BYTES, allocating in > a vector block will always be a bad idea, no matter the scenario. Allocating a lot of VECTOR_BLOCK_BYTES / 2 + sizeof (Lisp_Object) vectors (and negligible amount of others) will waste ~50% of space in blocks; if the block allocation limit is VECTOR_BLOCK_BYTES / 2, allocating a lot of VECTOR_BLOCK_BYTES / 4 + sizeof (Lisp_Object) vectors will waste ~25% of space in blocks, etc. I believe this is the most important problem with current design. So, per-block allocation limit should be an answer to two questions: 1) how often we expect to get the worst case and 2) how much we allow to waste for such a case. Dmitry