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: Tue, 06 Dec 2011 19:14:38 +0400 Message-ID: <4EDE315E.3030804@yandex.ru> References: <4EDDA68B.5050601@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 1323184495 17378 80.91.229.12 (6 Dec 2011 15:14:55 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Tue, 6 Dec 2011 15:14:55 +0000 (UTC) To: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Tue Dec 06 16:14:51 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 1RXwjK-00007M-Qi for ged-emacs-devel@m.gmane.org; Tue, 06 Dec 2011 16:14:51 +0100 Original-Received: from localhost ([::1]:58274 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1RXwjJ-0006JP-NU for ged-emacs-devel@m.gmane.org; Tue, 06 Dec 2011 10:14:49 -0500 Original-Received: from eggs.gnu.org ([140.186.70.92]:43875) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1RXwjC-0006JH-2H for emacs-devel@gnu.org; Tue, 06 Dec 2011 10:14:47 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1RXwj7-00062L-Nt for emacs-devel@gnu.org; Tue, 06 Dec 2011 10:14:42 -0500 Original-Received: from mail.dev.rtsoft.ru ([213.79.90.226]:45433) by eggs.gnu.org with smtp (Exim 4.71) (envelope-from ) id 1RXwj7-00061p-0v for emacs-devel@gnu.org; Tue, 06 Dec 2011 10:14:37 -0500 Original-Received: (qmail 680 invoked from network); 6 Dec 2011 15:14:34 -0000 Original-Received: from unknown (HELO ?192.168.5.146?) (192.168.1.70) by 0 with SMTP; 6 Dec 2011 15:14:34 -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:146507 Archived-At: On 12/06/2011 05:35 PM, Stefan Monnier wrote: > Could you give a quick overview of what you've considered and thrown away? The most basic idea was to maintain separate vector blocks for vectors of each possible size (with the room enough to 0, 1, 2, etc. Lisp_Objects - let's call it order0, order1 and so on), up to 4x1K vectors in 4K blocks, and dedicated list for >1K vectors. This scheme is simple, but it tends to hold too much space in free lists, and this space is of 'wrong order'. It was typical to have 1000 free slots in order[234] blocks, but no free space in order50 blocks. As a result, the total memory consumption was _more_ than current. > For large vectors we can probably just keep using what we have now. It is so. > I don't like much splitting&coalescing. Is it really needed? I believe splitting is important because the most of vectors are small, so even a small pieces of unused memory are very likely to be utilized. For (64-bit) example, consider 600-byte request, and there is no 600-byte free block in corresponding free list. In this case, proposed allocator will not consider 608 and 616-byte free lists, because splitting gives 8 and 16-bytes tails, which can't be used to hold any vector (except 0-sized, which is very rare). But it will consider free list with 624-bytes blocks, because 24-bytes tail can be used for the vector holds 1 Lisp_Object. If it fails, next candidate is 632-byte block free list, and so on. And it's very likely that 24-bytes (or 32, or 40, etc.) tail will be used soon, because most vectors are small. Coalescing is harder, because... yes, most vectors are small :-). For example, we can have vector block with 10 free and adjacent 40-byte vectors. While coalescing as much as possible, an obvious result is to create 400-byte free vector and set it on a free list. Next, it's very likely to have, for example, 8 requests for 32,40,32,40,48,32,24,48-byte vectors instead of one request for 360-byte vector. So, if corresponding small-size free lists are empty, an allocator will split 400-byte block back into small pieces. This is an obvious disadvantage of this allocator. But it's possible to introduce a kind of 'coalescing threshold' and stop coalescing if small-size free lists becomes too short in favor of mid- and large-size ones. Dmitry