[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: sorting in C
From: |
Andrew Cohen |
Subject: |
Re: sorting in C |
Date: |
Sun, 27 Feb 2022 17:11:53 +0800 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) |
>>>>> "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
- Re: sorting in C, (continued)
- Re: sorting in C, Andrew Cohen, 2022/02/22
- Re: sorting in C, Eli Zaretskii, 2022/02/23
- Re: sorting in C, Andrew Cohen, 2022/02/23
- Re: sorting in C, Eli Zaretskii, 2022/02/23
- Re: sorting in C, Andrew Cohen, 2022/02/23
- Re: sorting in C, Andrew Cohen, 2022/02/23
- Re: sorting in C, Eli Zaretskii, 2022/02/23
- Re: sorting in C, Andrew Cohen, 2022/02/26
- Re: sorting in C, Andrew Cohen, 2022/02/26
- Re: sorting in C, Eli Zaretskii, 2022/02/27
- Re: sorting in C,
Andrew Cohen <=
- Re: sorting in C, Eli Zaretskii, 2022/02/27
- Re: sorting in C, Andrew Cohen, 2022/02/27
- Re: sorting in C, Yuri Khan, 2022/02/23
- Re: sorting in C, Andrew Cohen, 2022/02/23
Re: sorting in C, Lars Ingebrigtsen, 2022/02/22