From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Andrew Cohen Newsgroups: gmane.emacs.devel Subject: Re: sorting in C Date: Sun, 27 Feb 2022 17:11:53 +0800 Organization: Hong Kong University of Science and Technology Message-ID: <87o82sfzc6.fsf@ust.hk> 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> <83zgmcojj5.fsf@gnu.org> 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="8678"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) To: emacs-devel@gnu.org Cancel-Lock: sha1:JfLvSYkTsNzdskzT1sbhF87Hh4A= Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Sun Feb 27 10:13:44 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 1nOFce-00026H-Ny for ged-emacs-devel@m.gmane-mx.org; Sun, 27 Feb 2022 10:13:44 +0100 Original-Received: from localhost ([::1]:52526 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1nOFcd-0002wD-Nh for ged-emacs-devel@m.gmane-mx.org; Sun, 27 Feb 2022 04:13:43 -0500 Original-Received: from eggs.gnu.org ([209.51.188.92]:58668) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nOFb4-0001sH-08 for emacs-devel@gnu.org; Sun, 27 Feb 2022 04:12:06 -0500 Original-Received: from ciao.gmane.io ([116.202.254.214]:37286) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nOFb1-0003tz-95 for emacs-devel@gnu.org; Sun, 27 Feb 2022 04:12:05 -0500 Original-Received: from list by ciao.gmane.io with local (Exim 4.92) (envelope-from ) id 1nOFay-000AaA-G3 for emacs-devel@gnu.org; Sun, 27 Feb 2022 10:12:00 +0100 X-Injected-Via-Gmane: http://gmane.org/ Received-SPF: pass client-ip=116.202.254.214; envelope-from=ged-emacs-devel@m.gmane-mx.org; helo=ciao.gmane.io X-Spam_score_int: -16 X-Spam_score: -1.7 X-Spam_bar: - X-Spam_report: (-1.7 / 5.0 requ) BAYES_00=-1.9, HEADER_FROM_DIFFERENT_DOMAINS=0.249, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01 autolearn=no autolearn_force=no X-Spam_action: no action 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:286713 Archived-At: >>>>> "EZ" == Eli Zaretskii writes: >> From: Andrew Cohen Date: Sun, 27 Feb 2022 >> 10:27:30 +0800 Cc: Mattias Engdegård [...] >> 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. >> [...] EZ> It is okay to use the existing scheme, since it will at worst EZ> have the same limitation as the existing one: when the list or EZ> vector to sort is very large, you might run out of memory trying EZ> to allocate L/2-size array. EZ> However, from your description, it doesn't sound like the more EZ> optimal approach of allocating dynamically is much more EZ> complicated. In particular, what Mattias said should be easy EZ> using the unwind-protect machinery we already have (and use in EZ> many similar situations). See the calls to EZ> record_unwind_protect_ptr whose first argument is 'xfree'. We EZ> also have reallocation routines ready to be used. That is how I am handling it now, but I'm not sure if I have it right (sorry for the naive question): When I need new memory I call : specpdl_ref sa_count = SPECPDL_INDEX (); : a = (Lisp_Object *) record_xmalloc (need * sizeof (Lisp_Object)); and I save =sa_count=; I guess =record_xmalloc= handles freeing the memory on exception. Later during the sorting process I free the memory explicitly with : safe_free (sa_count) Does this seem right? (Probably, since I've been running this way for awhile and would have expected lots of problems if I weren't allocating and freeing the memory :)) -- Andrew Cohen