GNU bug report logs -
#79611
add drop-while and take-while
Previous Next
To reply to this bug, email your comments to 79611 AT debbugs.gnu.org.
There is no need to reopen the bug first.
Toggle the display of automated, internal messages from the tracker.
Report forwarded
to
bug-gnu-emacs <at> gnu.org:
bug#79611; Package
emacs.
(Fri, 10 Oct 2025 14:42:01 GMT)
Full text and
rfc822 format available.
Acknowledgement sent
to
Mattias Engdegård <mattias.engdegard <at> gmail.com>:
New bug report received and forwarded. Copy sent to
bug-gnu-emacs <at> gnu.org.
(Fri, 10 Oct 2025 14:42:02 GMT)
Full text and
rfc822 format available.
Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):
[Message part 1 (text/plain, inline)]
A recent thread on emacs-devel [1] reminded me that we still don't have a good implementation of the function commonly known as drop-while. Current alternatives include
cl-member-if, cl-member-if-not: very slow
seq-drop-while: also very slow
cl-loop: flexible but difficult to use correctly
It thus seems reasonable to add `drop-while` and it's natural companion, `take-while`; we already have their counted counterparts, `drop` and `take` as built-ins. Suggested patch attached; manual and NEWS entries remain to be written.
Performance is close to that of hand-written code and much better than the alternatives above, which are difficult to improve to the same level because of how they are designed.
`drop-while` could also be used for fast implementations of `any` and `all`. These are very handy and readable so I added them in a separate patch below.
I also include `notall` and `notany` although they are really just negations of `all` and `any` and so just save some bracketing as well as a double negation for `notall`. Do tell what you think about those.
[1] https://lists.gnu.org/archive/html/emacs-devel/2025-09/msg00915.html
[0001-Add-drop-while-and-take-while.patch (application/octet-stream, attachment)]
[0002-Add-any-all-notany-and-notall.patch (application/octet-stream, attachment)]
Information forwarded
to
bug-gnu-emacs <at> gnu.org:
bug#79611; Package
emacs.
(Sat, 11 Oct 2025 10:45:02 GMT)
Full text and
rfc822 format available.
Message #8 received at 79611 <at> debbugs.gnu.org (full text, mbox):
Some benchmark results, presented as relative times (`drop-while` is 1), run on a list of SIZE elements for which the predicate is true. (Native-comp not enabled here.)
Predicates used: (lambda (x) (< x 1)), #'zerop and #'bufferp.
Note that in practice, performance for short lists are just as important as for long ones; short lists are often found inside loops. The constant overhead for each call matters.
| function | pred | size | total | in GC | non-GC |
|------------------+---------+------+--------+-------+--------|
| cl-loop | lambda | 0 | 1.270 | 0.000 | 1.270 |
| cl-member-if-not | lambda | 0 | 84.680 | 6.815 | 22.297 |
| seq-drop-while | lambda | 0 | 53.536 | 4.525 | 12.110 |
|------------------+---------+------+--------+-------+--------|
| cl-loop | lambda | 10 | 1.357 | 0.000 | 1.357 |
| cl-member-if-not | lambda | 10 | 12.671 | 0.682 | 6.127 |
| seq-drop-while | lambda | 10 | 7.644 | 0.451 | 3.318 |
|------------------+---------+------+--------+-------+--------|
| cl-loop | lambda | 100 | 1.377 | 0.000 | 1.377 |
| cl-member-if-not | lambda | 100 | 5.268 | 0.061 | 4.592 |
| seq-drop-while | lambda | 100 | 2.876 | 0.035 | 2.483 |
|------------------+---------+------+--------+-------+--------|
| cl-loop | zerop | 0 | 1.437 | 0.000 | 1.437 |
| cl-member-if-not | zerop | 0 | 45.675 | 2.293 | 21.755 |
| seq-drop-while | zerop | 0 | 10.294 | 0.000 | 10.294 |
|------------------+---------+------+--------+-------+--------|
| cl-loop | zerop | 10 | 1.608 | 0.000 | 1.608 |
| cl-member-if-not | zerop | 10 | 9.488 | 0.227 | 6.888 |
| seq-drop-while | zerop | 10 | 3.555 | 0.000 | 3.555 |
|------------------+---------+------+--------+-------+--------|
| cl-loop | zerop | 100 | 1.651 | 0.000 | 1.651 |
| cl-member-if-not | zerop | 100 | 5.651 | 0.012 | 5.495 |
| seq-drop-while | zerop | 100 | 2.964 | 0.000 | 2.964 |
|------------------+---------+------+--------+-------+--------|
| cl-loop | bufferp | 0 | 1.248 | 0.000 | 1.248 |
| cl-member-if-not | bufferp | 0 | 26.436 | 2.327 | 12.303 |
| seq-drop-while | bufferp | 0 | 5.627 | 0.000 | 5.627 |
|------------------+---------+------+--------+-------+--------|
| cl-loop | bufferp | 10 | 1.285 | 0.000 | 1.285 |
| cl-member-if-not | bufferp | 10 | 4.465 | 0.234 | 3.106 |
| seq-drop-while | bufferp | 10 | 1.461 | 0.000 | 1.461 |
|------------------+---------+------+--------+-------+--------|
| cl-loop | bufferp | 100 | 1.285 | 0.000 | 1.285 |
| cl-member-if-not | bufferp | 100 | 2.324 | 0.013 | 2.244 |
| seq-drop-while | bufferp | 100 | 1.060 | 0.000 | 1.060 |
|------------------+---------+------+--------+-------+--------|
Information forwarded
to
bug-gnu-emacs <at> gnu.org:
bug#79611; Package
emacs.
(Sat, 11 Oct 2025 13:19:02 GMT)
Full text and
rfc822 format available.
Message #11 received at 79611 <at> debbugs.gnu.org (full text, mbox):
Hello,
On Fri 10 Oct 2025 at 04:41pm +02, Mattias Engdegård wrote:
> `drop-while` could also be used for fast implementations of `any` and
> `all`. These are very handy and readable so I added them in a separate patch
> below.
>
> I also include `notall` and `notany` although they are really just negations
> of `all` and `any` and so just save some bracketing as well as a double
> negation for `notall`. Do tell what you think about those.
I think that we should use the existing CL names 'every', 'some',
'notevery', 'notany'.
And then I think we should replace 'cl-every' with a new 'every',
'cl-notany' with a new 'notany' etc..
We have done this several times before like with how 'cl-plusp' was
replaced with a native 'plusp' recently, and less recently there was
'cl-incf' becoming just 'incf'.
--
Sean Whitton
Information forwarded
to
bug-gnu-emacs <at> gnu.org:
bug#79611; Package
emacs.
(Sat, 11 Oct 2025 14:06:01 GMT)
Full text and
rfc822 format available.
Message #14 received at 79611 <at> debbugs.gnu.org (full text, mbox):
11 okt. 2025 kl. 15.18 skrev Sean Whitton <spwhitton <at> spwhitton.name>:
> I think that we should use the existing CL names 'every', 'some',
> 'notevery', 'notany'.
Well the semantics are not quite the same: `cl-every` works on vectors and strings and take multiple sequence arguments, neither of which are proposed here. `cl-some` and `cl-notevery` also differ in return values.
But if you are happy with an `every` that is faster but not quite the same as `cl-every` then we could add it as an alias for `all`, etc.
Information forwarded
to
bug-gnu-emacs <at> gnu.org:
bug#79611; Package
emacs.
(Sat, 11 Oct 2025 14:25:01 GMT)
Full text and
rfc822 format available.
Message #17 received at 79611 <at> debbugs.gnu.org (full text, mbox):
> Some benchmark results, presented as relative times (`drop-while` is 1), run
[...]
> | function | pred | size | total | in GC | non-GC |
> |------------------+---------+------+--------+-------+--------|
> | cl-loop | lambda | 0 | 1.270 | 0.000 | 1.270 |
> | cl-member-if-not | lambda | 0 | 84.680 | 6.815 | 22.297 |
> | seq-drop-while | lambda | 0 | 53.536 | 4.525 | 12.110 |
[ I don't know how to interpret those numbers: shouldn't the "total"
column have a value somewhere between the "in GC" and the
"non-GC" column? ]
It would be nice to lower the cost of the cl-generic dispatch, which
AFAIK is the only reason why `seq-drop-while` is slower than `cl-loop`
or your new code.
There's a lot room for improvement.
E.g. avoiding allocation in the `&rest+apply` path should bring the "in GC"
cost to zero for `seq-drop-while`.
Stefan
Information forwarded
to
bug-gnu-emacs <at> gnu.org:
bug#79611; Package
emacs.
(Sat, 11 Oct 2025 14:30:02 GMT)
Full text and
rfc822 format available.
Message #20 received at 79611 <at> debbugs.gnu.org (full text, mbox):
Hello,
On Sat 11 Oct 2025 at 04:04pm +02, Mattias Engdegård wrote:
> 11 okt. 2025 kl. 15.18 skrev Sean Whitton <spwhitton <at> spwhitton.name>:
>
>> I think that we should use the existing CL names 'every', 'some',
>> 'notevery', 'notany'.
>
> Well the semantics are not quite the same: `cl-every` works on vectors and
> strings and take multiple sequence arguments, neither of which are proposed
> here. `cl-some` and `cl-notevery` also differ in return values.
Ah, good points.
I take it making your proposed new functions generic over sequences
would make them too slow?
--
Sean Whitton
Information forwarded
to
bug-gnu-emacs <at> gnu.org:
bug#79611; Package
emacs.
(Sat, 11 Oct 2025 14:50:02 GMT)
Full text and
rfc822 format available.
Message #23 received at 79611 <at> debbugs.gnu.org (full text, mbox):
11 okt. 2025 kl. 16.23 skrev Stefan Monnier <monnier <at> iro.umontreal.ca>:
> [ I don't know how to interpret those numbers: shouldn't the "total"
> column have a value somewhere between the "in GC" and the
> "non-GC" column? ]
You are right, it's an artefact of the normalisation to the time of `drop-while` (which always has an in-GC value of zero). Better ignore the "in GC" column for now.
> It would be nice to lower the cost of the cl-generic dispatch, which
> AFAIK is the only reason why `seq-drop-while` is slower than `cl-loop`
> or your new code.
No, the inlining of the predicate call is a major factor: it bypasses closure creation for lambda forms as well as removes calls to it.
It is true that the dispatch overhead of seq functions is high, and it shows when scaling down.
> There's a lot room for improvement.
That for sure, but I don't think seq can ever really compete without much more muscle behind it, like a JIT that can type-specialise and inline. (I note that `seq-subseq` has so little faith in the generic machinery that it does the type dispatch the old-fashioned way...)
> E.g. avoiding allocation in the `&rest+apply` path should bring the "in GC"
> cost to zero for `seq-drop-while`.
Is that really an issue here? None of the functions are variadic, and `seq-drop-while` has zero GC cost when there's no closure creation.
Information forwarded
to
bug-gnu-emacs <at> gnu.org:
bug#79611; Package
emacs.
(Sat, 11 Oct 2025 14:51:01 GMT)
Full text and
rfc822 format available.
Message #26 received at 79611 <at> debbugs.gnu.org (full text, mbox):
11 okt. 2025 kl. 16.29 skrev Sean Whitton <spwhitton <at> spwhitton.name>:
> I take it making your proposed new functions generic over sequences
> would make them too slow?
Oh yes. That's essentially what `seq-drop-while` does. Given that it's practically always going to be lists, that's a waste.
Information forwarded
to
bug-gnu-emacs <at> gnu.org:
bug#79611; Package
emacs.
(Sat, 11 Oct 2025 19:23:01 GMT)
Full text and
rfc822 format available.
Message #29 received at 79611 <at> debbugs.gnu.org (full text, mbox):
>> E.g. avoiding allocation in the `&rest+apply` path should bring the "in GC"
>> cost to zero for `seq-drop-while`.
> Is that really an issue here? None of the functions are variadic, and
> `seq-drop-while` has zero GC cost when there's no closure creation.
Oh, indeed, I misread. Yeah, it happens to avoid the allocation in
`&rest+apply` because the dispatch is on the last argument (so the
&rest is an empty list).
Stefan
Information forwarded
to
bug-gnu-emacs <at> gnu.org:
bug#79611; Package
emacs.
(Fri, 17 Oct 2025 13:17:03 GMT)
Full text and
rfc822 format available.
Message #32 received at 79611 <at> debbugs.gnu.org (full text, mbox):
[Message part 1 (text/plain, inline)]
The patches again, this time with manual and NEWS entries.
A (very) minor inconvenience with this approach is that most declarations, like `important-return-value`, has no effect because of the early inline expansion. Some trivial constant-folding (as with an empty list) could be recovered by some modest compiler improvements.
Regarding the return values from `all`, `any` etc I've followed the Lisp tradition of not normalising a non-nil value to `t` to avoid some unnecessary overhead and because the value might be useful.
[0001-Add-drop-while-and-take-while.patch (application/octet-stream, attachment)]
[0002-Add-any-all-notany-and-notall.patch (application/octet-stream, attachment)]
Information forwarded
to
bug-gnu-emacs <at> gnu.org:
bug#79611; Package
emacs.
(Fri, 17 Oct 2025 13:53:03 GMT)
Full text and
rfc822 format available.
Message #35 received at 79611 <at> debbugs.gnu.org (full text, mbox):
> Cc: Michael Heerdegen <michael_heerdegen <at> web.de>, 79611 <at> debbugs.gnu.org,
> Sean Whitton <spwhitton <at> spwhitton.name>
> From: Mattias Engdegård <mattias.engdegard <at> gmail.com>
> Date: Fri, 17 Oct 2025 15:16:21 +0200
>
> The patches again, this time with manual and NEWS entries.
Thanks.
> +@defun drop-while pred list
> +This function skips leading list elements for which the predicate @var{pred}
> +returns non-@code{nil} and returns the rest.
^
A comma is missing there.
> +@defun take-while pred list
> +This function returns the leading list elements for which the predicate
> +@var{pred} returns non-@code{nil} and ignores the rest.
^
Same here.
> --- a/lisp/subr.el
> +++ b/lisp/subr.el
Why not make drop-while and take-while autoloaded functions in subr-x
instead?
I'm worried that we keep bloating the default footprint with more and
more functions which (based on the fact we didn't have until now) are
rarely used.
> +(defun take-while (pred list)
> + "Longest prefix of LIST whose elements satisfy PRED."
I think "Return the longest prefix of LIST whose elements satisfy
PRED." is a better wording.
> +(defun drop-while (pred list)
> + "Suffix of LIST after the longest prefix of elements that satisfy PRED."
Similarly here.
> --- a/lisp/subr.el
> +++ b/lisp/subr.el
Same here: why not have all, any, notall, and notany autoloaded
functions in subr-x.el?
> +(defun all (pred list)
> + "Whether PRED is true for all elements in LIST."
I prefer "Return non-nil if PRED is true for all elements in LIST."
Similarly for other functions.
> +(defun any (pred list)
> + "Whether PRED is true for at least one element in LIST.
> +Returns the longest suffix of LIST whose first element satisfies PRED,
> +or nil if none does."
Here, by "whose" you mean "suffix of LIST, but it could also be
interpreted as alluding to the original LIST instead. Can the wording
be changed to avoid the ambiguity?
> +(defun notall (pred list)
> + "Whether PRED is false for at least one element in LIST.
> +Returns the longest suffix of LIST whose first element does not satisfy PRED,
> +or nil if all do. This function is the same as `drop-while'."
Same here.
Information forwarded
to
bug-gnu-emacs <at> gnu.org:
bug#79611; Package
emacs.
(Fri, 17 Oct 2025 15:28:01 GMT)
Full text and
rfc822 format available.
Message #38 received at 79611 <at> debbugs.gnu.org (full text, mbox):
Hello Mattias,
Thanks for the new patches. Stefan suggested looking into improving the
existing functions instead of adding new ones. Have you looked into
that?
--
Sean Whitton
Information forwarded
to
bug-gnu-emacs <at> gnu.org:
bug#79611; Package
emacs.
(Sat, 18 Oct 2025 13:30:05 GMT)
Full text and
rfc822 format available.
Message #41 received at 79611 <at> debbugs.gnu.org (full text, mbox):
[Message part 1 (text/plain, inline)]
After going a bit back-and-forth I decided to drop `notall` and `notany` for now because it wasn't clear that they'd really make code easier to read or write, compared to (not (all ...)) and (not (any ...)). They could always be added later.
17 okt. 2025 kl. 15.52 skrev Eli Zaretskii <eliz <at> gnu.org>:
>> +@defun drop-while pred list
>> +This function skips leading list elements for which the predicate @var{pred}
>> +returns non-@code{nil} and returns the rest.
> ^
> A comma is missing there.
Yes, it's probably better that way. Thank you, fixed both.
> Why not make drop-while and take-while autoloaded functions in subr-x
> instead?
Nothing against that in principle but I'd really like the new functions to be available for Emacs itself, such as the compiler, without causing bootstrapping problems.
Existing code tries to work around this by adding lower-quality duplicates of these functions (rx--every), explicit `while` loops or ridiculous expressions like
(null (delq nil (mapcar (lambda (x) (not (symbolp x))) v)))
and you are certainly forgiven if you cannot immediately tell what the above line does; surely
(all #'symbolp v)
is better in every way.
What about moving them to subr-x when we can show that bootstrapping wouldn't be an obstacle to their use?
>> +(defun take-while (pred list)
>> + "Longest prefix of LIST whose elements satisfy PRED."
>
> I think "Return the longest prefix of LIST whose elements satisfy
> PRED." is a better wording.
That's fine, I can use that.
>> +(defun drop-while (pred list)
>> + "Suffix of LIST after the longest prefix of elements that satisfy PRED."
>
> Similarly here.
There's a bit of Emacs-English golfing here to fit it on a line:
"Return the suffix of LIST after the longest prefix of elements that satisfy PRED."
"Return the shortest suffix of LIST after elements that all satisfy PRED."
"Skip initial elements of LIST satisfying PRED and return the rest."
I went with the last one, putting brevity before precision.
>> +(defun all (pred list)
>> + "Whether PRED is true for all elements in LIST."
>
> I prefer "Return non-nil if PRED is true for all elements in LIST."
That's fine.
>> +(defun any (pred list)
>> + "Whether PRED is true for at least one element in LIST.
>> +Returns the longest suffix of LIST whose first element satisfies PRED,
>> +or nil if none does."
>
> Here, by "whose" you mean "suffix of LIST, but it could also be
> interpreted as alluding to the original LIST instead. Can the wording
> be changed to avoid the ambiguity?
I don't think the ambiguity really is a problem here but I changed it to
Returns the LIST suffix starting at the first element that satisfies PRED,
or nil if none does.
[0001-Add-drop-while-and-take-while.patch (application/octet-stream, attachment)]
[0002-Add-any-and-all.patch (application/octet-stream, attachment)]
Information forwarded
to
bug-gnu-emacs <at> gnu.org:
bug#79611; Package
emacs.
(Sat, 18 Oct 2025 14:29:02 GMT)
Full text and
rfc822 format available.
Message #44 received at 79611 <at> debbugs.gnu.org (full text, mbox):
> From: Mattias Engdegård <mattias.engdegard <at> gmail.com>
> Date: Sat, 18 Oct 2025 15:29:33 +0200
> Cc: Stefan Monnier <monnier <at> iro.umontreal.ca>,
> Michael Heerdegen <michael_heerdegen <at> web.de>,
> 79611 <at> debbugs.gnu.org,
> Sean Whitton <spwhitton <at> spwhitton.name>
>
> > Why not make drop-while and take-while autoloaded functions in subr-x
> > instead?
>
> Nothing against that in principle but I'd really like the new functions to be available for Emacs itself, such as the compiler, without causing bootstrapping problems.
>
> Existing code tries to work around this by adding lower-quality duplicates of these functions (rx--every), explicit `while` loops or ridiculous expressions like
>
> (null (delq nil (mapcar (lambda (x) (not (symbolp x))) v)))
>
> and you are certainly forgiven if you cannot immediately tell what the above line does; surely
>
> (all #'symbolp v)
>
> is better in every way.
> What about moving them to subr-x when we can show that bootstrapping wouldn't be an obstacle to their use?
Fine by me.
Thanks for the other changes, they LGTM.
Information forwarded
to
bug-gnu-emacs <at> gnu.org:
bug#79611; Package
emacs.
(Sat, 18 Oct 2025 16:19:01 GMT)
Full text and
rfc822 format available.
Message #47 received at 79611 <at> debbugs.gnu.org (full text, mbox):
Hello,
On Sat 18 Oct 2025 at 03:29pm +02, Mattias Engdegård wrote:
> After going a bit back-and-forth I decided to drop `notall` and `notany` for
> now because it wasn't clear that they'd really make code easier to read or
> write, compared to (not (all ...)) and (not (any ...)). They could always be
> added later.
Makes sense to me.
--
Sean Whitton
Reply sent
to
Mattias Engdegård <mattias.engdegard <at> gmail.com>:
You have taken responsibility.
(Mon, 20 Oct 2025 10:18:02 GMT)
Full text and
rfc822 format available.
Notification sent
to
Mattias Engdegård <mattias.engdegard <at> gmail.com>:
bug acknowledged by developer.
(Mon, 20 Oct 2025 10:18:02 GMT)
Full text and
rfc822 format available.
Message #52 received at 79611-done <at> debbugs.gnu.org (full text, mbox):
18 okt. 2025 kl. 16.28 skrev Eli Zaretskii <eliz <at> gnu.org>:
> Thanks for the other changes, they LGTM.
Thank you, now pushed to master.
This bug report was last modified 17 days ago.
Previous Next
GNU bug tracking system
Copyright (C) 1999 Darren O. Benham,
1997,2003 nCipher Corporation Ltd,
1994-97 Ian Jackson.