GNU bug report logs - #54532
Faster sorting

Previous Next

Full log

Message #32 received at 54532 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Andrew Cohen <acohen <at> ust.hk>
Cc: 54532 <at> debbugs.gnu.org, mattiase <at> acm.org
Subject: Re: bug#54532: [PATCH] sorting
Date: Thu, 24 Mar 2022 10:55:48 +0200

> From: Andrew Cohen <acohen <at> ust.hk>
> Cc: Mattias Engdegård <mattiase <at> acm.org>,
>   54532 <at> debbugs.gnu.org
> Date: Thu, 24 Mar 2022 15:22:50 +0800
> 
>     EZ> I understand that these objects are on the heap, but AFAIU a
>     EZ> reference to them is on the stack, isn't it?
> 
> Not always. The algorithm merges sublists A and B (which are adjacent to
> each other on the stack). Doing this entirely in place is very slow
> (lots of swaps) so we use temp memory of size A (assume A is the shorter
> list). The idea is to copy the A list to the heap memory, and then use
> the standard merge algorithm between the heap version of A and (stack
> version of) B, filling in the space where A used to reside in the
> stack. The issue is that since we are filling in areas in the stack that
> were once occupied by A we can end up with some of the original
> Lisp_Objects residing only in the /copy/ of A on the heap. Once the
> merging is done, everyone is at home back on the stack.

If this is just temporary, then how about disabling GC (using
inhibit_garbage_collection) during this stage instead?  Do we expect
to have a lot of garbage generated while this particular part of the
code runs?  Does this code call some Lisp about whose consing behavior
which we cannot assume anything?  If we can be certain we won't have a
lot of garbage during this stage, disabling GC is just TRT, IMO.

In general, having marked Lisp objects should be avoided, because
examining those objects in GDB is tricky at best, and because some
functions/macros will hit assertions if passed such an object.  Two
examples are ASIZE and ASET.  When inside GC, the use of marked
objects is unavoidable, but AFAIU this patch also marks those Lisp
objects while they are in the heap, and GC is not necessarily running,
is that right?  So from my POV we should try to avoid this quite
unusual practice, if that's feasible.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.