From: Andrew Cohen <acohen@ust.hk>
To: emacs-devel@gnu.org
Subject: Re: sorting in C
Date: Sun, 27 Feb 2022 17:11:53 +0800 [thread overview]
Message-ID: <87o82sfzc6.fsf@ust.hk> (raw)
In-Reply-To: 83zgmcojj5.fsf@gnu.org
>>>>> "EZ" == Eli Zaretskii <eliz@gnu.org> writes:
>> From: Andrew Cohen <acohen@ust.hk> Date: Sun, 27 Feb 2022
>> 10:27:30 +0800 Cc: Mattias Engdegård <mattiase@acm.org>
[...]
>> 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
next prev parent reply other threads:[~2022-02-27 9:11 UTC|newest]
Thread overview: 22+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-02-22 2:52 sorting in C Andrew Cohen
2022-02-22 12:30 ` Eli Zaretskii
2022-02-22 12:54 ` Andrew Cohen
2022-02-22 13:11 ` Eli Zaretskii
2022-02-23 4:14 ` Andrew Cohen
2022-02-23 12:34 ` Eli Zaretskii
2022-02-23 12:53 ` Andrew Cohen
2022-02-23 13:14 ` Eli Zaretskii
2022-02-23 13:52 ` Andrew Cohen
2022-02-23 14:06 ` Andrew Cohen
2022-02-23 14:18 ` Eli Zaretskii
2022-02-26 23:54 ` Andrew Cohen
2022-02-27 2:27 ` Andrew Cohen
2022-02-27 7:28 ` Eli Zaretskii
2022-02-27 9:11 ` Andrew Cohen [this message]
2022-02-27 9:29 ` Eli Zaretskii
2022-02-27 10:42 ` Andrew Cohen
2022-03-04 0:13 ` Andrew Cohen
2022-03-04 7:05 ` Eli Zaretskii
2022-02-23 13:19 ` Yuri Khan
2022-02-23 14:12 ` Andrew Cohen
2022-02-22 13:12 ` Lars Ingebrigtsen
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.gnu.org/software/emacs/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=87o82sfzc6.fsf@ust.hk \
--to=acohen@ust.hk \
--cc=emacs-devel@gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://git.savannah.gnu.org/cgit/emacs.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).