Subject: bug#25606: [DRAFT PATCH 2/2] Signal list cycles in ‘length’ etc.

From: Paul Eggert <[email-masked]>
Date: Thu, 2 Feb 2017 15:01:16 -0800

On 02/02/2017 09:28 AM, Eli Zaretskii wrote:

> could we please have tests for these functions?
Good point, I'll look into adding some.

> I think we shouldn't second-guess users this way, and
> should always leave them the possibility of interrupting a possibly
> prolonged calculation.

Sure, but we shouldn't insert maybe_quit calls after every nanosecond's 
worth of computation; that'd be overkill and would slow down Emacs 
unnecessarily. We should insert a maybe_quit call only when Emacs may 
have done enough computation that it would be annoying if the user typed 
C-g and Emacs did not respond for that period of time.

A reasonable rule of thumb is that if an operation can take longer than 
a garbage collection, then we should insert a maybe_quit in its loop 
body. Conversely, if an operation is always significantly faster then 
GC, then we needn't bother inserting maybe_quit, as Emacs cannot quit in 
the middle of GC anyway (and if we ever get around to fixing *that* 
problem then we will likely be able use the fix approach to attack the 
problem everywhere, not just in GC).

This rule of thumb corresponds pretty closely to what Emacs is already 
doing. For example, Emacs does a maybe_quit while doing regex searching, 
as in practice buffers can be quite large and searching them can easily 
take longer than a GC. In contrast, Emacs does not do a maybe_quit when 
FACE_FOR_CHAR searches font-encoding-charset-alist, as in practice that 
list is never so long that the a user would notice any C-g delay (and if 
the list actually did contain billions of elements (!), GC would be slow 
too as it would have to mark the list).

With cycle checking, all the loops containing removed maybe_quits are 
waaaay faster than a GC would be, which is why these loops don't need 
those maybe_quit calls once they start checking for list cycles.