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 10:27:30 +0800 Organization: Hong Kong University of Science and Technology Message-ID: <87h78l9h7x.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> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="18236"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) Cc: Mattias =?utf-8?Q?Engdeg=C3=A5rd?= To: emacs-devel@gnu.org Cancel-Lock: sha1:fJ/RTNJzLTU5M42XWQrO8u95wnM= Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Sun Feb 27 03:28:24 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 1nO9IO-0004dH-PX for ged-emacs-devel@m.gmane-mx.org; Sun, 27 Feb 2022 03:28:24 +0100 Original-Received: from localhost ([::1]:35804 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1nO9IN-0003vz-DZ for ged-emacs-devel@m.gmane-mx.org; Sat, 26 Feb 2022 21:28:23 -0500 Original-Received: from eggs.gnu.org ([209.51.188.92]:41238) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nO9Hk-0003Ev-H4 for emacs-devel@gnu.org; Sat, 26 Feb 2022 21:27:44 -0500 Original-Received: from ciao.gmane.io ([116.202.254.214]:46784) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nO9Hi-0004l1-Fg for emacs-devel@gnu.org; Sat, 26 Feb 2022 21:27:44 -0500 Original-Received: from list by ciao.gmane.io with local (Exim 4.92) (envelope-from ) id 1nO9Hg-0003ie-Mv for emacs-devel@gnu.org; Sun, 27 Feb 2022 03:27:40 +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:286709 Archived-At: 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. -- Andrew Cohen