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: Thu, 07 Jun 2012 10:07:06 -0400 Message-ID: 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> <4FCF701C.6070106@yandex.ru> <4FD07C54.8030701@yandex.ru> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: dough.gmane.org 1339078046 14575 80.91.229.3 (7 Jun 2012 14:07:26 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Thu, 7 Jun 2012 14:07:26 +0000 (UTC) Cc: emacs-devel@gnu.org To: Dmitry Antipov Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Thu Jun 07 16:07:26 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 1ScdMz-0001NH-6q for ged-emacs-devel@m.gmane.org; Thu, 07 Jun 2012 16:07:25 +0200 Original-Received: from localhost ([::1]:51145 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ScdMy-000830-Sp for ged-emacs-devel@m.gmane.org; Thu, 07 Jun 2012 10:07:24 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:54538) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ScdMs-0007wR-9i for emacs-devel@gnu.org; Thu, 07 Jun 2012 10:07:22 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ScdMj-0001v9-Mi for emacs-devel@gnu.org; Thu, 07 Jun 2012 10:07:17 -0400 Original-Received: from chene.dit.umontreal.ca ([132.204.246.20]:42809) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ScdMj-0001uq-HR for emacs-devel@gnu.org; Thu, 07 Jun 2012 10:07:09 -0400 Original-Received: from faina.iro.umontreal.ca (lechon.iro.umontreal.ca [132.204.27.242]) by chene.dit.umontreal.ca (8.14.1/8.14.1) with ESMTP id q57E77Fh017517; Thu, 7 Jun 2012 10:07:07 -0400 Original-Received: by faina.iro.umontreal.ca (Postfix, from userid 20848) id C0084B4192; Thu, 7 Jun 2012 10:07:06 -0400 (EDT) In-Reply-To: <4FD07C54.8030701@yandex.ru> (Dmitry Antipov's message of "Thu, 07 Jun 2012 14:03:00 +0400") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.1.50 (gnu/linux) X-NAI-Spam-Flag: NO X-NAI-Spam-Threshold: 5 X-NAI-Spam-Score: 0 X-NAI-Spam-Rules: 1 Rules triggered RV4245=0 X-NAI-Spam-Version: 2.2.0.9309 : core <4245> : streams <766630> : uri <1128232> X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 132.204.246.20 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:150808 Archived-At: >> The cost (CPU or memory, it doesn't matter much here, and we ignore >> fragmentation) of allocating a vector is something like: >> and CPU costs alike, ignores fragmentation): >> - outside of a vector-block: malloc + mem_node >> - inside a vector-block: vector-block + frac * (malloc + mem_node + a-bit-more) >> where "frac" is a fraction that's more or less vector-size / >> VECTOR_BLOCK_BYTES. >> So for small vectors, "frac" is small and since we expect the >> vector-block overhead to be significantly smaller than malloc+mem_node >> we win. But past a certain value of "frac", we're better off allocating >> outside of a vector-block. As I said, I don't know exactly where that >> threshold is, but using VECTOR_BLOCK_BYTES / 2 should be good enough. > OK. This is a bit more complicated since we need some tricks to > manage free space larger than (approx.) VECTOR_BLOCK_BYTES / 2. I do not know what you're referring to. Could you explain what you mean by that? ....aahhh.... right, I see what you mean now. I don't think fragmenting the left-over space is a good idea. Just keep your free lists for free chunks of size [VECTOR_BLOCK_BYTES/2 ... VECTOR_BLOCK_BYTES], even if you never allocate a vector of that size from those free lists. I.e. keep the old code, just change the part that chooses between "allocate via vector-block or allocate directly" to use a VECTOR_BLOCK_BYTES/2 threshold. > + roundup_size = COMMON_MULTIPLE (sizeof (Lisp_Object), > +#ifdef USE_LSB_TAG > + 8 /* Helps to maintain alignment constraints. */ > +#else > + 1 /* If alignment doesn't matter, should round up > + to sizeof (Lisp_Object) at least. */ > +#endif > + ) All I wanted was a comment explaining the choice of 8. I think using 8 for all cases is perfectly fine (I don't know of any significant case where the above expression will give something smaller anyway). > +/* If VECTOR is too large to join a free list at once, > + this function splits it to smaller fragments. Next, > + all fragments are set up to appropriate free lists. */ > + > +static inline void > +setup_free_space (struct Lisp_Vector *vector) > +{ > + ptrdiff_t index, usedbytes, restbytes; > + > + for (restbytes = vector->header.next.nbytes; > + restbytes >= VBLOCK_BYTES_MIN; restbytes -= usedbytes) > + { > + eassert (restbytes % roundup_size == 0); > + usedbytes = min (restbytes, VBLOCK_BYTES_MAX); > + > + /* Do not create too small fragments. */ > + if (restbytes - usedbytes > 0) > + while (restbytes - usedbytes < VBLOCK_BYTES_MIN) > + usedbytes -= roundup_size; > + > + SETUP_ON_FREE_LIST (vector, usedbytes, index); > + vector = ADVANCE (vector, usedbytes); > + } > + > + /* Make sure all space is used. */ > + eassert (restbytes == 0); > +} This should not have any loop and should not fragment. I.e. it should be barely more than SETUP_ON_FREE_LIST (vector, restbytes, index). The rest looks good now. Feel free to install it, Stefan