From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Eli Zaretskii Newsgroups: gmane.emacs.devel Subject: Re: sorting in C Date: Sun, 27 Feb 2022 09:28:30 +0200 Message-ID: <83zgmcojj5.fsf@gnu.org> References: <87ilt7bokp.fsf@ust.hk> <83tucrt75y.fsf@gnu.org> <8735kakymb.fsf@ust.hk> <835yp5u5h7.fsf@gnu.org> <87ee3thhh3.fsf@ust.hk> <83zgmhsp13.fsf@gnu.org> <8735k97k4b.fsf@ust.hk> <83wnhlsm3m.fsf@gnu.org> <87pmn9gp5q.fsf@ust.hk> <87h78l9h7x.fsf@ust.hk> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="26486"; mail-complaints-to="usenet@ciao.gmane.io" Cc: mattiase@acm.org, emacs-devel@gnu.org To: Andrew Cohen Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Sun Feb 27 08:31:08 2022 Return-path: Envelope-to: ged-emacs-devel@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1nOE1M-0006j8-Hg for ged-emacs-devel@m.gmane-mx.org; Sun, 27 Feb 2022 08:31:08 +0100 Original-Received: from localhost ([::1]:47582 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1nOE1L-0008Es-3n for ged-emacs-devel@m.gmane-mx.org; Sun, 27 Feb 2022 02:31:07 -0500 Original-Received: from eggs.gnu.org ([209.51.188.92]:44616) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nODz3-0006pq-O9 for emacs-devel@gnu.org; Sun, 27 Feb 2022 02:28:45 -0500 Original-Received: from [2001:470:142:3::e] (port=45698 helo=fencepost.gnu.org) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nODz2-0002L0-Pc; Sun, 27 Feb 2022 02:28:44 -0500 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org; s=fencepost-gnu-org; h=MIME-version:References:Subject:In-Reply-To:To:From: Date; bh=wU+VtFONWQEya6sQIKVfcO01O1/SZvzheBwS1cll5a0=; b=BoV/s4FzbnW6uR1+uT3J +GnuFgkoOpTWPJipyzmNyOsDS+QRFqzk3FrOQUCcDq7HTxceh9Aoqc8Sig4MxsRXwL/GtXaSF7lgi sZ/qKmfppQs7j31fFhck64LwAoJwttYl8mlOYHXF0hkBokg0l484RMkwdCAM3g6iNIBENmusLn5da fR9W0T8N7p4N7rU2IlUY3X4pzd+EPUG87e7uL2lXiCdcJORcMmQaEDzulPejJX4vITgOlpmGu5esy 4PtX214yvC4ExfxNG/WRSV7m5W0/3KRZ+w/HHOX5kHiXGqbmnvz48iYsiOxNrqGEY7hgwyL2wKbAM 3xDyUhnewSDBFg==; Original-Received: from [87.69.77.57] (port=1467 helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nODz0-0008Gs-Qm; Sun, 27 Feb 2022 02:28:44 -0500 In-Reply-To: <87h78l9h7x.fsf@ust.hk> (message from Andrew Cohen on Sun, 27 Feb 2022 10:27:30 +0800) X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.29 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-mx.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.io gmane.emacs.devel:286712 Archived-At: > From: Andrew Cohen > Date: Sun, 27 Feb 2022 10:27:30 +0800 > Cc: Mattias Engdegård > > > Mattias E. reminds me (in a private email): > >Since Timsort may allocate temporary scratch space it is important to > >make sure it's freed if the comparison predicate throws. A specbind > >may be needed for the clean-up, but I haven't looked at your timsort > >code -- perhaps you have already solved that problem. > > Dealing with the tmp space is my one remaining question. I note that > when sorting a list of length L, the current (vector) sorting routine > requires space for a tmp array of length L/2. It uses SAFE_ALLOCA_LISP > (and SAFE_FREE) outside the sorting routine and passes a pointer to the > storage as an argument to =sort_vector_inplace=. This way memory > management is easy. > > TIMSORT /also/ requires space for a tmp array of length L/2, but only in > the worst case (random lists). For partially sorted lists it can make do > with less. So it takes a dynamic approach: it allocates a small amount > of storage (enough for an array of length 256) which can handle all > short lists and longer partially sorted lists; and then allocates > additional storage on the fly as needed for other cases. > > Right now my routine accepts a pointer to tmp space as an argument; if > this is null, it uses the dynamic allocation, and otherwise just uses > the pre-allocated storage. > > Clearly the less memory required the better, and for mostly-sorted lists > the pre-allocated 256 is usually sufficient. This saves the space, and > any (minimal) time needed to allocate additional space. > > But the early allocation of the maximum space required (as is done for > the current sorting routine) makes the memory management trivial (which > is good!) and avoids the (minmal) additional time for allocs for random > lists. > > I'm inclined to just go with the current system: allocate the maximum > required before calling the routine, but welcome any advice or > expressions of preference for the dynamic allocation. It is okay to use the existing scheme, since it will at worst have the same limitation as the existing one: when the list or vector to sort is very large, you might run out of memory trying to allocate L/2-size array. However, from your description, it doesn't sound like the more optimal approach of allocating dynamically is much more complicated. In particular, what Mattias said should be easy using the unwind-protect machinery we already have (and use in many similar situations). See the calls to record_unwind_protect_ptr whose first argument is 'xfree'. We also have reallocation routines ready to be used. You could also start with the existing scheme and then add the dynamic allocation as a followup patch. Bottom line: I think it's up to you. Thanks.